Prim's algorithm using priority_queue

Prim 알고리즘

개요

가중치가 있는 무방향 그래프에서 MST(최소 스패닝 트리)를 구할 때 Prim's 알고리즘을 이용할 수 있다.

본 포스팅에서는 인접 리스트로 표현된 그래프에서 PQ 자료구조를 이용해 MST를 구하는 방법을 알아 본다.

시간 복잡도는 O(E log(V)) 가 된다.

 

※ 참고: 인접 행렬로 구한 Prim 알고리즘 : O(V^2)

 

Prim 알고리즘에 PQ를 이용하기 위해서는 아래 두가지 연산이 필요하다.

- ExtractMin: MST에 아직 포함되지 않은 모든 정점에서 최소 키 값을 가진 정점을 가져온다.
- DecreaseKey: 정점을 추출한 후 인접한 정점의 키를 업데이트 해야 하며, 새 키가 더 작으면 업데이트 한다.

 

알고리즘

1) 모든 정점을 무한 값을 키 값으로 가지게 초기화 하고, 각 정점의 부모 노드는 '-1' 로 초기화 한다. 2) pq를 생성하고, (weight, vertex)를 입력으로 받는다. weight가 앞으로 간 이유는 첫번째 원소를 기준으로 정렬을 하기 때문이다. 3) 모든 정점을 MST에 포함되지 않은 것으로 초기화 한다(inMST[]). 이 배열은 고려된 정점이 다시 PQ에 포함되지 않게 하는데 사용된다.  4) 소스 정점을 pq에 넣고, 키 값을 '0'으로 만든다. 5) pq가 비어 있지 않을 때 까지 아래를 반복한다     5-1) 최소 키 값을 가지는 정점  u를 추출한다.     5-2) inMST[u] = true     5-3) 정점 u의 모든 인접 정점(v)을 확인한다.             If inMST[v] = false && key[v] > weight(u, v)                 Update key of v, i.e., do key[v] = weight(u, v)                 Insert v into the pq                 parent[v] = u                 // 만약 (u, v) 의 가중치가 key[v] 보다 작고, MST에 포함되지 않은 정점 v 라면,                  // key[v]를 업데이트 해준다. v를 pq에 삽입한다. v의 부모 노드는 u가 된다.

※ 2) 에서 순서를 (vertex, weight) 로 하고 싶다면, Compare 함수를 따로 정의해 주면 됩니다.

struct NodeInfo {
	size_t node;
	float dist;
};

struct NodeCompare {
	bool operator() (const NodeInfo & l, const NodeInfo & r) {
		return l.dist > r.dist;
	}
};

※ 3) 에서 inMST[]는 다익스트라와 다른 점이다. 다익스트라에서는 거리가 항상 증가하므로, 해당 배열이 필요하지 않았지만, prim 알고리즘에는 처리된 정점의 키 값을 확인하지 않으면 키 값이 감소할 수 있으므로 inMST[] 배열이 필요합니다.

다시말해, 새로 삽입된 항목의 키 값이 추출된 항목의 키 값보다 작을 수 있기 때문에, inMST[] 배열이 필요합니다.

 

코드

// STL implementation of Prim's algorithm for MST
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
 
typedef pair<int, int> iPair; // iPair ==>  Integer Pair
 
// This class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
 
    // In a weighted graph, we need to store vertex and weight pair for every edge
    // 각 정점에 대해 (인접 정접, 가중치)를 저장한 인접 리스트 가 필요하다.
    list< pair<int, int> > *adj;
public:
    Graph(int V);  // Constructor
 
    void addEdge(int u, int v, int w); // function to add an edge to graph
 
    void primMST(); // Print MST using Prim's algorithm
};

// Allocates memory for adjacency list
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair> [V];
}
 
void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}

void Graph::primMST()
{
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq; // iPair를 원소로 가지는 pq 선언
 
    int src = 0; // Taking vertex 0 as source
 
    // Create a vector for keys and initialize all keys as infinite (INF)
    vector<int> key(V, INF);
    
    // To store parent array which in turn store MST
    vector<int> parent(V, -1);
 
    // To keep track of vertices included in MST
    // MST에 포함되었는지 확인하는 배열을 생성한다(다익스트라와 다른점)
    vector<bool> inMST(V, false);
 
    // Insert source itself in priority queue and initialize its key as 0.
    // 시작점의 가중치 값은 '0'으로 둔다.
    pq.push(make_pair(0, src));
    key[src] = 0;  
    
    // pq가 빌 때 까지 루프를 돈다.
    while (!pq.empty())
    {
        // The first vertex in pair is the minimum key
        // vertex, extract it from priority queue.
        // vertex label is stored in second of pair (it
        // has to be done this way to keep the vertices
        // sorted key (key must be first item in pair)
        // pq에서 추출된 정점은 최소 가중치를 가지는 정점이다. 
        int u = pq.top().second;
        pq.pop();    
        
        //Different key values for same vertex may exist in the priority queue.
        //The one with the least key value is always processed first.
        //Therefore, ignore the rest.
        // 다른 가중치 값을 가지지만, 이미 처리했던 정점이 PQ에 있을 수 있다. 무시한다.
        if(inMST[u] == true)
          continue;
          
        inMST[u] = true;  // Include vertex in MST

        // 'i' 는 모든 인접 정점을 확인하기 위한 이터레이터다.
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            // Get vertex label and weight of current adjacent of u.
            // 헷갈림 주의 pq와 다르게 인접 리스트는 (정점, 가중치)로 저장했다.
            int v = (*i).first;
            int weight = (*i).second;

            //  If v is not in MST and weight of (u,v) is smaller than current key of v
            if (inMST[v] == false && key[v] > weight)
            {
                // Updating key of v
                key[v] = weight;
                pq.push(make_pair(key[v], v));
                parent[v] = u;
            }
        }
      }
    
      // Print edges of MST using parent array
      for (int i = 1; i < V; ++i)
          printf("%d - %d\n", parent[i], i);
}

// Driver program to test methods of graph class
int main()
{
    // create the graph given in above figure
    int V = 9;
    Graph g(V);
 
    //  making above shown graph
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
 
    g.primMST();
 
    return 0;
}

 

출처: https://www.geeksforgeeks.org/prims-algorithm-using-priority_queue-stl/

Prim's algorithm using priority_queue in STL - GeeksforGeeks