**그래프(Graph)**는 정점(Vertex)들과 이들을 연결하는 간선(Edge)들의 집합 $G = (V, E)$로 표현되는 비선형 자료구조입니다.
1. 그래프 표현 방식
- 인접 행렬 (Adjacency Matrix): $V imes V$ 2차원 배열 사용. 간선 조회 $O(1)$, 메모리 $O(V^2)$.
- 인접 리스트 (Adjacency List): 각 정점에 연결된 정점 목록을 리스트로 유지. 메모리 $O(V+E)$, 희소 그래프에 효율적.
2. 그래프 순회: DFS vs BFS
| 특징 | 깊이 우선 탐색 (DFS) | 너비 우선 탐색 (BFS) |
|---|---|---|
| 탐색 방식 | 한 노선으로 갈 수 있는 데까지 깊게 탐색 | 시작점에서 가까운 정점부터 넓게 탐색 |
| 구현 도구 | 스택(Stack) 또는 재귀 함수 | 큐(Queue) |
| 시간 복잡도 | $O(V+E)$ (인접 리스트 기준) | $O(V+E)$ (인접 리스트 기준) |
| 주요 활용 | 사이클 검출, 백트래킹, 위상 정렬 | 가중치 없는 최단 경로 탐색 |
3. 최소 신장 트리 (MST, Minimum Spanning Tree)
그래프의 모든 정점을 연결하면서 사이클이 없는 간선 가중치 합의 최솟값을 찾는 문제.
- 프림(Prim) 알고리즘: 하나의 정점에서 시작하여 연결된 최소 가중치 간선 정점을 확장 ($O(E log V)$).
- 크루스칼(Kruskal) 알고리즘: 모든 간선을 가중치 순 정렬 후, Union-Find 알고리즘으로 사이클 발생 여부를 확인하며 연결 ($O(E log E)$).
4. 최단 경로: 다익스트라 (Dijkstra) 알고리즘
가중치가 양수인 그래프에서 특정 출발 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.
- 우선순위 큐(Heap) 활용 시 시간 복잡도: $O((V+E) log V)$
5. 자주 묻는 질문 (Q&A)
Q. 다익스트라 알고리즘에서 음수 가중치 간선이 존재하면 어떤 문제가 발생하나요? A. 최단 거리를 구했더라도 음수 가중치 간선을 지나면서 거리가 더 짧아질 수 있어 최적성이 깨집니다. 음수 가중치가 존재할 때는 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.