24. 크루스칼(Kruskal) 알고리즘

1. 개요

 크루스칼 알고리즘은 쉬움.

 MST를 만드는 알고리즘. 또 다른 알고리즘으로는 프림(Prim) 알고리즘 존재.

 크루스칼 알고리즘을 위한 2가지 방식 존재. DFS와 Disjoint Set.

 DFS는 그래프 탐색 기법으로 그래프의 Cycle을 형성하는지 체크.

 Disjoint Set은 집합을 트리로 형성하여 그래프의 Cycle을 형성하는지 체크.

 보통 DFS 방식보다 Disjoint Set이 성능면에서 좋음.

 크루스칼 알고리즘

 (1) 입력받은 엣지 데이터를 가중치(weight)를 기준으로 정렬

 (2) 현재 가장 최소 가중치를 가진 엣지부터 그래프에 연결

 (3) 그래프 Cycle 체크

 (4) 모든 엣지를 검사할 때까지 (2)~(3) 과정을 반복

 그래프에 Cycle이 생긴다는 의미는 최소신장트리가 될 수 없다는 의미.

 Disjoint Set으로 Cycle을 체크하는 방식은 이전 23 Chapter 참조

2. 문제

 아래 두 그래프에 대한 MST를 크루스칼 알고리즘을 통해 구성하라.

 (출력에서 UNION( X, Y )는 Vertex X와 Y가 연결되었다는 사실이다.)

 

3. 코드

3-1) 구조체 및 전역변수 선언

3-2) 메인

3-3) 그래프 생성 및 데이터 입력

3-4) 크루스칼 알고리즘

3-5) 출력

  

      (1) 문제 1번

        (2) 문제 2번

4. 정리

기억해야할 것

 (1) 크루스칼 알고리즘은 정렬에 대부분의 시간이 사용된다.

 (2) 알고리즘 순서는 정렬 - 연결 - Cycle 체크, 이 3가지순이다.

 (3) 크루스칼 알고리즘에 쓰이는 Disjoint Set은 집합의 구성을 따지는 알고리즘이다.