MST (Minimum Spanning Tree)

• 모든 정점을 포함하는, 사이클이 없는 그래프
• Minimum Spanning Tree is tree that acycle and all vertex is visited.
• MST is tree, but MST doesn’t have to be a binary tree. Thus, MST’s parent nodes may have two or more child nodes, unlike the binary tree.

Kruskal’s Algorithm

• 크루스칼 알고리즘은 prim, 다익스트라와는 다르게 정점을 다루지 않고, 간선만을 다루는 알고리즘임
• prim, 다익스트라는 정점에서 다음 정점을 탐색하기 때문에 인접 행렬, 인접 리스트가 필요함

Kruskal’s Algorithm 작동

1. Kruskal’s Algorithm에서는 간선을 선택하기 때문에, 간선의 가중치를 중심으로 오름차순으로 정렬
2. 간선을 선택하면 두 정점을 선택하게 되고, 두 정점이 서로소인지 확인하기 위해 Union-Find 자료구조를 이용함 - Union-Find를 이용해서 사이클이 생기는지를 판단하게 됨. 사이클을 방지
3. 선택된 간선이 n-1개가 될 때까지 반복, (정점의 개수가 n개라면, MST의 간선의 개수는 n-1이기 때문)

• 시간 복잡도 : O(E logE) (E : 간선의 개수)
  • 간선 정렬 : O(E logE)
  • Union-Find 연산 : 거의 O(1)

Union-Find 연산

원본 집합 A = {1, 2, 3, 4, 5}가 있음 집합 A를 집합 B, C로 분리하고 싶음 이때, B와 C의 교집합이 없어야함. (즉, A의 원소가 B와 C중 둘 중 하나에만 속해야함)

Union-Find연산은 Kruskal’s Algorithm에서 사이클이 생기는지 검사하는데 쓰임 → Kruskal’s Algorithm은 하나의 간선을 선택하는데, 하나의 간선을 선택하면 두 개의 정점을 선택하게 됨. 이때, 선택된 두 정점이 서로소인 경우 : 사이클이 생기지 않음. 서로소가 아닌 경우 : 사이클이 생기는 경우임.