[자료구조/알고리즘] 스패닝 트리와 최소 스패닝 트리, 크루스칼 알고리즘, 프림 알고리즘

스패닝 트리(spanning tree)는 신장 부분 그래프(spanning subgraph)의 한 종류이다. 신장 부분 그래프는 원본 그래프의 모든 꼭짓점을 포함하는 부분 그래프로, 생성 부분 그래프라고도 한다. 이때 해당 부분 그래프가 트리라면 스패닝 트리 혹은 최소 신장 트리라고 부르고, 간선의 가중치가 동일하지 않은 경우에 한하여 가장 적은 가중치의 합으로 표현되는 스패닝 트리를 최소 스패닝 트리라 부른다. 즉, 최소 비용으로 모든 노드가 연결될 수 있도록 만드는 트리가 최소 스패닝 트리다. 아래의 사진이 그 예가 되겠다.

 

출처: 위키백과

최소 스패닝 트리를 구할 수 있는 대표적인 알고리즘이 크루스칼 알고리즘과 프림 알고리즘이다.

 

[크루스칼(Kruskal) 알고리즘의 동작 원리 및 순서]

 

1. 전체 간선을 가중치 순서대로 정렬한다.

2. 가장 낮은 가중치부터 탐색하며 간선 목록에 추가한다.

3. 선택된 간선이 연결하는 두 노드가 이미 연결된 노드라면 간선을 추가하지 않는다. (Union-Find로 확인)

4. 간선 목록에 (노드의 개수 - 1)개의 간선이 추가될 때까지 반복한다.

 

문제 및 코드 예시: https://mingchin.tistory.com/345

[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 4386번 _ 별자리 만들기

[프림(Prim) 알고리즘 동작 원리 및 순서]

 

1. 임의의 노드 k를 선택하여, 노드 목록에 추가한다.

2. 노드 목록에 있는 모든 노드에 대하여, 연결된 모든 간선 중 가장 가중치가 낮은 간선을 선택하여 간선 목록에 추가한다. 이때 새롭게 추가하는 간선과 연결된 반대편 노드를 노드 목록에 추가한다.

3. 노드 목록에 있는 노드의 수가 n이 될 때까지 2의 과정을 반복한다.