[알고리즘] 최소 신장트리 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)

Spanning Tree란 (최소 연결 부분 그래프)(신장트리)

신장트리

• 그래프 내의 모든 정점을 연결하되 사이클이 없는 그래프를 의미한다.
• 최소 연결이라는 것은  간선의 수가 가장 적다라는 것이다.
• n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.
  
  

따라서 모든 노드를 포함한 것이 서로 연결되어있어야하고 사이클이 존재하지 않는 것이다.

 

Minimum Spanning Tree(최소 신장 트리)

- MST 라고 불리고 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다.

- 가장 가중치가 낮은 간선부터 선택을 하여 사이클이 없도록 만들면 된다.

 

대표적인 최소 신장 트리 알고리즘

• Kruskal’s algorithm (크루스칼 알고리즘)
• Prim's algorithm (프림 알고리즘)

 

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

탐욕 알고리즘을 기초로하는 것이다.

1. 모든 정점을 독립적인 집합으로 만든다.
2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)

 

---

이 알고리즘을 코드로 작성하기 위한 선행지식 

- 사이클이 생기는지 안생기는지 알 수 있는 알고리즘이다.

Union-Find 알고리즘

• Disjoint Set(서로 중복되지 않는 부분 집합)을 표현할 때 사용하는 알고리즘
• 간단하게, 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 (합칠 때) 사용

Union - 트리 합치기.

두 개별 집합을 하나의 집합으로 합침, 두 트리를 하나의 트리로 만듬

 

 

 

Find - 사이클 여부 확인

여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해, 각 그룹의 최상단 원소 (즉, 루트 노드)를 확인

 

트리가 링크드 리스트와 같은 형태가 되는 경우에는 Find/Union시 계산량이 O(N)이 될 수 있으므로 union-by-rank, path compression 기법을 사용

 

union-by-rank 기법

union-by-rank

2개의 부분집합이 합쳐질때 어떻게 높이를 작게 하느냐에 해당하는 기법이다.

Union시 랭크값에 해당하는 것이 저장된다.

• Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함)
• 높이가 h - 1 인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시켜주고, 다른 쪽의 트리를 해당 트리에 붙여줌

따라서 union-by-rank 기법을 사용하면, union/find 연산의 시간복잡도는 O(N) 이 아닌, O(logN) 로 낮출 수 있음

 

path compression

path compression

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법

얻을 수 있는 것 :  Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있음

 

 

최소신장트리

 

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

parent = dict()
rank = dict()


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


def union(node_v, node_u):
    root1 = find(node_v)
    root2 = find(node_u)
    
    # 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 기반 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
    
    
    
kruskal(mygraph)

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

 

시간복잡도

시간복잡도

이기에 O(ElogE)이다.