크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘이란?

---

 -> 프림 알고리즘과 같이 MST(최소 스패닝 트리) 를 찾기 위한 알고리즘.

 -> 조금 Greedy한 방법.

 -> 간선을 중심으로 탐색하면서 노드를 확인용으로만 사용함.

 -> 핵심은 각 단계에서 사이클을 이루지 않은 간선을 선택하는 것!

 -> Union-Find 개념이 필요함! 

https://maivve.tistory.com/11

 -> 시간복잡도 : O(ElogV) 지만, 프림보다 크루스칼이 빠르다.

 

 

 

매커니즘

---

  1) 모든 간선들을 우선순위 큐에 넣고 weight를 오름차순해서 가장 작은 값부터 poll 한다.

  2) poll 한 간선의 양 끝 점이 같은 부모인지 체크한다.

  3) 같은 부모이면 다음 간선을 선택하고

  3-1) 다른 부모이면 해당 간선을 최종 선택한다. -> 가중치 추가 및 양 끝 노드의 부모 노드를 동일시(Union)

  4) 전체 노드의 개수 – 1개만큼 위 순서를 반복

 

 

 

샘플 코드

---

		** 이전에 모든 Vertex(간선)들을 우선순위 큐(graph)에 넣어둔 상태.
		int count = 0;
		int sum = 0;
		while(!graph.isEmpty()) {
			Vertex1647_2 vertex = graph.poll();
			int start = vertex.getStart();
			int end = vertex.getEnd();
			if(!isSameParent(start, end)) {	// 두 노드의 부모가 다른 경우 (사이클 여부를 판단하기 위함)
				sum += vertex.getWeight();
				count++;
				union(start, end);
				if(count + 2 == v) {
					break;
				}
			}
		}

 

 

 

참고사항

---

 ** 그래프 내에 적은 숫자의 간선들만 가지는 경우 - 크루스칼 알고리즘

 ** 그래프 내에 간선이 많이 존재하는 경우 - 프림 알고리즘

 ** 사용 권장!