Kruskal Algorithm

Kruskal

• 간선을 중심으로 생각한다
• 이전 상태와는 관계없이 제일 가중치가 낮은 간선을 추가한다.

Algorithm Kruskal(G, T)

• T <- Empty Set
• K <- Every Set
• N(T) < n-1
  • 간선 개수가 n-1개보다 작을동안 가중치가 제일 낮은 간선을 추가한다
  • 만약 사이클이 생기면 그 다음으로 가중치가 낮은 간선을 추가한다.
  • 사이클이 생기는 건 Union Find로 확인한다.

Example

성능 : $O(MlogM)$
$N$개의 노드가 있고, $M$개의 간선이 있을 때
우선순위 큐와 Union Find를 사용한다.
1. 우선순위 큐에 간선들을 저장하고 정렬한다. $O(MlogM)$
2. 맨 처음 간선을 꺼내고 $T_{mst}$에 넣는다.
3. 간선의 양쪽 노드에 대해서 Union Find를 한다.
3-1. 만약 두 노드의 부모가 같으면 사이클이 생기는 걸 알 수 있다. 이런 경우엔 그냥 진행한다.
3-2. 만약 두 노드의 부모가 다르면 두 노드를 합치고(Union Set의 우선순위가 낮은 쪽을 높은 쪽에 합침) 간선을 $T_{mst}$에 넣는다.
4. 우선순위 큐가 비어있지 않으면 3으로 돌아간다. 비어있으면 종료한다. 모든 간선에 대해서 수행하므로 위 과정을 $O(M)$번 수행한다.

그러므로 성능은 $O(MlogM)$!

kruskal은 모든 가능한 답을 찾을 수 있다.
Edge weight가 모두 다르면 kruskal은 한 개의 답만 찾는다.