[python] 크루스칼알고리즘(최소신장트리)

 

1. 특정 노드의 parent를 찾기

노드 x의 부모가 x가 아니라면, 노드x 의 부모를 거슬러 올라가 루트노드까지 찾아 반환해준다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    
    return parent[x]

 

2. 노드들의 부모를 찾아 서로 연결해주기

각각 a와 b의 부모를 찾아서 부모노드 번호 순으로 연결해준다.

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

 

3.  2개의 노드가 연결되어있지 않으면 부모찾아서 연결해주기

(단, edges그래프를 낮은비용부터정렬)

for edge in edges:
    cost, a,b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost