크루스칼

신장트리

• 원래의 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프
• Spanning Tree로 불리기도 한다.
• 신장 트리의 조건
  • 본래의 그래프의 모든 노드를 포함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족 (사이클이 존재X)

최소 신장 트리

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

최소 신장 트리 알고리즘

• 그래프에서 최소 신장 트리를 찾는 알고리즘
• 크루스칼 알고리즘, 프림 알고리즘이 존재

크루스칼 알고리즘

• 모든 정점을 독립적인 집합으로 만든다.
• 모든 간선을 비용을 기준으로 정렬, 작은 간선 부터 양 끝의 두 정점을 비교
• 두 정점의 최상위 정점을 확인, 다를 경우 연결 (사이클이 생기지 않도록)

Union- find

• 크루스칼 알고리즘의 사이클 생성 방지를 위한 알고리즘

• 각 노드를 개별 집합으로 초기화 한 후에 합치고 찾는 자료구조

• Disjoint Set (서로소 집합)

• Union : 두 개별 집합을 하나의 집합으로 합침 (두 트리를 하나의 트리로)

• Find : 찾는 노드가 같은 그래프에 속하는지 판별하기 위해 루트노드를 확인

• 최악의 경우 링크드 리스트형태가 나오므로 union-by-rank를 이용해 최적화

  • O(N)을 O(logN)으로 낮출 수 있다.

union-by-rank

• 각 트리에 높이 (rank)를 저장
• Union 시에 트리의 높이가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임

• 높이가 같다면, 아무 한쪽의 높이를 높이고, 남은 한쪽을 붙인다.

높이가 0인 상태에서, union-by-rank를 사용한다면

높이가 h인 트리가 만들어지려면, 높이가 h-1 인 두 개의 트리가 합쳐져야 한다.

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

path compression

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결
• 이후 루트 노드를 한번에 알 수 있다.
• union-by-rank 와 path compression 기법을 사용시 O(1)에 가까운 시간복잡도를 갖는다.

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