[Algorithm] Kruskal Algorithm (크루스칼 알고리즘)

1. Minimum Spanning Tree (MST)

 

MST란, 트리가 주어져 있을 때 모든 노드들이 연결되어 있으면서 가중치의 합이 최소인 spanning tree (tree의 일부분, 부분집합 개념으로 생각하면 된다) 이다. 단, 이는 cycle을 포함해서는 안된다. Spanning tree의 정의 자체가 cycle을 포함하지 않는 것이기 때문이다.

이를 찾아주는 알고리즘이 크루스칼 알고리즘이다.

 

2. 크루스칼 알고리즘

 

이는 union-find를 이용하여 MST를 찾아준다. union-find에 대한 글은 다음 링크를 참고하자. 

https://codinglilly.tistory.com/32

[Algorithm] Union-Find

 

처음에는 가중치의 값이 가장 작은 간선(edge)을 선택한다. 이후 가중치의 값이 작은 순서대로 선택하되, 선택할 때마다 union 연산을 수행한다. 단, union 이전에 find 연산을 수행하여 cycle이 있는지 확인한다.

만약 cycle이 발생하게 된다면, 두 노드는 같은 조상을 갖고 있을 것이다. 따라서 조상이 같을 경우에는 연산을 수행하지 않고 넘어간다. 이 과정을 통해 가중치가 작은 간선들을 선택하게 되면, MST를 만들 수 있다. 

 

2. 구현

 

n = int(input())
graph = []
edges = []

for i in range(n):
    graph.append(input().split())
for i in range(n):
    for j in range(n):
        graph[i][j] = int(graph[i][j])
        if(graph[i][j] != 0):
            edges.append([i, j, graph[i][j]])

mst = []
uf = [-1 for _ in range(n)]
def find(uf, x):
    if uf[x] == -1:
        return x
    tmp = find(uf, uf[x])
    uf[x] = tmp
    return uf[x]

def union(uf, x, y):
    X, Y = find(uf, x), find(uf, y)
    uf[X] = Y
    return uf

edges.sort(key=lambda x:x[2])
res = 0
max_cost = 0

for edge in edges:
    start, end, cost = edge[0], edge[1], edge[2]
    if find(uf, start) != find(uf, end):
        uf = union(uf, start, end)
        mst.append((start, end))
        res += cost

print(mst, res)