그래프 알고리즘: 연결된 데이터의 탐색과 분석
그래프 알고리즘 공부 노트
그래프를 처음 공부했을 때 제일 혼란스러웠던 건, 용어가 한꺼번에 쏟아진다는 거였습니다. 정점, 간선, 인접 행렬, 인접 리스트, BFS, DFS, 다익스트라, 벨만-포드, 플로이드-워셜, 크루스칼, 위상 정렬… 이름만 나열해도 숨이 차는데, 각각이 뭘 하는 건지 처음엔 잘 구분이 안 됐습니다.
나중에 좀 감이 온 건, 이것들이 전부 “연결 관계가 있는 데이터를 어떻게 돌아다닐 것인가”라는 하나의 질문에서 파생된 거라는 걸 알고 나서였습니다. 그래서 이 노트도 그 흐름대로 정리해봤습니다.
그래프가 뭔지부터
그래프는 **정점(Vertex)**과 그 사이를 잇는 **간선(Edge)**으로 이루어진 구조입니다.
G = (V, E)
- V: 정점들의 집합
- E: 간선들의 집합종류 구분은 이렇게 됩니다.
방향 유무: 간선에 방향이 있으면 방향 그래프(A에서 B로 가는 것과 B에서 A로 가는 게 다름), 없으면 무방향 그래프(A-B와 B-A가 같음).
가중치 유무: 간선에 비용이 붙으면 가중 그래프. 지하철 노선도처럼 역 사이에 소요 시간이 다른 경우를 생각하면 됩니다.
단순 vs 다중: 두 정점 사이에 간선이 하나면 단순, 여러 개 가능하면 다중.
처음엔 이 분류가 왜 필요한지 몰랐는데, 문제를 풀다 보니 “이 그래프가 방향인지 무방향인지”에 따라 코드가 달라져서 결국 외우게 됐습니다.
그래프를 코드로 표현하는 법
인접 행렬
2차원 배열로 연결 여부를 표현합니다. graph[i][j]가 1이면 i에서 j로 연결돼 있다는 뜻입니다.
# 무방향 그래프
graph = [
[0, 1, 1, 0], # 정점 0의 연결
[1, 0, 1, 1], # 정점 1의 연결
[1, 1, 0, 0], # 정점 2의 연결
[0, 1, 0, 0] # 정점 3의 연결
]
# 방향 가중 그래프
weighted_graph = [
[0, 3, 8, 0], # 0→1: 3, 0→2: 8
[0, 0, 0, 1], # 1→3: 1
[0, 4, 0, 0], # 2→1: 4
[0, 0, 2, 0] # 3→2: 2
]두 정점이 연결됐는지 확인하는 건 O(1)로 빠른데, 정점이 많으면 V x V 크기의 배열을 만들어야 해서 메모리를 많이 먹습니다. 정점이 만 개인데 간선이 몇 개 안 되는 경우라면 대부분 빈칸인 배열을 들고 있는 셈이라 비효율적입니다.
인접 리스트
각 정점에 연결된 이웃 목록만 저장합니다.
# 무방향 그래프
graph = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1],
3: [1]
}
# 가중 그래프
weighted_graph = {
0: [(1, 3), (2, 8)], # (이웃, 가중치)
1: [(3, 1)],
2: [(1, 4)],
3: [(2, 2)]
}공간은 O(V + E)로 효율적이고, 실제 문제 풀이에서는 거의 이쪽을 씁니다. 다만 특정 두 정점이 연결됐는지 확인하려면 리스트를 순회해야 해서 O(degree)가 걸립니다. 근데 그게 병목이 되는 경우는 별로 없었습니다.
BFS와 DFS
여기가 처음에 제일 헷갈렸던 부분입니다. 둘 다 “그래프의 모든 정점을 방문한다”는 목적은 같은데 순서가 다릅니다.
BFS - 가까운 데서부터
큐를 써서 시작점에서 가까운 정점부터 차례로 방문합니다. 물에 돌 던지면 파문이 퍼지듯이요.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
order = []
while queue:
vertex = queue.popleft()
order.append(vertex)
# 인접 정점들을 큐에 추가
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# 테스트
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1, 5],
4: [1, 2, 5],
5: [3, 4]
}
print("BFS 순회:", bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]시간 O(V + E), 공간 O(V).
DFS - 한쪽으로 끝까지
스택이나 재귀를 써서 한 방향으로 갈 수 있는 데까지 갔다가 막히면 돌아옵니다.
def dfs_recursive(graph, vertex, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(vertex)
order.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, order)
return order
def dfs_iterative(graph, start):
visited = set()
stack = [start]
order = []
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
order.append(vertex)
# 역순으로 스택에 추가 (DFS를 위해)
for neighbor in reversed(graph[vertex]):
if neighbor not in visited:
stack.append(neighbor)
return order
# 테스트
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1, 5],
4: [1, 2, 5],
5: [3, 4]
}
print("DFS (재귀):", dfs_recursive(graph, 0)) # [0, 1, 3, 5, 4, 2]
print("DFS (반복):", dfs_iterative(graph, 0)) # [0, 2, 4, 5, 3, 1]시간 O(V + E), 공간 O(V).
BFS랑 DFS, 결과가 왜 다른지
처음에 같은 그래프에 BFS랑 DFS를 돌렸는데 방문 순서가 다르게 나와서 “둘 중 하나가 틀린 건가?” 싶었습니다. 종이에 직접 그래프를 그리고 한 스텝씩 따라가 보고서야 이해했습니다. BFS는 레벨별로 퍼지니까 0 -> 1, 2 -> 3, 4 -> 5 이런 순서가 되고, DFS는 한 갈래를 끝까지 파고 들어가니까 0 -> 1 -> 3 -> 5 -> (돌아와서) 4 -> 2 이런 순서가 되는 거였습니다.
| 측면 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 | 스택/재귀 |
| 탐색 순서 | 레벨별 | 깊이 우선 |
| 최단 경로 | 보장 | 불보장 |
| 메모리 | 더 많이 사용 | 적게 사용 |
| 응용 | 최단 경로 | 위상 정렬 |
“최단 경로 찾아라” 하면 BFS, “경로 존재 여부만 확인해라” 하면 DFS도 괜찮고, “모든 경우를 탐색해라” 하면 DFS가 자연스럽습니다. 이 구분이 문제 풀 때 제일 실용적이었습니다.
최단 경로 알고리즘들
여기부터 좀 복잡해지는데, 결국 핵심 질문은 하나입니다: “A에서 B까지 가장 짧은 경로가 뭐냐?”
다익스트라 - 양수 가중치만 있을 때
가장 많이 쓰이는 최단 경로 알고리즘입니다. 시작점에서 가장 가까운 정점부터 확정해나가는 그리디 방식으로 동작합니다.
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
pq = [(0, start)] # (거리, 정점)
while pq:
current_distance, current_node = heapq.heappop(pq)
# 이미 처리된 노드라면 스킵
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
# 더 짧은 경로를 발견하면 업데이트
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_node
heapq.heappush(pq, (distance, neighbor))
return distances, previous
def reconstruct_path(previous, start, end):
path = []
current = end
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return path if path[0] == start else []
# 테스트
graph = {
0: [(1, 4), (2, 1)],
1: [(0, 4), (2, 2), (3, 5)],
2: [(0, 1), (1, 2), (3, 8), (4, 10)],
3: [(1, 5), (2, 8), (4, 2)],
4: [(2, 10), (3, 2)]
}
distances, previous = dijkstra(graph, 0)
print("최단 거리:", distances)
print("경로 0→4:", reconstruct_path(previous, 0, 4))시간 복잡도 O((V + E) log V), 우선순위 큐 덕분입니다. 단, 음수 가중치가 있으면 안 됩니다. 처음에 왜 안 되는지 이해 못했는데, 음수 간선이 있으면 “이미 확정한 최단 거리”가 나중에 뒤집힐 수 있어서 그렇습니다.
벨만-포드 - 음수 가중치도 처리
다익스트라를 못 쓰는 상황(음수 가중치)에서 쓸 수 있습니다. 모든 간선을 V-1번 반복해서 완화하는 방식입니다.
def bellman_ford(graph, start, num_vertices):
distances = {node: float('inf') for node in range(num_vertices)}
distances[start] = 0
# V-1번 반복
for _ in range(num_vertices - 1):
for u, v, weight in graph:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
# 음수 사이클 검출
has_negative_cycle = False
for u, v, weight in graph:
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
has_negative_cycle = True
break
return distances, has_negative_cycle
# 테스트 (음수 가중치 포함)
edges = [
(0, 1, 4), (0, 2, 1),
(1, 2, 2), (1, 3, 5),
(2, 3, -8), (3, 4, 2) # 음수 가중치
]
distances, has_cycle = bellman_ford(edges, 0, 5)
print("최단 거리:", distances)
print("음수 사이클 존재:", has_cycle)시간 O(V x E)로 다익스트라보다 느리지만, 음수 사이클 검출까지 해줍니다. V-1번 돌고 나서 한 번 더 돌려봐서 값이 또 줄어들면 음수 사이클이 있다는 뜻인데, 이 아이디어가 깔끔하다고 느꼈습니다.
플로이드-워셜 - 모든 쌍의 최단 경로
“A에서 B까지”가 아니라 “모든 정점 쌍 사이의 최단 거리”를 한 번에 구합니다.
def floyd_warshall(graph, num_vertices):
# 거리 행렬 복사
dist = [row[:] for row in graph]
# k: 경유할 수 있는 정점들
for k in range(num_vertices):
# i: 출발 정점
for i in range(num_vertices):
# j: 도착 정점
for j in range(num_vertices):
if (dist[i][k] != float('inf') and
dist[k][j] != float('inf') and
dist[i][k] + dist[k][j] < dist[i][j]):
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# 테스트
INF = float('inf')
graph = [
[0, 3, INF, 7],
[8, 0, 2, INF],
[5, INF, 0, 1],
[2, INF, INF, 0]
]
result = floyd_warshall(graph, 4)
print("모든 정점 쌍 최단 거리:")
for row in result:
print([x if x != INF else "INF" for x in row])3중 for문이라 O(V³)입니다. 정점 수가 적을 때(500 이하 정도) 쓸 수 있고, 코드가 짧아서 구현 실수가 적다는 게 장점입니다. 처음 봤을 때 “3중 루프인데 이게 맞아?” 싶었는데, k를 경유지로 하나씩 추가하면서 거리를 갱신한다는 아이디어를 이해하고 나니 납득이 됐습니다.
최소 신장 트리 (MST)
모든 정점을 연결하되 간선 비용의 합이 최소가 되게 하는 문제입니다. 네트워크 케이블을 최소 비용으로 깔려면 어떻게 해야 하나, 같은 상황을 생각하면 됩니다.
크루스칼 - 간선 정렬해서 하나씩
def kruskal_mst(edges, num_vertices):
# 간선을 비용 순으로 정렬
edges.sort()
parent = list(range(num_vertices))
rank = [0] * num_vertices
mst = []
total_weight = 0
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:
if rank[px] < rank[py]:
parent[px] = py
elif rank[px] > rank[py]:
parent[py] = px
else:
parent[py] = px
rank[px] += 1
for weight, u, v in edges:
if find(u) != find(v):
union(u, v)
mst.append((u, v, weight))
total_weight += weight
return mst, total_weight
# 테스트
edges = [
(7, 0, 1), (5, 0, 3), (8, 1, 2), (9, 1, 3),
(7, 1, 4), (5, 2, 4), (15, 3, 4), (6, 4, 5),
(8, 2, 5), (9, 3, 5), (11, 4, 5)
]
mst, weight = kruskal_mst(edges, 6)
print("최소 신장 트리:")
for u, v, w in mst:
print(f"간선 ({u}, {v}): 가중치 {w}")
print(f"총 가중치: {weight}")간선을 비용 순으로 정렬한 다음, 사이클이 안 생기는 간선만 하나씩 추가합니다. 사이클 판단은 Union-Find로 하는데, 이 자료구조를 여기서 처음 접했습니다. find 할 때 경로 압축을 하면 거의 O(1)에 가까워진다는 게 인상적이었습니다.
위상 정렬
방향 그래프에서 “선행 관계”를 지키면서 순서를 정하는 겁니다. 대학 수강 신청할 때 선수과목 있는 거랑 같은 개념입니다.
from collections import deque
def topological_sort(graph, num_vertices):
# 진입 차수 계산
in_degree = [0] * num_vertices
for neighbors in graph.values():
for neighbor in neighbors:
in_degree[neighbor] += 1
# 진입 차수가 0인 정점들을 큐에 삽입
queue = deque([i for i in range(num_vertices) if in_degree[i] == 0])
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
# 이웃 정점들의 진입 차수 감소
if vertex in graph:
for neighbor in graph[vertex]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 사이클 검출
if len(result) != num_vertices:
return None # 사이클 존재
return result
# 테스트 (과목 선수 지식 그래프)
graph = {
0: [1, 2], # 프로그래밍 → 알고리즘, 자료구조
1: [3], # 알고리즘 → 고급 알고리즘
2: [3], # 자료구조 → 고급 알고리즘
3: [], # 고급 알고리즘 (종료)
4: [0] # 수학 → 프로그래밍
}
order = topological_sort(graph, 5)
if order:
subjects = ["수학", "프로그래밍", "알고리즘", "자료구조", "고급알고리즘"]
print("학습 순서:")
for idx in order:
print(f"{idx+1}. {subjects[idx]}")
else:
print("사이클이 존재합니다!")진입 차수가 0인 정점(선행 조건이 없는 것)부터 처리하고, 처리할 때마다 연결된 정점의 진입 차수를 줄여나갑니다. 전부 처리했는데 남은 정점이 있으면 사이클이 있다는 뜻이고, 그러면 위상 정렬 자체가 불가능합니다.
실무에서는 빌드 시스템이나 패키지 의존성 해결에 이 로직이 들어가 있습니다. npm install 할 때 패키지 설치 순서를 정하는 것도 사실상 위상 정렬입니다.
어디에 쓰이나
공부할 때는 추상적으로 느껴지는데, 막상 보면 꽤 다양한 데서 씁니다.
- 네비게이션 길 찾기 (다익스트라)
- SNS 친구 추천 (BFS로 2촌, 3촌 탐색)
- 빌드 도구에서 컴파일 순서 결정 (위상 정렬)
- 게임에서 캐릭터 이동 경로 (A* 같은 변형이지만 기반은 그래프 탐색)
- 웹 크롤러가 페이지를 돌아다니는 것도 그래프 순회
연습 문제
- 다음 그래프에서 BFS와 DFS의 방문 순서를 각각 구하세요:
A ─ B ─ D
│ │
C ─ E-
다익스트라 알고리즘과 벨만-포드 알고리즘의 차이점을 설명하세요.
-
위상 정렬이 필요한 실무 사례를 2가지 이상 들어보세요.
-
최소 신장 트리가 필요한 경우는 언제인가요?
돌아보면
그래프 알고리즘은 처음에 종류가 많아서 압도당하기 쉬운데, 결국 패턴이 있습니다. “그냥 돌아다녀라”면 BFS/DFS, “최소 비용으로 가라”면 다익스트라 계열, “순서를 정해라”면 위상 정렬, “전부 연결하되 비용 최소”면 MST. 문제를 읽고 이 네 가지 중 어디에 해당하는지 판단하는 게 그래프 문제의 절반이었습니다.
그리고 그래프를 어떤 형태로 저장할지(인접 행렬 vs 인접 리스트)를 먼저 정하는 습관을 들이면 구현이 훨씬 수월해집니다. 대부분은 인접 리스트로 시작하면 됩니다.