Data Structure : 최소비용신장트리 - Prim's Algorithm

Data Structure : 최소비용신장트리 - Prim's Algorithm

Prim의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다.

규칙

1. 하나의 정점에서 시작함.
2. 한번에 하나씩 Tree에 간선을 추가하고, 추가한 결과는 Tree를 이루어야 한다.
   • Tree가 여러 개이면 Forest
3. Tree에 추가한 간선이 Cycle을 구성하지 않도록, 간선을 고를 때 Tree에 속해있는 Vertex 하나와 속하지 않은 Vertex 하나가 만드는 간선을 골라야 한다.
4. Tree에 속한 edge의 개수가 vertex 개수 - 1인 경우 ( Spanning Tree 조건을 만족 ) 또는 추가할 edge가 없는 경우 ( Spanning Tree X ) 종료한다.

Prim 알고리즘

Tree = {  }; // Tree는 선택된 edge의 집합, E는 전체 edge의 집합, N은 Tree의 Vertex의 개수
TreeV = { 시작정점 }; // TreeV는 Tree에 포함된 Vertex의 집합

while ( Tree 가 n-1개의 edges를 가지지 못하면 && 추가할 edge가 없으면 ) {

TreeV에 속한 Vertex u와 속하지 않은 Vertex v에 대해 최소비용 edge(u, v)를 선택
    Tree에 edge(u,v)를 추가하고 TreeV에 v를 추가

}
if(Tree의 edge개수가 n-1이 안되면) {
   T는 Spanning Tree가 아니다
}

Prim 알고리즘의 동작방식

왼쪽의 Graph가 원본 그래프이고, 그래프를 토대로 최소비용신장트리를 구하고자 한다.

시작 정점을 3으로 지정하였다. Tree에는 현재 3만 들어있는 상태

Tree에서 뻗을 수 있는 가장 cost가 낮은 edge를 연결해가며 Tree를 확장한다.

Edge (3, 6)의 경우, 둘 다 Tree에 속해있고 최소비용의 edge도 아니기에 선택될 수 없다.

알고리즘 실행 결과로 붉은 색 edge들로 구성된 Spanning Tree를 얻을 수 있다.

Prim 알고리즘의 시간복잡도

Edge를 추가하는 과정이 n개의 Vertex마다 반복되고, 각각 추가할 edge를 탐색하는 과정이 n회 ( vertex 검사 ) 소요되므로 O ( n * n )이다.

따라서 Prim 알고리즘의 시간복잡도는 O ( n^2 ) 에 해당한다.