[코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리

# 신장 트리 (Spanning Tree)

그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프

모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음

# 최소 신장 트리 (Minimum Spanning Tree, MST)

가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree

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

 

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

가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 )

 

# Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘

Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘

Disjoint Set :서로 중복되지 않는  부분집합

다음 간선이 연결하는 두 노드가 같은 집합에 있으면 사이클 발생 ( 각 집합의 루트 노드 비교)

 

# union-by-rank 기법

각 트리의 높이(rank)를 기억해두고 union시 높이가 다르면 높이가 작은 트리를 높이가 큰 트리에 붙임

높이가 동일하다면 한쪽의 트리를 1 증가시켜주고 다른 쪽의 트리를 붙여줌

높이가 n인 트리가 만들어지려면 높이가 h-1인 트리 2개 필요

높이가 h-1인 트리를 만들기 위해 n개의 원소가 필요하다면, 높이가 h인 트리를 만들기 위해서는 2n개 필요

-> union/find의 시간복잡도  O(logN)

 

#path compression

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() # 해당 노드의 rank값 저장


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

# 크루스칼 알고리즘 시간복잡도

O(ElogE) (E는 간선의 수)

모든 정점을 독립적인 집합으로 만든다 O(V)

모든 간선을 비용 기준 정렬, 양 끝의 두 정점 비교 O(ElogE)

두 정점의 최상위 정점 확인, 서로 다르면 연결 O(E)