개념
크루스컬 알고리즘은 대표적인 최소 신장 트리 알고리즘입니다. 최소 신장 트리란 그래프가 주어져 있을 때 모든 노드들을 포함하고 있으며 사이클이 존재하지 않는 무방향 그래프를 의미합니다. 즉 모든 노드가 연결이 되어있어야 한다는 점과 사이클이 존재하지 않는다는 조건의 교집합이라고 할 수 있습니다. 다음 그림을 보겠습니다. (그림은 나동빈 님의 이것이 취업을 위한 코딩 테스트이다. 를 참고하였습니다.)
위 그림의 경우 모든 노드들은 연결이 되어있고 사이클이 존재하지 않으므로 신장 트리 입니다. 간선의 개수는 노드의 개수 -1 인 것을 확인할 수 있습니다. 크루스컬 알고리즘은 가능한 신장 트리 중 가장 최소의 비용으로 신장 트리를 연결하는 알고리즘입니다. 과정은 다음과 같습니다.
1. 모든 간선 정보를 따로 리스트에 저장한다.
2. 리스트에 저장된 간선 정보를 cost가 작은순으로 정렬한 후 사이클의 존재 유무를 파악한다.
3. 사이클이 아닐경우 두 노드를 연결한다.
4. 사이클일 경우 넘어간다.
소스코드
|
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
|
def find_parent(parent, x):
if parent[x] != x:
parent[x] = 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:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (1 + v)
for i in range(1, 1 + v):
parent[i] = i
result = 0
edges = []
for i 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_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 벨만 포드 알고리즘 (0) | 2021.03.01 |
|---|---|
| 사이클 판별 알고리즘 (Python (0) | 2020.12.31 |
| 서로소 집합 알고리즘 (Python) (0) | 2020.12.30 |
| 다익스트라 알고리즘 (Python) (0) | 2020.12.22 |
| 편집거리 알고리즘 (Python) (0) | 2020.12.22 |