issues
search
WonYong-Jang
/
algorithm
0
stars
0
forks
source link
크루스칼 알고리즘 - 최소 신장 트리(Minimum Spanning Tree / MST ) // Using 서로소 집합 ( Disjoint Set, Union-Find)
#16
Open
WonYong-Jang
opened
6 years ago
WonYong-Jang
commented
6 years ago
신장 트리 (스패닝 트리, Spanning Tree) 란?
그래프의 모든 정점이 간선으로 연결되어 있다.
그래프 안에 사이클이 포함되어 있지 않다.
최소 신장트리 (최소 스패닝 트리, Minimum Spanning Tree) 란?
최소 비용으로 만들어진 신장 트리, 가중치 합이 가장 작은 신장 트리
크루스칼 알고리즘
시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하여 mst를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야 함. 사이클 확인 방법으로 Union-Find(Disjoint-Set) 방법
O(E logE)
WonYong-Jang
commented
6 years ago
서로소 집합( Disjoint Set, Union-Find)
1차원 배열로 집합을 표현
초기화 : Parent[i] = i 와 같이 각 원소는 자기 자신을 대표하는 번호로 하는 집합에 속해 있다.
책 그림 확인
WonYong-Jang
commented
4 years ago
Union-Find 응용문제
leetcode 1202 Smallest String with swaps
아래 자료 구조 사용해볼 것 HashMap<Integer, PriorityQueue
> map = new HashMap<>();
신장 트리 (스패닝 트리, Spanning Tree) 란?
최소 신장트리 (최소 스패닝 트리, Minimum Spanning Tree) 란?
크루스칼 알고리즘