최소신장트리. [1197]

[1. 문제 설명]

그래프가 주어졌을 때, 최소 신장 트리의 가중치를 출력한다.

---

[2. 풀이 접근]

 

A. 크루스칼 알고리즘

• edge 를 가중치를 기준으로 하여 오름차순 정렬한다.
• 가중치가 낮은 edge 부터 tree 에 추가하도록 한다.
  => edge 추가로 인해 cycle 이 발생하는 경우, 이번 edge 는 버리도록 한다.
• tree 에 추가된 edge 개수가 정점의 개수 - 1 일 때 까진 반복한다.\

=> cycle 여부 판별을 union-find 를 이용하면 전체 알고리즘은 정렬 시간에 가장 큰 영향을 받는다.

(최적의 union-find 는 거의 상수 시간으로 동작 하기 때문이다.)

=> 시간복잡도: O(ElogE)

 

 

B. 프림 알고리즘

• 임의의 정점에서 시작한다. (보통 번호가 가장 빠른 노드)
• 이 정점에서 가중치가 가장 낮은 edge 를 tree 에 추가한다.
• tree 에 새로 추가 된 정점에 인접한 edge 중 weight 가 가장 낮은 것을 찾는다.
  => 이미 tree 에 추가된 정점으로 향하는 edge 는 제외해야 한다.
•  

밀집 그래프인 경우 우선순위 큐를 쓴 프림 알고리즘은 크루스칼 알고리즘 보다 빠르다.

=> 시간복잡도: O(ElogV)

---

[3. 코드 - 크루스칼]

---

[4. 코드 - 프림]