인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Kruskal의 알고리즘

• 에지들을 가중치의 오름차순으로 정렬한다.

• 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택하지 않는다.

• n-1개의 에지가 선택되면 종료한다.

왜 MST가 찾아지는가?

• Kruskal의 알고리즘의 임의의 한 단계를 생각해보자.

• A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자.

  

사이클 검사

• 초기 상태 : 선택된 에지 없음

• 각각의 연결요소를 하나의 집합으로 표현

  

  

  

  (가중치 순으로 반복)

  

  

  (반복)

  

Kruskal의 알고리즘