최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

최소 신장 트리(MST, Minimum Spanning Tree)

사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프.

 

※ 신장 트리(Spanning Tree)

사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결되어 있는 그래프.

▶ 간선의 개수 = 정점의 개수 - 1

ex) 정점의 개수 |V| = 6 / 간선의 개수 |E| = 5

        5 = 6 -1 

▶ 크루스칼 알고리즘Kruskal's Algorithm 혹은 프림 알고리즘Prim's Algorithm을 통해 구현가능

    시간복잡도: 둘다 동일하게 O(ElogV)로 구현 가능

 

Kruskal's Algorithm

; 가중치가 낮은 간선으로 정점을 이어가면 모든 정점을 방문하는 방식

① 비용이 낮은 간선 선택 ← 우선순위 큐

② 선택된 간선이 사이클 형성 여부 확인

      * 간선 선택 시, 사이클 유무 확인 ← Union-Find 사용

Disjoint-Set & Union-Find

③ 모든 정점이 연결될 때까지, ①, ②작업 반복 

 

- [BOJ] 1922 네트워크 연결

[BOJ] 백준 1922 네트워크 연결

 

Prim's Algorithm

선택(방문)된 정점에서 가장 낮은 가중치 간선으로 정점을 연결하며 확장하는 방식

① 임의의 정점을 선택해서 방문

    ※ 무방향 그래프이기 때문에 어느 정점에서 시작하든 결국 결과는 같음. 

         (간선에서 동등한 가중치가 있다면 구현에 따라 경로는 다를 수 있음)

② 선택된 정점포함해서 연결된 모든 정점들의 간선 중 

    가장 가중치가 낮은 간선Edge을 통해 연결되지 않은 정점 연결

    ※ 아직 방문하지 않은 정점을 연결하기에 사이클 형성 X

③ 모든 정점이 연결될때까지 ② 작업 반복

▶ 시간복잡도 O(ElogV) ← 우선순위 큐를 이용해 Heap 구조로 구현시

    단순 Array로 구현시 O(|V2|)

- [BOJ] 1197 최소 스패닝 트리

[BOJ] 백준 1197 최소 스패닝 트리

 

요약

Kruskal's Algorithm은 여기저기서 트리를 형성하여 나중에 합쳐지는 형태이기에

사이클 형성 여부를 확인해줘야 합니다. ← Union-Find

Prim's Algorithm은 시작단계부터 최소신장트리를 확장해가는 방식입니다.

 

Q. 최소 신장트리(MST)는 최단 경로인가?

A → E로 가는 경로는 최소신장트리에서는 [A - C - D - E]로, cost = 3 + 3 + 2 = 『 8 』 이지만,

실제 최단 거리는 [A - C - E]로 , cost = 3 + 4 = 『 7 』 입니다.

 

관련 문제

- [SWEA] 4006 고속도로 건설 2