AI 요약관련 정보

• 그래프는 정점(노드)과 간선(링크)으로 구성된 연결형 자료 구조로, 데이터 간의 연결 관계를 표현하는 데 사용됩니다. 🔗
• 트리는 사이클이 없고 고립된 노드가 없으며 상하 관계가 없는, 그래프의 특별한 한 종류입니다. 🌳
• 주요 그래프 유형에는 모든 정점이 연결된 연결 그래프, 일부 정점 간 경로가 없는 비연결 그래프가 있습니다. 🌐
• 간선에 방향이 있는 방향 그래프와 방향이 없는 무방향 그래프(양방향과 유사)가 존재합니다. ↔️
• 간선에 거리나 비용 같은 가중치가 부여된 가중치 그래프가 있으며, 가중치는 음수도 가능합니다. 💰
• 서브 그래프는 특정 그래프의 정점과 간선의 부분으로 이루어진 그래프를 의미합니다. 🧩
• 그래프는 인접 행렬(2차원 배열) 또는 인접 리스트(연결 리스트) 방식으로 코드상에서 표현할 수 있습니다. 💻
• 인접 행렬은 N*N 크기의 배열로 연결 여부(0 또는 1)나 가중치를 저장하며, 무방향 그래프는 대칭성을 가집니다. 📊
• 인접 리스트는 각 정점에 연결된 정점들을 연결 리스트로 관리하며, 가중치 그래프의 경우 노드에 가중치 데이터를 추가합니다. 📝
• 그래프 탐색 연산에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있으며, 이들은 트리에도 적용 가능합니다. 🔍
• 깊이 우선 탐색(DFS)은 스택을 활용하여 더 이상 방문할 정점이 없을 때까지 최대한 깊이 탐색 후 뒤로 돌아갑니다. ⬇️
• 너비 우선 탐색(BFS)은 큐를 활용하여 현재 정점에서 연결된 모든 정점을 먼저 탐색한 후 다음 깊이로 넘어갑니다. ➡️