# [06-08] 그래프 알고리즘
그래프 알고리즘은 최소 신장 트리, 최단 경로, 위상 정렬 등 그래프 구조에 특화된 문제를 효율적으로 해결하는 알고리즘들입니다.
🎯 그래프 알고리즘이란
그래프 문제의 특징
그래프 자료구조를 배웠다면, 이제 그래프로 표현된 문제를 효율적으로 해결하는 알고리즘을 배울 차례입니다.
자료구조 vs 알고리즘:
자료구조 파트에서 배운 것:
- 그래프란? (정점, 간선, 용어)
- 표현 방법 (인접 행렬, 인접 리스트)
- 기본 탐색 (DFS, BFS)
알고리즘 파트에서 배울 것:
- 최소 비용 네트워크 (MST)
- 최단 경로 찾기
- 작업 순서 정하기 (위상 정렬)
- 연결성 분석실생활 문제:
통신망 구축:
- 모든 도시를 연결하되 비용 최소화
→ 최소 신장 트리 (MST)
내비게이션:
- 출발지에서 목적지까지 최단 경로
→ 최단 경로 알고리즘
프로젝트 일정:
- 선후 관계를 고려한 작업 순서
→ 위상 정렬🌳 최소 신장 트리 (MST, Minimum Spanning Tree)
신장 트리란?
신장 트리(Spanning Tree)와 최소 신장 트리(Minimum Spanning Tree, MST)를 이해해 봅시다.
신장 트리:
그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프
특징:
- 모든 정점 포함
- 간선 개수 = 정점 개수 - 1
- 사이클 없음 (트리)
예:
원본 그래프: 신장 트리 중 하나:
A─B─C A─B─C
│ │ │ │
D─E─F D─E─F
간선 7개 간선 5개 (6개 정점 - 1)최소 신장 트리:
가중 그래프에서 총 가중치가 최소인 신장 트리
예:
A ─2─ B
│╲ │
1 3 4
│ ╲ │
C ─5─ D
가능한 신장 트리:
1. A-C(1) + C-D(5) + A-B(2) = 8
2. A-C(1) + A-D(3) + A-B(2) = 6 ← 최소!
3. A-C(1) + A-D(3) + D-B(4) = 8
MST: A-C(1) + A-D(3) + A-B(2) = 6실생활 응용:
통신망 구축:
- 모든 도시를 연결
- 케이블 비용 최소화
전력망:
- 모든 건물에 전기
- 전선 길이 최소화
도로망:
- 모든 마을 연결
- 건설 비용 최소화Kruskal 알고리즘
Kruskal은 간선을 가중치 순으로 정렬하여 MST를 만드는 그리디 알고리즘입니다.
핵심 아이디어:
1. 모든 간선을 가중치 오름차순 정렬
2. 가장 작은 간선부터 선택
3. 사이클을 만들지 않으면 추가
4. V-1개 간선을 선택할 때까지 반복
"욕심쟁이 방식"
- 항상 가장 저렴한 간선 선택
- 사이클만 피하면 됨사이클 판단: Union-Find 자료구조 사용
Union-Find:
- 각 정점이 어느 집합에 속하는지 관리
- 같은 집합끼리 연결하면 사이클 발생
예:
간선 A-B 추가:
A 집합: {A}
B 집합: {B}
→ 다른 집합 → 연결 가능 → Union
간선 A-C 추가:
A 집합: {A, B}
C 집합: {C}
→ 다른 집합 → 연결 가능 → Union
간선 B-C 추가:
B 집합: {A, B, C}
C 집합: {A, B, C}
→ 같은 집합 → 사이클 발생! → 거부Kruskal 구현
class UnionFind:
"""
Union-Find 자료구조 (Disjoint Set)
사이클 판단에 사용
"""
def __init__(self, n):
"""
n: 정점 개수
"""
# parent[i]: i의 부모 (초기: 자기 자신)
self.parent = list(range(n))
# rank[i]: i를 루트로 하는 트리의 높이
self.rank = [0] * n
def find(self, x):
"""
x가 속한 집합의 대표(루트) 찾기
경로 압축(Path Compression) 최적화:
- 찾는 과정에서 트리를 평평하게
시간복잡도: O(α(n)) ≈ O(1)
"""
if self.parent[x] != x:
# 재귀적으로 루트 찾기 + 경로 압축
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
x와 y가 속한 집합 합치기
Union by Rank 최적화:
- 높이가 낮은 트리를 높은 트리 아래 붙임
Returns: bool: 합쳤으면 True, 이미 같은 집합이면 False
"""
root_x = self.find(x)
root_y = self.find(y)
# 이미 같은 집합
if root_x == root_y:
return False
# Union by Rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal(num_vertices, edges):
"""
Kruskal의 최소 신장 트리 알고리즘
num_vertices: 정점 개수
edges: [(u, v, weight), ...] 간선 리스트
Returns: (최소 비용, MST 간선 리스트)
시간복잡도: O(E log E)
- 간선 정렬: O(E log E)
- Union-Find: O(E × α(V)) ≈ O(E)
알고리즘:
1. 간선을 가중치 순 정렬
2. 작은 것부터 선택
3. 사이클 안 만들면 추가
"""
# 1. 간선을 가중치 오름차순 정렬
edges.sort(key=lambda x: x[2])
# Union-Find 초기화
uf = UnionFind(num_vertices)
mst_edges = [] # MST에 포함될 간선
mst_cost = 0 # 총 비용
# 2. 각 간선 확인
for u, v, weight in edges:
# 3. 사이클을 만들지 않으면 추가
if uf.union(u, v):
mst_edges.append((u, v, weight))
mst_cost += weight
# MST 완성 (V-1개 간선)
if len(mst_edges) == num_vertices - 1:
break
return mst_cost, mst_edges
# 사용 예시
# 정점: 0, 1, 2, 3
# 간선: (u, v, weight)
edges = [
(0, 1, 2),
(0, 2, 1),
(0, 3, 3),
(1, 2, 3),
(1, 3, 4),
(2, 3, 5)
]
cost, mst = kruskal(4, edges)
print(f"최소 신장 트리 비용: {cost}")
print("MST 간선:")
for u, v, w in mst:
print(f" {u} - {v}: {w}")실행 과정:
간선 정렬:
(0,2,1), (0,1,2), (0,3,3), (1,2,3), (1,3,4), (2,3,5)
단계 1: (0,2,1) 선택
- find(0)=0, find(2)=2 (다른 집합)
- union(0,2) → MST에 추가
- 집합: {0,2}, {1}, {3}
- MST: [(0,2,1)], 비용: 1
단계 2: (0,1,2) 선택
- find(0)=0, find(1)=1 (다른 집합)
- union(0,1) → MST에 추가
- 집합: {0,1,2}, {3}
- MST: [(0,2,1), (0,1,2)], 비용: 3
단계 3: (0,3,3) 선택
- find(0)=0, find(3)=3 (다른 집합)
- union(0,3) → MST에 추가
- 집합: {0,1,2,3}
- MST: [(0,2,1), (0,1,2), (0,3,3)], 비용: 6
V-1=3개 간선 선택 완료!Prim 알고리즘
Prim은 정점을 하나씩 추가하며 MST를 만드는 그리디 알고리즘입니다.
핵심 아이디어:
1. 임의의 시작 정점 선택
2. MST에 포함된 정점들과 연결된 간선 중 최소 선택
3. 새 정점 추가
4. 모든 정점이 포함될 때까지 반복
"점진적 확장"
- 항상 현재 트리에서 가장 가까운 정점 추가Kruskal vs Prim:
Kruskal:
- 간선 중심
- 전체 간선 정렬
- Union-Find 사용
- 희소 그래프에 유리
Prim:
- 정점 중심
- 우선순위 큐 사용
- 시작점에서 확장
- 밀집 그래프에 유리Prim 구현
import heapq
def prim(num_vertices, adj_list, start=0):
"""
Prim의 최소 신장 트리 알고리즘
num_vertices: 정점 개수
adj_list: 인접 리스트 {v: [(neighbor, weight), ...]}
start: 시작 정점
Returns: (최소 비용, MST 간선 리스트)
시간복잡도: O((V + E) log V)
- 우선순위 큐 사용
알고리즘:
1. 시작 정점 선택
2. 연결된 간선들을 우선순위 큐에 추가
3. 최소 가중치 간선 선택
4. 새 정점이면 MST에 추가
"""
visited = set() # MST에 포함된 정점
mst_edges = []
mst_cost = 0
# 우선순위 큐: (가중치, 정점1, 정점2)
pq = []
# 1. 시작 정점부터
visited.add(start)
# 시작 정점의 모든 간선을 큐에 추가
for neighbor, weight in adj_list[start]:
heapq.heappush(pq, (weight, start, neighbor))
# 2. MST가 완성될 때까지
while pq and len(visited) < num_vertices:
# 3. 최소 가중치 간선 선택
weight, u, v = heapq.heappop(pq)
# 이미 MST에 포함된 정점이면 건너뛰기
if v in visited:
continue
# 4. MST에 추가
visited.add(v)
mst_edges.append((u, v, weight))
mst_cost += weight
# 새로 추가된 정점의 간선들을 큐에 추가
for neighbor, w in adj_list[v]:
if neighbor not in visited:
heapq.heappush(pq, (w, v, neighbor))
return mst_cost, mst_edges
# 사용 예시
# 인접 리스트로 표현
adj_list = {
0: [(1, 2), (2, 1), (3, 3)],
1: [(0, 2), (2, 3), (3, 4)],
2: [(0, 1), (1, 3), (3, 5)],
3: [(0, 3), (1, 4), (2, 5)]
}
cost, mst = prim(4, adj_list, start=0)
print(f"최소 신장 트리 비용: {cost}")
print("MST 간선:")
for u, v, w in mst:
print(f" {u} - {v}: {w}")🛣️ 최단 경로 알고리즘
최단 경로 (Single-Source Shortest Path) 문제의 종류
최단 경로 문제는 여러 변형이 있습니다.
1. 단일 출발점 최단 경로
한 정점에서 다른 모든 정점까지의 최단 경로
예: 내비게이션
출발: 서울
도착: 모든 도시
알고리즘:
- Dijkstra (양수 가중치)
- Bellman-Ford (음수 가중치 허용)2. 모든 쌍 최단 경로 (All-Pairs Shortest Path)
모든 정점 쌍 사이의 최단 경로
예: 물류 네트워크
모든 도시 간 최단 거리 표
알고리즘:
- Floyd-WarshallDijkstra 알고리즘 (복습 + 확장)
자료구조 파트에서 간단히 다뤘던 Dijkstra를 더 깊이 이해해 봅시다.
제약 조건: 음수 가중치 불가
왜 음수 가중치가 안 되나?
그래프:
A ─2→ B
↓ ↓
-5 1
↓ ↓
C ─→ D
A에서 D로:
경로 1: A → B → D = 2 + 1 = 3
경로 2: A → C → D = -5 + ? (C→D 간선 필요)
문제:
Dijkstra는 "확정된" 정점을 다시 보지 않음
→ 음수 간선으로 더 짧아질 수 있음을 놓침Bellman-Ford 알고리즘
Bellman-Ford는 음수 가중치를 허용하는 최단 경로 알고리즘입니다.
핵심 아이디어:
모든 간선을 V-1번 반복하며 거리 갱신
왜 V-1번?
- 최단 경로는 최대 V-1개 간선
- V번째에도 갱신되면? → 음수 사이클 존재!
음수 사이클:
A → B → C → A (총 비용: -1)
계속 돌면 무한히 짧아짐 → 최단 경로 없음Bellman-Ford 구현
def bellman_ford(num_vertices, edges, start):
"""
Bellman-Ford 최단 경로 알고리즘
num_vertices: 정점 개수
edges: [(u, v, weight), ...] 간선 리스트
start: 시작 정점
Returns: (거리 딕셔너리, 음수 사이클 존재 여부)
시간복잡도: O(VE)
- V-1번 반복
- 각 반복마다 E개 간선 확인
특징:
- 음수 가중치 허용
- 음수 사이클 탐지
- Dijkstra보다 느림
"""
# 거리 초기화
dist = {v: float('inf') for v in range(num_vertices)}
dist[start] = 0
# V-1번 반복
for _ in range(num_vertices - 1):
# 모든 간선에 대해 relaxation
updated = False
for u, v, weight in edges:
# u를 거쳐 v로 가는 것이 더 짧으면
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
updated = True
# 갱신이 없으면 조기 종료 (최적화)
if not updated:
break
# 음수 사이클 확인 (V번째 반복)
has_negative_cycle = False
for u, v, weight in edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
has_negative_cycle = True
break
return dist, has_negative_cycle
# 사용 예시
edges = [
(0, 1, 4),
(0, 2, 1),
(2, 1, 2),
(1, 3, 1),
(2, 3, 5)
]
dist, has_cycle = bellman_ford(4, edges, start=0)
print("최단 거리:")
for v, d in sorted(dist.items()):
print(f" 0 → {v}: {d}")
if has_cycle:
print("\n음수 사이클 존재!")
else:
print("\n음수 사이클 없음")
# 음수 가중치 예제
edges_negative = [
(0, 1, 1),
(1, 2, -3),
(2, 3, 1),
(0, 3, 4)
]
print("\n\n음수 가중치 그래프:")
dist2, has_cycle2 = bellman_ford(4, edges_negative, start=0)
for v, d in sorted(dist2.items()):
print(f" 0 → {v}: {d}")Floyd-Warshall 알고리즘
Floyd-Warshall은 모든 정점 쌍 사이의 최단 경로를 구하는 동적 계획법 알고리즘입니다.
핵심 아이디어:
3중 반복문으로 모든 경로 확인
for k in 정점들: # 중간 경유지
for i in 정점들: # 출발
for j in 정점들: # 도착
# i → k → j가 더 짧으면 갱신
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
k를 거쳐가는 것이 더 빠른지 확인!Floyd-Warshall 구현
def floyd_warshall(num_vertices, edges):
"""
Floyd-Warshall 모든 쌍 최단 경로
num_vertices: 정점 개수
edges: [(u, v, weight), ...] 간선 리스트
Returns: 거리 행렬 (2차원 리스트)
시간복잡도: O(V³)
공간복잡도: O(V²)
특징:
- 모든 쌍 최단 경로
- 동적 계획법
- 음수 가중치 허용 (음수 사이클 제외)
- 코드 간단
"""
# 거리 행렬 초기화
INF = float('inf')
dist = [[INF] * num_vertices for _ in range(num_vertices)]
# 자기 자신까지의 거리는 0
for i in range(num_vertices):
dist[i][i] = 0
# 간선 정보 입력
for u, v, weight in edges:
dist[u][v] = weight
# Floyd-Warshall
# k: 중간 경유지
for k in range(num_vertices):
# i: 출발점
for i in range(num_vertices):
# j: 도착점
for j in range(num_vertices):
# i → k → j가 더 짧으면 갱신
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# 사용 예시
edges = [
(0, 1, 3),
(0, 2, 8),
(0, 3, -4),
(1, 3, 1),
(1, 4, 7),
(2, 1, 4),
(3, 2, -5),
(3, 4, 6),
(4, 0, 2)
]
dist_matrix = floyd_warshall(5, edges)
print("모든 쌍 최단 거리:")
print(" ", end="")
for j in range(5):
print(f"{j:5d}", end="")
print()
for i in range(5):
print(f"{i}: ", end="")
for j in range(5):
if dist_matrix[i][j] == float('inf'):
print(" INF", end="")
else:
print(f"{dist_matrix[i][j]:5d}", end="")
print()📋 위상 정렬 (Topological Sort)
위상 정렬이란?
위상 정렬은 방향 그래프에서 정점들을 선후 관계를 만족하도록 일렬로 나열하는 것입니다.
실생활 예시:
대학 수강 신청:
- 자료구조를 듣기 전에 프로그래밍 기초
- 알고리즘을 듣기 전에 자료구조
- ...
프로그래밍 기초 → 자료구조 → 알고리즘
프로젝트 일정:
- 설계 완료 후 개발 시작
- 개발 완료 후 테스트 시작
- ...
설계 → 개발 → 테스트 → 배포조건:
1. 방향 그래프 (DAG: Directed Acyclic Graph)
2. 사이클 없음 (필수!)
사이클이 있으면?
A → B → C → A
A를 먼저? 그럼 C는?
C를 먼저? 그럼 B는?
B를 먼저? 그럼 A는?
→ 불가능!위상 정렬: DFS 기반
핵심 아이디어:
DFS로 탐색하되, 종료 시점에 스택에 추가
→ 스택을 뒤집으면 위상 정렬!
왜?
- DFS는 "끝"부터 완료
- 의존하는 것이 없는 것부터 완료
- 역순이 위상 정렬DFS 기반 위상 정렬 구현
def topological_sort_dfs(num_vertices, adj_list):
"""
위상 정렬 - DFS 기반
num_vertices: 정점 개수
adj_list: 인접 리스트 {v: [neighbors]}
Returns: - 위상 정렬 결과 (리스트)
- 사이클이 있으면 None
시간복잡도: O(V + E)
"""
visited = set() # 방문한 정점
rec_stack = set() # 현재 재귀 스택 (사이클 탐지용)
result = [] # 결과 (역순으로 추가됨)
has_cycle = False
def dfs(v):
"""DFS + 사이클 탐지"""
nonlocal has_cycle
# 사이클 탐지
if v in rec_stack:
has_cycle = True
return
if v in visited:
return
# 방문 표시
visited.add(v)
rec_stack.add(v)
# 인접 정점 탐색
for neighbor in adj_list.get(v, []):
dfs(neighbor)
if has_cycle:
return
# 현재 정점 처리 완료
rec_stack.remove(v)
result.append(v) # 종료 시 추가 (역순)
# 모든 정점에 대해 DFS
for v in range(num_vertices):
if v not in visited:
dfs(v)
if has_cycle:
return None # 사이클 있음
# 역순이 위상 정렬
return result[::-1]
# 사용 예시
# 과목 선수 관계
# 0: 프로그래밍 기초
# 1: 자료구조
# 2: 알고리즘
# 3: 운영체제
# 4: 데이터베이스
adj_list = {
0: [1], # 프로그래밍 기초 → 자료구조
1: [2], # 자료구조 → 알고리즘
0: [3], # 프로그래밍 기초 → 운영체제
1: [4], # 자료구조 → 데이터베이스
}
# 제대로 표현 (중복 키 수정)
adj_list = {
0: [1, 3], # 프로그래밍 기초 → 자료구조, 운영체제
1: [2, 4], # 자료구조 → 알고리즘, 데이터베이스
2: [],
3: [],
4: []
}
result = topological_sort_dfs(5, adj_list)
if result:
print("수강 순서:")
course_names = ["프로그래밍 기초", "자료구조", "알고리즘", "운영체제", "데이터베이스"]
for v in result:
print(f" {v}: {course_names[v]}")
else:
print("사이클 존재! (선수 관계 순환)")Kahn 알고리즘 (진입 차수 기반)
진입 차수(indegree)가 0인 노드부터 BFS(너비 우선 탐색) 방식으로 순차적으로 방문하여
DAG(방향 비순환 그래프)의 위상 정렬을 수행하는 효율적인 알고리즘입니다.
진입 차수가 0인 노드를 큐에 넣고, 해당 노드와 연결된 간선을 제거하며 반복하는 방식입니다.
핵심 아이디어:
1. 진입 차수가 0인 정점을 큐에 추가
2. 큐에서 정점 꺼내기
3. 그 정점이 가리키는 정점들의 진입 차수 감소
4. 진입 차수가 0이 되면 큐에 추가
5. 반복
진입 차수 (Indegree):
- 들어오는 간선의 개수
- 선수 과목의 개수Kahn 알고리즘 구현
from collections import deque
def topological_sort_kahn(num_vertices, edges):
"""
위상 정렬 - Kahn 알고리즘 (진입 차수 기반)
num_vertices: 정점 개수
edges: [(u, v), ...] 간선 리스트 (u → v)
Returns: - 위상 정렬 결과
- 사이클이 있으면 None
시간복잡도: O(V + E)
"""
# 인접 리스트와 진입 차수 계산
adj_list = {v: [] for v in range(num_vertices)}
indegree = {v: 0 for v in range(num_vertices)}
for u, v in edges:
adj_list[u].append(v)
indegree[v] += 1
# 진입 차수가 0인 정점들로 시작
queue = deque()
for v in range(num_vertices):
if indegree[v] == 0:
queue.append(v)
result = []
while queue:
# 진입 차수 0인 정점 꺼내기
v = queue.popleft()
result.append(v)
# 이 정점이 가리키는 정점들의 진입 차수 감소
for neighbor in adj_list[v]:
indegree[neighbor] -= 1
# 진입 차수가 0이 되면 큐에 추가
if indegree[neighbor] == 0:
queue.append(neighbor)
# 모든 정점을 방문했는가?
if len(result) == num_vertices:
return result
else:
return None # 사이클 존재
# 사용 예시
edges = [
(0, 1), # 프로그래밍 기초 → 자료구조
(0, 3), # 프로그래밍 기초 → 운영체제
(1, 2), # 자료구조 → 알고리즘
(1, 4), # 자료구조 → 데이터베이스
]
result = topological_sort_kahn(5, edges)
if result:
print("수강 순서 (Kahn):")
course_names = ["프로그래밍 기초", "자료구조", "알고리즘", "운영체제", "데이터베이스"]
for v in result:
print(f" {v}: {course_names[v]}")
else:
print("사이클 존재!")💡 실무 팁
MST 알고리즘 선택
# 희소 그래프 → Kruskal
# 간선이 적음
kruskal(vertices, edges) # O(E log E)
# 밀집 그래프 → Prim
# 간선이 많음
prim(vertices, adj_list) # O((V+E) log V)최단 경로 알고리즘 선택
# 단일 출발점 + 양수 가중치 → Dijkstra
dijkstra(graph, start) # O((V+E) log V)
# 단일 출발점 + 음수 가중치 → Bellman-Ford
bellman_ford(graph, start) # O(VE)
# 모든 쌍 → Floyd-Warshall
floyd_warshall(graph) # O(V³)
# 작은 그래프면 Floyd-Warshall
# 큰 그래프면 Dijkstra V번위상 정렬 선택
# 사이클 탐지도 필요 → DFS
topological_sort_dfs(graph)
# 단순 위상 정렬 → Kahn
topological_sort_kahn(graph)
# 둘 다 O(V+E), 취향 차이🎯 핵심 정리
최소 신장 트리
목표: 모든 정점 연결 + 최소 비용
Kruskal:
- 간선 정렬 후 선택
- Union-Find
- O(E log E)
Prim:
- 정점 확장
- 우선순위 큐
- O((V+E) log V)최단 경로
Dijkstra:
- 단일 출발점
- 양수 가중치
- O((V+E) log V)
Bellman-Ford:
- 단일 출발점
- 음수 가중치 허용
- O(VE)
Floyd-Warshall:
- 모든 쌍
- 동적 계획법
- O(V³)위상 정렬
목표: 선후 관계를 만족하는 순서
DFS 기반:
- 재귀
- 사이클 탐지
Kahn:
- 진입 차수
- 큐 사용
둘 다 O(V+E)🔗 다음 글에서는
[06-09] 문자열 알고리즘
- 문자열 매칭: 패턴을 효율적으로 찾는 다양한 방법
- KMP 알고리즘: 실패 함수를 이용한 빠른 탐색
- 라빈-카프: 해싱을 이용한 패턴 매칭
- 트라이 자료구조: 문자열 집합의 효율적 저장과 검색
이전 글: [06-07] 무작위 알고리즘
다음 글: [06-09] 문자열 알고리즘
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자