그래프 알고리즘
그래프 표현
# 인접 리스트 (공간 효율)
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 4],
}
# 인접 행렬 (조회 O(1))
matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 0],
[0, 1, 0, 0],
]BFS (너비 우선 탐색)
최단 경로 (가중치 없는 그래프), 레벨 탐색.
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)DFS (깊이 우선 탐색)
연결 요소, 위상 정렬, 사이클 감지.
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited다익스트라 (Dijkstra)
단일 출발지 최단 경로. 음수 간선 불가. O((V+E) log V).
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)] # (거리, 노드)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist벨만-포드 (Bellman-Ford)
음수 간선 허용, 음수 사이클 감지. O(VE).
def bellman_ford(edges, V, start):
dist = [float('inf')] * V
dist[start] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 음수 사이클 감지
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # 음수 사이클 존재
return dist플로이드-워셜 (Floyd-Warshall)
모든 쌍 최단 경로. O(V³).
def floyd_warshall(dist): # dist: V×V 행렬
V = len(dist)
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist위상 정렬 (Topological Sort)
DAG(방향 비순환 그래프)에서 의존성 순서 정렬.
from collections import deque
def topological_sort(graph, in_degree):
queue = deque([u for u in graph if in_degree[u] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result최소 신장 트리 (MST)
크루스칼 (Kruskal) — 간선 중심
def kruskal(edges, V): # edges: (비용, u, v)
edges.sort()
parent = list(range(V))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
parent[px] = py
return True
mst_cost = 0
for cost, u, v in edges:
if union(u, v):
mst_cost += cost
return mst_cost프림 (Prim) — 정점 중심
def prim(graph, start):
visited = set([start])
heap = [(w, start, v) for v, w in graph[start]]
heapq.heapify(heap)
total = 0
while heap:
w, u, v = heapq.heappop(heap)
if v in visited: continue
visited.add(v)
total += w
for nv, nw in graph[v]:
if nv not in visited:
heapq.heappush(heap, (nw, v, nv))
return total