토픽 72 / 76·비교표
## Part 5: 그래프 자료구조
인접 행렬 vs 인접 리스트
| 항목 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 공간 | O(V^2) | O(V+E) |
| 간선 확인 | O(1) | O(degree) |
| 순회 | O(V^2) | O(V+E) |
| 적합 그래프 | 밀집 그래프 | 희소 그래프 |
| 적용 | Floyd-Warshall | BFS/DFS, Dijkstra |
DFS vs BFS
| 항목 | DFS (깊이 우선) | BFS (너비 우선) |
|---|---|---|
| 자료구조 | 스택 (재귀/명시적) | 큐 |
| 탐색 순서 | 깊이 먼저 | 너비 먼저 (레벨별) |
| 메모리 | O(h) - 높이 | O(w) - 너비 |
| 최단 경로 | 미보장 | 보장 (비가중) |
| 적용 | 경로 탐색, 위상정렬, SCC | 최단 경로, 레벨 탐색 |