DFS vs BFS
| 항목 | DFS (깊이 우선) | BFS (너비 우선) |
|---|
| 자료구조 | 스택 (재귀) | 큐 |
| 메모리 | O(h) - 효율적 | O(w) - 많음 |
| 최단 경로 | 미보장 | 보장 (비가중) |
| 사이클 감지 | 적합 | 적합 |
| 적용 | 위상정렬, SCC, 경로 | 최단 경로, 레벨 탐색 |
Dijkstra vs Bellman-Ford vs Floyd-Warshall
| 비교 항목 | Dijkstra | Bellman-Ford | Floyd-Warshall |
|---|
| 유형 | 단일 출발 | 단일 출발 | 모든 쌍 |
| 설계 기법 | 탐욕 (Greedy) | 동적 프로그래밍 | 동적 프로그래밍 |
| 시간 복잡도 | O((V+E)logV) - 힙 | O(VE) | O(V³) |
| 공간 복잡도 | O(V) | O(V) | O(V²) |
| 음수 가중치 | 불가 | 가능 | 가능 |
| 음수 사이클 탐지 | 불가 | 가능 (V번째 반복) | 가능 (dist[i][i]<0) |
| 핵심 자료구조 | 우선순위 큐 (힙) | 간선 리스트 | 인접 행렬 |
| 핵심 연산 | 최소 거리 정점 추출 + Relaxation | 모든 간선 Relaxation V-1회 | 경유 정점별 거리 갱신 |
| 구현 복잡도 | 중간 (힙 관리) | 낮음 (3중 for) | 매우 낮음 (3중 for) |
| 적합한 경우 | 양수 가중치 단일 출발 | 음수 가중치 존재 | 작은 그래프 모든 쌍 |
Kruskal vs Prim (MST)
| 항목 | Kruskal | Prim |
|---|
| 접근 | 간선 기반 (정렬 후 선택) | 정점 기반 (확장) |
| 자료구조 | Union-Find | 우선순위 큐 |
| 시간 | O(E log E) | O((V+E) log V) |
| 적합 | 희소 그래프 | 밀집 그래프 |
| 구현 | 간선 정렬 + Union-Find | 인접 리스트 + 힙 |
위상 정렬: DFS 기반 vs Kahn 알고리즘
| 항목 | DFS 기반 | Kahn (진입차수) |
|---|
| 방식 | 후위 순서의 역순 | 진입차수 0부터 큐 처리 |
| 사이클 감지 | 백 엣지로 감지 | 결과 크기 != V 시 사이클 |
| 적용 | 재귀 자연스러운 경우 | 반복문 선호 시 |