신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘
이 있다.
크루스칼 알고리즘
을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.
크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다.
그리디 알고리즘으로 분류된다.
신장 트리
란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.트리
의 성립 조건이기도 함.크루스칼 알고리즘
은 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘이다. 아래 그림을 통해 최소 신장 트리를 알아보자.
왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선(23+13)으로 이루어진 신장 트리가 최소 신장 트리
가 된다!
즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리가 최소 신장 트리
가 된다.
크루스칼 알고리즘의 구체적인 동작 과정은 아래와 같다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
① 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
② 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. (X)- 모든 간선에 대하여 2번의 과정을 반복한다.
아래 그림을 통해 이해해보자.
[step 0] 그래프의 모든 간선 정보만 따로 빼내어 정렬을 수행한다.
(원래는 비용을 기준으로 오름차순 정렬을 한다.--> 최소한의 비용으로 MST를 만들기 위해서이다.)
[step 1] 비용이 가장 최소인 (3, 4)를 선택한 후 3번 노드와 4번 노드에 대하여 union 함수를 수행한다.
[step 2] 방문하지 않은 간선들 중에서 가장 최소인 (4, 7)을 선택하여 처리한다.
[step 3] 방문하지 않은 간선들 중에서 가장 최소인 (4, 6)을 선택하여 처리한다.
[step 4] 방문하지 않은 간선들 중에서 가장 최소인 (6, 7)을 선택하여 처리한다. 하지만 (6, 7)을 방문할 경우(연결할 경우(=union() 함수)) 사이클이 발생하므로 (6, 7) 간선을 연결하지 않는다.
[step 5] 방문하지 않은 간선들 중에서 가장 최소인 (1, 2)을 선택하여 처리한다.
[step 6] 방문하지 않은 간선들 중에서 가장 최소인 (2, 6)을 선택하여 처리한다.
[step 7] 방문하지 않은 간선들 중에서 가장 최소인 (2, 3)을 선택하여 처리한다. 하지만, (2, 3)을 연결할 경우에도 사이클이 발생하므로 연결하지 않는다.
[step 8] 방문하지 않은 간선들 중에서 가장 최소인 (5, 6)을 선택하여 처리한다.
[step 9] 방문하지 않은 간선들 중에서 가장 최소인 (1, 5)을 선택하여 처리한다. 마찬가지로 (1, 5)를 연결하면 사이클이 발생하므로 연결하지 않는다.
[최종 결과]
또한, 최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다. 위 예시에서는 총 비용이 159이다.
사진 출처 : 링크
크루스칼 알고리즘을 코드로 구현할 때, 앞서 배운 union-find 알고리즘
을 이용하여 구현한다!
# 특정 원소가 속한 집합을 찾기
def find(parent, x):
if parent[x] == x:
return x
parent[x] = find(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기 (간선 연결한다고 생각!)
def union(parent, a, b):
rootA = find(parent, a)
rootB = find(parent, b)
if rootA < rootB:
parent[rootB] = rootA
else:
parent[rootA] = rootB
import sys
input = sys.stdin.readline
# 노드의 개수와 간선(union 연산)의 개수 입력받기
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, a) != find(parent, b):
union(parent, a, b)
result += cost
print(result)
# sample input
# 7 9
# 1 2 29
# 1 6 75
# 2 3 35
# 2 6 34
# 3 4 7
# 4 6 23
# 4 7 13
# 5 6 53
# 6 7 25
O(ElogE)
E
개일 때, O(ElogE)
의 시간 복잡도를 가진다. 왜냐하면 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이며, E
개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)
이기 때문이다. --> (Python에서 .sort()
함수는 퀵 정렬을 기본으로 하며 퀵 정렬의 시간 복잡도는 O(NlogN)
이다!)This is the first time I've encountered the Kruskal Algorithm, and I'm totally intrigued by its approach to finding a minimum pokedoku spanning tree, particularly its classification as a greedy algorithm.
Hi ! I need to install ispmanager snaptik Linux but I can't figure out how , who can help me ?
덕분에 이해했습니다. 좋은 글 감사합니다 😀