CHAPTER 04

그래프 알고리즘

정점과 간선으로 세상을 모델링하다 — DFS, BFS, MST, 최단 경로, 사이클 탐지까지

Graph Traversal DFS / BFS Kruskal MST Dijkstra Floyd Cycle Union-Find
§1 · 그래프 기본

Graph Basics

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 소셜 네트워크, 지도, 인터넷 라우팅 — 현실의 수많은 문제가 그래프로 모델링됩니다.

노드를 드래그해서 이동할 수 있습니다.
ADJACENCY LIST
정점 V = 6 간선 E = 8 공간 O(V+E)
§2 · 깊이/너비 우선 탐색

DFS / BFS

그래프를 탐색하는 두 가지 전략입니다. DFS(깊이우선탐색)는 스택을 사용해 한 방향으로 끝까지 파고들고, BFS(너비우선탐색)는 큐를 사용해 가까운 노드부터 탐색합니다.

시작 노드
속도 5
STACK / QUEUE
VISITED
탐색 순서:
시간 O(V+E) 공간 O(V) DFS: 스택 기반 BFS: 큐 기반
§3 · 최소 신장 트리

Kruskal's Algorithm

신장 트리(Spanning Tree)는 모든 정점을 연결하는 최소한의 간선 집합입니다. Kruskal 알고리즘은 가중치 오름차순으로 간선을 추가하되, 사이클을 만들지 않는 간선만 선택합니다(Union-Find 활용).

MST 가중치: —
정렬된 간선 리스트
시간 O(E log E) 공간 O(V) Union-Find Greedy Algorithm
§4 · 최단 경로

Dijkstra's Algorithm

단일 출발점 최단 경로 알고리즘입니다. 음수 가중치가 없는 그래프에서 출발점에서 모든 정점까지의 최단 거리를 구합니다. 구글 지도, 네트워크 라우팅의 핵심 알고리즘입니다.

출발 노드
최단 거리 테이블
시간 O((V+E) log V) 공간 O(V) Priority Queue 음수 가중치 불가
§5 · 사이클 탐지

Floyd's Tortoise & Hare

Floyd의 토끼와 거북이 알고리즘은 연결 리스트에서 사이클을 O(n) 시간, O(1) 공간으로 탐지합니다. 느린 포인터(거북이)는 한 칸씩, 빠른 포인터(토끼)는 두 칸씩 이동합니다. 사이클이 있으면 반드시 만납니다.

연결 리스트: 1 → 2 → 3 → 4 → 5 → 6 → 3 (사이클)
🐢 거북이(slow) = 1, 🐇 토끼(fast) = 1 — 탐색 시작
SLOW POINTER 🐢
노드 1
FAST POINTER 🐇
노드 1
단계
0
시간 O(n) 공간 O(1) Two Pointers 사이클 시작점도 탐지 가능