Python으로 알고리즘 공부 12. 최소 신장 트리 - Kruskal 알고리즘

최소 신장 트리 (Minimum Spanning Tree)

최소신장트리?

• 신장트리란, 사이클을 형성하지 않고 그래프의 모든 정점(V)이 간선(E)으로 연결되어 있는 것

• 최소신장트리란 최소한의 비용으로 신장트리를 형성하는 것

Kruskal's Algorithm

• 모든 정점을 독립적인 집합으로 만든다.

• 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.

• 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.

• 시간 복잡도는 ​

Python Code

parent = {}
rank = {}
​
# 정점을 독립적인 집합으로 만든다.
def make_set(v):
    parent[v] = v
    rank[v] = 0
​
# 해당 정점의 최상위 정점을 찾는다.
def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])
        
    return parent[v]
​
# 두 정점을 연결한다.
def union(v, u):
    root1 = find(v)
    root2 = find(u)
    
    if root1 != root2:
        # 짧은 트리의 루트가 긴 트리의 루트를 가리키게 만드는 것이 좋다.
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            
            if rank[root1] == rank[root2]:
                rank[root2] += 1
​
def kruskal(graph):    
    for v in graph['vertices']:
        make_set(v)
    
    mst = []
    
    edges = graph['edges']
    edges.sort()
    
    for edge in edges:
        weight, v, u = edge
                
        if find(v) != find(u):
            union(v, u)
            mst.append(edge)
    
    return mst
            
​
​
graph = {
'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'),
    (15, '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(graph) )

결과

[(5, 'A', 'D'),
 (5, 'C', 'E'),
 (6, 'D', 'F'),
 (7, 'A', 'B'),
 (7, 'B', 'E'),
 (9, 'E', 'G')]

참조

• https://gist.github.com/msAzhar/b51d7dc21c939c53209d5a2dda3fc8ad