가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘, 최소 비용 신장 트리(Minimum Spanning Tree)를 만들기 위한 대표적인 알고리즘이다. 흔히 여러 개의 도시가 있을 대, 각 도시를 도로를 이용해 최소한의 비용으로 연결하고자 할 때 적용된다.
핵심 개념은 "간선을 거리가 짧은 순서대로 그래프에 포함"시키는 것이다. 즉, 모든 노드들을 최대한 적은 비용으로 '연결'만 시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 그래프에 포함시킨다.
주의할 점은 "사이클"이 만들어지면 안된다는 점이다. 이것은 노드가 같은 최상위 정점을 갖는지 확인하면 된다.
1. 정렬된 순서에 맞게 노드를 그래프에 포함시킨다.
2. 포함시키기 전에는 사이클 테이블을 확인한다.
3. 사이클을 형성하는 경우 간선을 포함하지 않는다.
parent = dict()
rank = dict()
#vertice 초기화
def make_set(vertice):
parent[vertice] = vertice
rank[vertice] = 0
#해당 vertice의 최상위 정점을 찾는다
def find(vertice):
if parent[vertice] != vertice:
parent[vertice] = find(parent[vertice])
return parent[vertice]
#두 정점을 연결한다
def union(vertice1, vertice2):
root1 = find(vertice1)
root2 = find(vertice2)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
def kruskal(graph):
minimum_spanning_tree = []
#초기화
for vertice in graph['vertices']:
make_set(vertice)
#간선 weight 기반 sorting
edges = graph['edges']
edges.sort()
#간선 연결 (사이클 없게)
for edge in edges:
weight, vertice1, vertice2 = edge
if find(vertice1) != find(vertice2):
union(vertice1, vertice2)
minimum_spanning_tree.append(edge)
return minimum_spanning_tree
graph = {
'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
'edges': [
(7, 'A', 'B'),
(5, 'A', 'D'),
(7, 'B', 'A'),
(8, 'B', 'C'),
(9, 'B', 'D'),
(7, 'B', 'E'),
(8, 'C', 'B'),
(5, 'C', 'E'),
(5, 'D', 'A'),
(9, 'D', 'B'),
(7, 'D', 'E'),
(6, 'D', 'F'),
(7, 'E', 'B'),
(5, 'E', 'C'),
(7, 'E', 'D'),
(8, 'E', 'F'),
(9, 'E', 'G'),
(6, 'F', 'D'),
(8, 'F', 'E'),
(11, 'F', 'G'),
(9, 'G', 'E'),
(11, 'G', 'F')
]
}