최소 신장 트리

1. 신장 트리란?

• Spanning Tree, 또는 신장 트리라고 부른다.
• 원래의 그래프의 모든 노드가 연결되어있으면서 트리의 속성을 만족하는 그래프
• 신장 트리의 조건
  • 본래의 그래프의 모든 노드를 포함해야함.
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킨다. ( 사이클이 존재하지 않는다. )

5. Union - Find 알고리즘

• Disjoint Set 를 표현할때 사용하는 알고리즘으로 트리구조를 활용하는 알고리즘
• 간단하게, 노드들중에 연결된 노드를 찾거나, 노드들을 서로 연결할때 사용
• Disjoint Set 란?
  • 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대해 정보를 저장하고 조작하는 자료구조
  • 공통원소가 없는 상호 배타적인 부분집합들로 나눠진 원소들에 대한 자료구조를 의미한다.
  • Disjoint Set = 서로소 집합 자료 구조

1. 초기화
   • n 개의 원소가 개별 집합으로 이뤄지도록 초기화
2. Union
   • 두 개별 집합을 하나의 집합으로 합침, 두 트리를 하나의 트리로 만듬
3. Find
   • 여러 노드가 존재할때, 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해, 각 그룹의 최상단 원소를 확인

Union-Find 알고리즘의 고려할점

• Union 순서에 따라서, 최악의 경우 링크드 리스트와같은 형태가 될 수 있음
• 이 때는 Find/Union 시 계산량이 O(n) 이 될 수 있으므로, 해당 문제를 해결하기 위해, union-by-rank, path compression 기법을 사용한다.

union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해두고

• Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙인다.

• 높이가 h-1 인 두개의 트리를 합칠때는 한쪽의 트리 높이 1을 증가시켜주고, 다른 쪽의 트리를 해당 트리에 붙여준다.

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

path compression

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• Find 를 실행한 노드는 이후부터 루트 노드를 한번에 알 수 있음

6. 크루스칼 알고리즘 코드 작성

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):
    # parent 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')]
 """

7. 시간복잡도

• 크루스컬 알고리즘의 시간복잡도는 O(ElogE)
  • 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨.(즉, 간선을 비용 기준으로 정렬하는 시간이 가장큼)
  • 모든 정점을 독립적인 집합으로 만든다.
  • 모든 간선을 비용을 시준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
    • 퀵소트를 사용한다면 시간 복잡도는 O(nlog n) 이고, 간선이 n 이므로 O(ElogE)
  • 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.( 최소 신장 트리는 사이클이 없으므로 사이클이 생기지 않게 한다.
    • union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움.