크루스칼 알고리즘 - 최소 신장 트리(Minimum Spanning Tree / MST ) // Using 서로소 집합 ( Disjoint Set, Union-Find)

[WonYong-Jang]

신장 트리 (스패닝 트리, Spanning Tree) 란?

• 그래프의 모든 정점이 간선으로 연결되어 있다.
• 그래프 안에 사이클이 포함되어 있지 않다.

최소 신장트리 (최소 스패닝 트리, Minimum Spanning Tree) 란?

• 최소 비용으로 만들어진 신장 트리, 가중치 합이 가장 작은 신장 트리

크루스칼 알고리즘

• 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하여 mst를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야 함. 사이클 확인 방법으로 Union-Find(Disjoint-Set) 방법
• O(E logE)

[WonYong-Jang]

서로소 집합( Disjoint Set, Union-Find)

• 1차원 배열로 집합을 표현
• 초기화 : Parent[i] = i 와 같이 각 원소는 자기 자신을 대표하는 번호로 하는 집합에 속해 있다.

책 그림 확인

[WonYong-Jang]

Union-Find 응용문제

• leetcode 1202 Smallest String with swaps
• 아래 자료 구조 사용해볼 것
  HashMap<Integer, PriorityQueue> map = new HashMap<>();