그래프 2

그래프에서 본 저장 방법과 탐색을 바탕으로, 그래프(graph)라는 자료구조(data structure) 위에서 무엇을 구하는지를 이어서 다룬다. 간선(edge)마다 비용이 붙은 그래프의 최단 경로, 선후 관계를 지키는 작업 순서, 모든 정점(vertex)을 가장 싸게 잇는 방법을 차례로 본다.

다익스트라 알고리즘: 가중치 최단 경로

다익스트라 알고리즘(Dijkstra's algorithm)은 간선 가중치가 음수가 아닌 그래프에서, 한 출발 정점으로부터 다른 모든 정점까지의 최단 거리를 구한다.

1. 거리표를 만들어 출발점은 0, 나머지는 무한대로 둔다.
2. 아직 확정하지 않은 정점 중 거리가 가장 짧은 정점을 꺼내 확정한다.
3. 그 정점의 이웃마다 "이 정점을 거쳐 가는 거리"가 거리표보다 짧으면 거리표를 고친다.
4. 모든 정점이 확정될 때까지 2~3을 반복한다.

아래 그래프는 간선에 방향이 있는 방향 그래프(directed graph)이면서 가중치 그래프(weighted graph)다. 여기서 A로부터의 최단 거리를 구해 보자.

다이어그램 로딩…

단계	확정	A	B	C	D
시작	-	0	∞	∞	∞
1	A	0	4	1	∞
2	C	0	3 (1+2)	1	6 (1+5)
3	B	0	3	1	4 (3+1)
4	D	0	3	1	4

확정 열은 그 단계에서 가장 가까워 확정한 정점이고, 굵은 숫자는 그 정점의 최단 거리가 확정됐다는 뜻이다. A에서 B로 바로 가면 4지만 C를 거치면 3이라 더 짧다. 이렇게 "거쳐 가면 더 짧은지"를 매번 고치는 것이 3단계다.

2단계의 "가장 짧은 정점 꺼내기"를 우선순위 큐(priority queue)로 하면 빠르다. 매번 모든 정점을 훑어 최솟값을 찾지 않고, 가장 짧은 정점을 log V 시간에 바로 꺼낼 수 있기 때문이다. 이진 힙(binary heap)으로 만든 우선순위 큐를 쓰면 전체 시간 복잡도(time complexity)는 O((V + E) log V)다. 여기서 V는 정점 수, E는 간선 수이고, 빅오 표기법(Big-O notation)으로 적은 이 값은 입력이 커질 때 실행 시간이 늘어나는 정도를 나타낸다.

음수 간선이 있으면 다익스트라는 틀린 답을 낼 수 있다. 이 알고리즘은 "지금 가장 가까운 정점은 나중에 더 짧아질 수 없다"는 가정으로 정점을 확정하는데, 음수 간선이 있으면 이미 확정한 정점으로 가는 더 짧은 길이 뒤늦게 나타날 수 있기 때문이다. 음수 간선이 있으면 정점을 미리 확정하지 않고 모든 간선을 V − 1번 되풀이해 고치는 벨만-포드 알고리즘(Bellman-Ford algorithm)처럼, 더 느리지만 음수 간선을 다룰 수 있는 방법을 쓴다.

위상 정렬: 선후 관계대로 줄 세우기

위상 정렬(topological sort)은 모든 간선이 앞에서 뒤로 향하도록 정점을 한 줄로 늘어놓는 것이다. "선수 과목을 먼저 들어야 한다"거나 "이 모듈을 먼저 빌드해야 한다" 같은 작업 순서를 정할 때 쓴다. A가 B보다 먼저, B가 C보다 먼저, C가 다시 A보다 먼저여야 하는 식으로, 출발한 정점으로 되돌아오는 경로인 사이클(cycle)이 있으면 누구도 맨 앞에 설 수 없다. 그래서 위상 정렬은 DAG(Directed Acyclic Graph, 사이클 없는 방향 그래프)에서만 가능하다.

대표 방법은 들어오는 간선 수인 진입 차수(in-degree)가 0인 정점, 즉 먼저 할 일이 없는 정점부터 꺼내는 것이다. 진입 차수 0인 정점을 큐(queue)에 넣고, 꺼낼 때마다 그 정점에서 나가는 간선을 지워 이웃의 진입 차수를 줄인다. 새로 0이 된 정점을 다시 큐에 넣는다. 끝났는데 꺼내지 못한 정점이 남았다면 사이클이 있다는 뜻이다. 복잡도는 O(V + E)다. 같은 때에 진입 차수가 0인 정점이 여럿이면 어느 것을 먼저 꺼내도 되므로, 답은 하나가 아닐 수 있다.

최소 신장 트리

신장 트리(spanning tree)는 그래프의 모든 정점을 사이클 없이 잇는 간선 V − 1개의 모음이다. MST(Minimum Spanning Tree, 최소 신장 트리)는 간선에 방향이 없는 무방향 그래프(undirected graph)이면서 가중치가 붙은 그래프에서, 신장 트리 중 가중치 합이 가장 작은 것이다. 모든 도시를 가장 적은 비용의 케이블로 잇는 문제가 대표 예다.

• 크루스칼 알고리즘(Kruskal's algorithm): 간선을 가중치 순으로 정렬하고, 작은 것부터 사이클을 만들지 않는 간선만 고른다. 사이클 여부는 보통 유니온-파인드(union-find) 자료구조로 빠르게 확인한다. 정렬이 대부분이라 O(E log E)다.
• 프림 알고리즘(Prim's algorithm): 한 정점에서 시작해, 지금까지 만든 트리와 바깥 정점을 잇는 간선 중 가장 싼 것을 골라 트리를 한 정점씩 키운다. 우선순위 큐를 쓰면 O(E log V)다.

면접 포인트

• "다익스트라는 음수 간선에서 왜 안 되나요?" → 확정한 정점이 나중에 더 짧아질 수 있어 가정이 깨짐. 이진 힙으로 O((V+E) log V).
• "위상 정렬 조건은?" → 사이클 없는 방향 그래프. 진입 차수 0부터 꺼내기, 남으면 사이클.
• "크루스칼 vs 프림" → 간선 정렬 + 유니온-파인드 vs 정점에서 키워 가기 + 우선순위 큐.