크루스칼 알고리즘(Kruskal's algorithm)

1. 신장 트리(Spanning Tree)의 조건
  - 주어진 그래프의 모든 노드를 연결해야 한다
  - 단, 노드를 연결할 때 사이클이 생겨선 안 된다

2. 최소 신장 트리 MST(Minimum Spanning Tree)
  - 최소 비용(간선 가중치의 합이 최소)의 Spanning Tree

3. 크루스칼 알고리즘(Kruskal's algorithm)
  - 간선의 비용을 기준으로 오름차순 정렬하여 비교할 노드를 선정
  - 두 노드씩 최상위 노드를 탐색한 후, 서로 다를 경우 노드를 연결하는 알고리즘
    - 부모 노드가 서로 다르다는 것은 연결해도 사이클이 발생하지 않는다는 것을 의미함
  * 유니온-파인드(Union-Find) 알고리즘 활용

4. 시간 복잡도: O(E log E)

def find(node):
    # path compression
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

def union(node_x, node_y):
    root1 = find(node_x)
    root2 = find(node_y)

    # union-by-rank 기법
    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2

        if rank[root1] == rank[root2]:
            rank[root2] += 1

def make_set(node):
    parent[node] = node
    rank[node] = 0

def kruskal(graph):
    mst = list()
    
    # 1. 초기화: 각 노드 개별 집합화
    for node in graph['vertices']:
        make_set(node)
    
    # 2. 간선 weight based sorting
    edges = graph['edges']
    edges.sort()

    # 3. 간선 연결 (사이클이 안 되는 것끼리)
    for edge in edges:
        weight, node_x, node_y = edge
        if find(node_x) != find(node_y):
            union(node_x, node_y)
            mst.append(edge)
    return mst

parent = dict()
rank = dict()

mygraph = {
    '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')
    ]
}

print(kruskal(mygraph))

""" MST(최소 신장 트리)
    [(5, 'A', 'D'), 
     (5, 'C', 'E'), 
     (6, 'D', 'F'), 
     (7, 'A', 'B'), 
     (7, 'B', 'E'), 
     (9, 'E', 'G')]
"""

- 출처: FASTCAMPUS