신장 트리(Spanning Tree)
신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리의 성립 조건이기도 하다.
신장 트리가 아닌 부분 그래프 예시를 보면 1번 노드가 포함되지 않았고 467번 노드에서 사이클이 발생하기 때문에 신장 트리가 아니다.
크루스칼 알고리즘
다양한 문제 상황 속에서는 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 수 있다. 가령 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 이는 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 설치한다는 것과 같은 의미다. 즉, 경유를 하던지 아니면 직선거리로 연결되어 있던지 A에서 B로 반드시 갈 수 있다는 것이다.
신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾기 위한 알고리즘 중 가장 대표적인 것이 크루스칼 알고리즘이다. 그리디 알고리즘의 일종으로 구체적인 동작 과정은 아래와 같다.
- 간선 데이터를 비용에 따라 오름차순 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않으면 최소 신장 트리에 포함시킴
- 사이클이 발생하면 최소 신장 트리에 포함시키지 않음
- 모든 간선에 대해 2번의 과정을 반복
최소 신장 트리는 일종의 트리 자료구조이므로 최종적으로 신장트리에 포함되는 간선의 개수가 노드의 개수 - 1과 같다는 특징이 있다.
따라서 크루스칼 알고리즘의 핵심 원리는 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다는 것이다. 다만, 사이클을 발생시키는 간선은 제외하고 연결한다. 이렇게하면 항상 최적의 해를 보장할 수 있다. 이를 코드로 구현하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[z] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parnet[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블 상에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
# 간선을 비용순 정렬
edges.sort()
# 간선을 하나씩 확인
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parnet(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
크루스칼 알고리즘의 시간복잡도는 간선의 개수가 E개 일때 O(ElogE)의 시간 복잡도를 가진다. 왜냐면 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이며 E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)이기 때문이다.
위상 정렬
위상정렬은 이름대로 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행할 때 사용가능하다. 이를 좀더 이론적으로 설명하면 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이 위상정렬이라고 할 수 있다.
현실 세계에서 위상 정렬을 수행하게 되는 전형적인 예시로는 선수과목을 고려한 학습 순서 설정을 들 수 있다. 가령 컴공과 커리큘럼에서는 자료구조 과목을 수강한 뒤 알고리즘 강의를 수강하는 것을 권장한다고 하자. 이때 자료구조 및 알고리즘은 각각 노드로 표현가능하고 자료구조에서 알고리즘으로 이어질 수 있는 방향성을 갖는 간선을 그릴 수 있다. 즉, 그래프 상에서 선후관계가 명확하다면 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산 가능하다.
위상 정렬 알고리즘을 알아보기 전 진입차수와 진출차수라는 개념을 먼저 알아야한다. 진입차수(Indegree)는 특정한 노드로 들어오는 간선의 개수이고 진출차수(Outdegree)는 특정한 노드에서 나가는 간선의 개수이다.
앞선 예제를 보면 고급 알고리즘은 자료구조와 알고리즘이라는 두 개의 선수과목을 가지고 있다. 다시말해 그래프상에서 진입차수가 2인 것이다. 알고리즘은 자료구조라는 선수과목을 가지고 있기 때문에 진입차수가 1이며 알고리즘을 수강한 뒤 고급 알고리즘 과목을 수강할 수 있기 때문에 진출차수도 1이 된다.
큐를 이용하는 위상 정렬 알고리즘의 동작과정은 아래와 같다.
- 집입차수가 0인 모든 노드를 큐에 넣는다
- 큐가 빌 때까지 다음의 과정을 반복한다
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
- 새롭게 진입차수가 0이된 노드를 큐에 넣는다
단 한가지 주의해야할 건 위상 정렬을 수행할 그래프는 사이클이 없는 방향그래프(DAG)여야 한다. 만약 사이클이 존재한다면 그 사이클에 포함되어 있는 모든 노드는 진입차수가 1이상이 된다. 따라서 지금과 같이 알고리즘을 설계한 경우 사이클에 포함된 모든 노드는 큐에 들어갈 수 없기 때문에 위상정렬을 수행할 수 없다. 위의 과정을 거치면 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.
이 모든 내용들을 코드로 구현하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from collections import deque
# 노드의 개수와 간선의 개수 입력
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수를 0으로 초기화
indegree = [0] * (v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v+1)]
# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 정점 A에서 B로 이동 가능
# 진입 차수 1 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상정렬을 수행한 결과 출력
for i in result:
print(i, end=' ')
ropology_sort()
앞에서 언급했지만 위상 정렬은 DAG에 대해서만 수행 가능하다. 또한 위상 정렬은 여러가지 답이 존재할 수 있다. 가령 한 단계에서 큐에 새롭게 들어가는 원소가 두개 이상은 경우라면 여러가지 답이 존재하게 된다.
만약 모든 원소를 방문하기 전에 큐가 빈다면 이는 사이클이 존재한다고 판단할 수 있다. 사이클에 포함된 원소는 큐에 들어갈 수 없기 때문이다. 추가로 스택을 활용한 DFS를 이용하여 위상정렬을 수행할 수도 있다.
위상 정렬은 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거하기 때문에 위상 정렬 알고리즘의 시간 복잡도는 O(V+E)이다.