신장 트리, 최소 신장 트리, Kruskal Algorithm

1.  신장 트리: 모든 node를 포함하면서 cycle이 존재하지 않는 그래프를 의미한다.

2. 최소 신장 트리: 신장 트리 중에서 최소 비용으로 만들 수 있는 트리

3. Kruskal Algorithm: 최소 신장 트리를 찾는 알고리즘

- O(vlogv)

- Greedy하게 최소 비용 edge부터 차례로 연결한다.

- 연결하고자 하는 node가 서로소였다면, union을 진행

- 연결하고자 하는 node가 cycle을만든다면, pass

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

def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

"""
Kruskal Algorithm
"""
# edges는 sort된 상태
for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result.append(edge)
        total_cost += cost