3.1.3. 그래프 활용: 그래프의 이해, 구현 및 탐색

3.1.3. 그래프 활용:  정점과 간선의 관계, 그리고 탐색 알고리즘을 중심

1. 그래프(Graph)의 기본 이해

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 비선형 자료구조입니다.

• 무방향 그래프 vs 방향 그래프: 간선에 화살표(방향)가 있는지에 따라 나뉩니다.
• 가중치 그래프(Network): 간선에 비용(Cost)이나 거리 같은 수치가 부여된 그래프입니다.
• 완전 그래프(Complete Graph): 모든 정점이 서로 연결된 그래프입니다.
  • 간선 수 계산 (단골 문제): 정점이 $n$개일 때 무방향 완전 그래프의 간선 수는 $\frac{n(n-1)}{2}$입니다.
• 차수(Degree): 하나의 정점에 연결된 간선의 수입니다. 방향 그래프에서는 들어오는 진입 차수(In-degree)와 나가는 진출 차수(Out-degree)로 나뉩니다.

---

2. 그래프의 구현 (표현 방법)

컴퓨터 메모리에 그래프를 저장하는 방식은 크게 두 가지입니다.

1. 인접 행렬 (Adjacency Matrix): $2$차원 배열을 사용합니다.
   • 연결되어 있으면 $1$, 아니면 $0$으로 표시합니다.
   • 장점: 두 정점이 연결되었는지 확인하기 매우 빠릅니다 ($O(1)$).
   • 단점: 정점은 많은데 간선이 적을 경우 메모리 낭비가 심합니다 ($O(n^2)$).
2. 인접 리스트 (Adjacency List): 각 정점에 연결된 노드들을 연결 리스트로 저장합니다.
   • 장점: 간선의 개수만큼만 메모리를 사용하므로 효율적입니다.
   • 단점: 두 정점이 연결되었는지 확인하려면 리스트를 다 뒤져야 합니다.

---

3. 그래프 탐색 알고리즘 (핵심 중의 핵심)

모든 정점을 한 번씩 방문하는 방법으로, 시험에서 경로 찾기 문제가 반드시 나옵니다.

가. DFS (Depth First Search, 깊이 우선 탐색)

• 원리: 한 방향으로 갈 수 있는 한 가장 깊게 탐색하다가 더 이상 갈 곳이 없으면 뒤로 돌아와서 다른 길을 찾는 방식입니다.
• 자료구조: 스택(Stack)을 사용하거나 재귀 호출(Recursion)을 이용합니다.
• 특징: 모든 노드를 방문하고자 할 때 주로 사용합니다.

나. BFS (Breadth First Search, 너비 우선 탐색)

• 원리: 시작 정점으로부터 가까운 정점들을 먼저 방문하고 점차 멀리 있는 정점들을 방문하는 방식입니다.
• 자료구조: 큐(Queue)를 사용합니다.
• 특징: 두 정점 사이의 최단 경로를 찾을 때 유리합니다.

---

4. 최소 신장 트리 (MST, Minimum Spanning Tree)

그래프의 모든 정점을 연결하되, 간선들의 가중치 합이 최소가 되는 트리입니다.

• Kruskal(크루스칼) 알고리즘: 가중치가 작은 간선부터 차례대로 선택합니다. 단, 사이클이 형성되지 않아야 합니다 (Greedy 방식).
• Prim(프림) 알고리즘: 임의의 시작점에서 출발하여 연결된 정점들 중 가장 가중치가 작은 정점을 선택하며 확장합니다.

---

필기 시험 핵심 요약

1. DFS는 Stack, BFS는 Queue! 이 공식은 시험장에 갈 때까지 잊지 마세요.
2. 완전 그래프 간선 수 계산: "정점이 6개인 무방향 완전 그래프의 간선 수는?" $\rightarrow \frac{6 \times 5}{2} = 15$개.
3. 최단 경로 알고리즘: 다익스트라(Dijkstra) 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 데 쓰입니다.
4. 트리와 그래프의 차이: 트리는 사이클이 없는 그래프의 일종입니다. 즉, 모든 트리는 그래프이지만 모든 그래프가 트리는 아닙니다.