Kruskal's Algorithm with Python

지난 Python 강의 기록에서 작성했던 Kruskal's algorithm에 대해 더 작성해보고자 한다.

패스트캠퍼스 Python 코딩테스트 강의 4주차

 

Kruskal's algorithm은 대표적인 최소 신장 트리 알고리즘이다.

신장 트리, Spanning tree. : 그래프의 모든 노드가 연결되어 있으며 트리의 속성을 만족하는 그래프 1. 모든 노드를 포함해야 함 2. 모든 노드가 서로 연결 3. 트리의 속성을 만족 (사이클x)

당장 눈앞의 최소 비용을 선택하여 결과적으로 최적의 솔루션을 찾는 탐욕 알고리즘을 기초로 한다.

 

이 알고리즘은 크게 세 단계로 이루어진다.

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

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

3. 두 정점의 최상위 정점 확인, 서로 다를 경우 연결 (사이클이 생기지 않으면 연결)

 

위에 첨부한 글에서 이론적인 내용을 다루고 있으니, 코드 구현으로 넘어가 본다.

 

위와 같은 그래프가 있다고 가정할 때, 이를 코드로 표현하면

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

이와 같이 표현할 수 있겠다.

vertices로 어떤 정점이 있는지 리스트로 표현하고, edges로 간선을 표현한다.

 

kruskal(graph) 함수에는, 위에서 말했듯 

1. 노드 초기화

2. Weight 기반 Sorting

3. 사이클 없는 간선만 연결

이렇게 3단계를 구성할 것이다.

def kruskal(graph):
    mst = list()
    
    # 1. 초기화
    for node in graph['vertices']:
        make_set(node)
    
    # 2. Weight 기반 Sorting
    edges = graph['edges']
    edges.sort()
    
    # 3. 사이클 없는 간선만 연결
    for edge in edges:
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u):
            union(node_v, node_u)
            mst.append(edge)
    
    return mst

1단계에서 독립적인 집합으로 만들 때 parent 값과 rank 값을 초기화하면 되는데,

이를 위해 parent와 rank를 dictionary 데이터로 생성하여 각각 {node : parent}, {node : rank}로 저장할 수 있게 한다. ➡️ make_set(node)

2단계에서는 sorting 한다.

3단계에서는 edges의 각 edge의 parent를 비교하여 다르다면 union하는 과정을 한다. 그리고 union된 간선은 mst 리스트에 담는다.

find(node) 함수는 path compression 기법을 사용하는 함수로, 모든 노드들을 root에 다이렉트로 연결하는 기법을 사용한다.

path compression

그렇게 root 노드를 찾고, 다르다면 union(a, b)해준다.

union(a, b) 함수는 a와 b의 root 노드를 비교하여,

- rank가 큰 트리에 작은 트리를 연결하거나 

- rank가 같다면 한쪽 트리의 rank를 +1 시켜 연결한다.

 

Code

make_set(node), find(node), union(a, b)를 모두 구현한 전체 코드는 아래와 같다.

parent = dict() # {node : parent}
rank = dict() # {node : rank}

def find(node):
    # path compression 기법
    if parent[node] != node: # root가 아니다
        parent[node] = find(parent[node])
    return parent[node]

def union(node_v, node_u):
    root1 = find(node_v)
    root2 = find(node_u)
    
    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 기반 Sorting
    edges = graph['edges']
    edges.sort()
    
    # 3. 사이클 없는 간선만 연결
    for edge in edges:
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u):
            union(node_v, node_u)
            mst.append(edge)
    
    return mst

 

Result

kruskal(mygraph)하여 잘 구현되었는지 확인해본다.

 

Time Complexity

Kruskal's algorithm의 시간복잡도는 O(ElogE)이다.

1단계에서는 정점만큼의 시간 복잡도인 O(V) 이고,

2단계에서는 Sotring하기 위해 Quick sorting을 사용하다면 시간 복잡도가 O(ElogE) 이고,

3단계에서는 최상위 정점을 확인하고 연결할 때는 간선만큼의 시간 복잡도인 O(E) 가 된다.

결론적으로, Sorting 하는데에 소요되는 O(ElogE)가 시간 복잡도가 된다.