크루스칼(Kruskal) 알고리즘 이론과 파이썬 구현

 크루스칼(Kruskal) 알고리즘 

크루스칼(Kruskal) 알고리즘은 간선들을 가중치가 증가하는 순서로 정렬하고 가중치가 가장 작은 간선이 사이클을 만들지 않으면 트리 간선으로 선택합니다. 다음 가중치에서도 사이클을 만들지 않으면 트리 간선으로 선택하고 이 과정을 반복해서 정점-1개의 간선을 선택하는 알고리즘입니다.

 

크루스칼 알고리즘은 최소신장트리(무방향 가중치 그래프에서 간선의 가중치 합이 최소인 것)를 찾는 알고리즘입니다.

 

크루스칼 알고리즘은 항상 욕심내서 최솟값을 선택하여 가중치의 합이 최소인 것을 찾기 때문에 그리디 알고리즘이라고 할 수 있습니다.

 

크루스칼 알고리즘에서 간선이 사이클을 만드는지는 union연산과 find연산을 사용합니다. 이는 Union-Find 알고리즘이라고도 부르고 서로소 집합 알고리즘이라고도 합니다. 이 알고리즘은 여러 노드가 존재할 때 두 개의 노드를 선택해 루트를 확인하고 현재 서로 같은 그래프에 속하는지 판별합니다.

상호 배타적 집합들은 1차원 리스트로 표현하며 루트의 리스트 원소에는 루트 자신이 저장되고 루트가 아닌 노드의 원소에는 부모 노드가 저장됩니다. union은 두 개의 집합을 하나의 집합으로 합치는 연산입니다. find는 find연산을 수행하면서 루트까지 올라가는 경로 상의 각 노드의 부모 노드를 루트로 갱신합니다. 이를 경로 압축이라 하는데 이를 실행하면서 수행 시간을 단축시켜 줄 수 있습니다.

 

find 연산 경로압축

find(1)이 수행되면서 1, 3, 7, 10을 거쳤는데 각 노드의 부모노드를 루트로 갱신했습니다.

 

다음은 크루스칼 알고리즘으로 최소신장트리를 찾는 과정입니다.

 

 

크루스칼 알고리즘에서 최소신장트리를 찾기 위해서는 먼저 그래프의 가중치를 기준으로 오름차순으로 정렬합니다.

그리고 가중치에 따른 간선들이 싸이클을 형성하는지 하나씩 확인합니다.

 

정점 4와 5를 이어주는 첫번째 간선을 선택합니다.

정점 5와 6을 이어주는 두번째 간선을 선택합니다.

 

정점 3와 5를 이어주는 세 번째 간선을 선택합니다.

정점 1와 3을 이어주는 네 번째 간선을 선택합니다.

 

정점 4와 6을 선택할 경우 정점 4, 5, 6이 사이클을 형성하기 때문에 선택하지 않습니다.

정점 2와 4을 이어주는 여섯 번째 간선을 선택합니다.

이를 통해 모든 정점이 연결되어 최소신장트리를 이룹니다.

간서의 가중치의 값은 1 + 2 + 3 + 5 + 9 = 20입니다.

 

크루스칼 알고리즘의 파이썬 코드입니다.

graph=[(1,2,13),(1,3,5),(2,4,9),(3,4,15),(3,5,3),(4,5,1),(4,6,7),(5,6,2)]
graph.sort(key = lambda x: x[2]) # 가중치로 간선 정렬 (정점1, 정점2, 가중치)

mst=[]
n=6 # 정점 개수
p=[0] # 상호배타적 집합

for i in range(1,n+1):
    p.append(i) # 각 정점 자신이 집합의 대표

def find(u):
    if u != p[u]:
        p[u] = find(p[u]) # 경로압축
    return p[u]

def union(u, v):
    root1 = find(u)
    root2 = find(v)
    p[root2] = root1 # 임의로 root2가 root1의 부모

tree_edges = 0 # 간선 개수
mst_cost = 0 # 가중치 합

while True:
    if tree_edges == n-1:
        break
    u, v, wt =graph.pop(0)
    if find(u) != find(v): # u와 v가 서로 다른 집합에 속해 있으면
        union(u, v)
        mst.append((u, v)) 
        mst_cost += wt
        tree_edges += 1

# 출력>>최소신장트리:  [(4, 5), (5, 6), (3, 5), (1, 3), (2, 4)]
print('최소신장트리: ',mst)

# 출력>>최소신장트리 가중치: 20
print('최소신장트리 가중치:', mst_cost)