[GeeksForGeeks] Prim

🔒 문제

💭 생각의 흐름

MST (Minimum Spanning Tree) + Undirected Graph

=> 2가지 방법!

• Kruskcal
• Prim✔️

• mstSet: 방문된 MST 원소의 집합
• not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합
• find minimum cut vertex : mstSet과  not visited Set을 최소 비용으로 연결하는 노드 찾기

 

mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set

not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용

⭐ find minimum cut vertex -> not visted Set 에서 value 최소값 구하기 -> min_element 함수 사용

Time Compexity : O(V^2) // N^2/2

 

Prirority Queue를 사용하는 것이 더 효율적이다.

 

---

🔑 풀이1 (C++)

prim.h

#pragma once
#include <unordered_set>
#include <map>
#include <vector>
#include <algorithm>

class Prim {
private:
    enum {
        DESTINATION_VERTEX,
        WEIGHT
    };
    struct CompareValue {
        bool operator()(const std::pair<int, int>& left, const std::pair<int, int>& right) const {
            return left.second < right.second;
        }
    };

public:
    // list representation, with V vertices.
    int spanningTree(int V, std::vector<std::vector<int>>& adj);

};

 

Prim.cpp

#include "Prim.h"

int Prim::spanningTree(int V, std::vector<std::vector<int>>& adj) {
    // w: weight (distance) [0,1000]

    std::unordered_set<int> mstSet;
    std::map<int, int> notVisitedVertices;

    for (int i = 0; i < V; i++) {
        notVisitedVertices[i] = 1000;
    }
    // first vertex is 0 for picking first
    notVisitedVertices[0] = 0;

    int answer = 0;

    while (mstSet.size() < V) {
    	// find minimum cut vertex
        std::pair<int, int> minimumVertex = *min_element(notVisitedVertices.begin(), notVisitedVertices.end(), CompareValue());
        mstSet.emplace(minimumVertex.first);
        answer += minimumVertex.second;
        notVisitedVertices.erase(minimumVertex.first);

        for (const auto& adjacentVertex : adj[minimumVertex.first]) {
            // update key, 0: destination vertex , 1: weight
            // not exists in mstSet -> not visited Vertex
            if (mstSet.find(adjacentVertex[DESTINATION_VERTEX]) == mstSet.end()) {
                // less than previous value -> update
                if (adjacentVertex[WEIGHT] < notVisitedVertices[adjacentVertex[DESTINATION_VERTEX]]) {
                    notVisitedVertices[adjacentVertex[DESTINATION_VERTEX]] = adjacentVertex[WEIGHT];
                }
            }
            // exists -> nothing to do
        }
    }

    return answer;

}

main.cpp

#include "DetectCycleDFS.h"
#include "Prim.h"
#include <iostream>

using namespace std;

int main() {

        int V, E;
        cin >> V >> E;
        vector<vector<int>> adj[V]; // adjacent Matrix
        int i = 0;
        while (i++ < E) {
            int u, v, weight;
            cin >> u >> v >> weight;
            vector<int> t1, t2;
            t1.emplace_back(v);
            t1.emplace_back(weight);
            adj[u].emplace_back(t1);
            
            t2.emplace_back(u);
            t2.emplace_back(weight);
            adj[v].emplace_back(t2);
            
        }
        Prim obj;
        cout << adj->size() << endl;
        cout << "result : " << obj.spanningTree(V, adj) << endl;

    return 0;
}

 

🔑 풀이2 (Optimization using Priority Queue)

Prim.h

#pragma once
#include <unordered_set>
#include <vector>
#include <queue>

class Prim {

private:
    struct Node {
        unsigned int nodeNumber;
        // max weight is 1000
        unsigned int weight = 1000;
    };

    struct CompareWeight {
        bool operator()(const Node& previousNode, const Node& nextNode) const {
            return previousNode.weight > nextNode.weight;
        }
    };

    enum {
        DESTINATION_VERTEX,
        WEIGHT
    };

public:
    // list representation, with V vertices.
    int spanningTree(int V, std::vector<std::vector<int>> adj[]);

};

Prim.cpp

#include "Prim.h"

int Prim::spanningTree(int V, std::vector<std::vector<int>> adj[]) {
    // w: weight (distance) [0,1000]

    std::unordered_set<unsigned int> mstSet;
    struct Node nodes[V];

    for (int index = 0; index < V ; index++) {
        nodes[index] = {static_cast<unsigned int>(index)};
    }
    // first vertex is 0 for picking first
    nodes[0] = {0, 0};

	// auto minHeap Generate and construct prirority queue like this
    std::priority_queue<Node, std::vector<Node>, CompareWeight> priorityQueue(nodes, nodes + V);

    int answer = 0;

    while (mstSet.size() < V) {
        // find minimum cut vertex
        const Node minimumNode = priorityQueue.top();
        priorityQueue.pop();
        
        
        // there is duplication of nodeNumber
        // because C++ STL doesn't support change priority (Decrease key) operation
        // emplace || push operation makes duplication
        // so check the duplication like this
        if (mstSet.find(minimumNode.nodeNumber) != mstSet.end()) continue;

        mstSet.emplace(minimumNode.nodeNumber);
        answer += minimumNode.weight;

        for (const auto& adjacentVertex : adj[minimumNode.nodeNumber]) {
            // update key, 0: destination vertex , 1: weight
            // not exists in mstSet -> not visited Vertex
            if (mstSet.find(adjacentVertex[DESTINATION_VERTEX]) == mstSet.end()) {
                // less than previous value -> update
                if (adjacentVertex[WEIGHT] < nodes[adjacentVertex[DESTINATION_VERTEX]].weight) {
                    nodes[adjacentVertex[DESTINATION_VERTEX]].weight = adjacentVertex[WEIGHT];
                    // need to update update priority queue change priority
                    priorityQueue.emplace(Node{static_cast<unsigned int>(adjacentVertex[DESTINATION_VERTEX]), static_cast<unsigned int>(adjacentVertex[WEIGHT])});
                }
            }
            // exists -> nothing to do
        }
    }

    return answer;

}

---

Time Complexity 풀이 1 vs 풀이2

Prim 알고리즘은 N개의 노드 모두 MST 집합에 포함될 때까지 연산하는데

가장 최소 비용으로 연결할 cut vertex 를 찾는 연산에서 시간복잡도가 좌지우지 된다.

 

 

[풀이1] 노드 갯수만큼 조사해야함

while (mstSet.size() < V) {
    	// find minimum cut vertex
        std::pair<int, int> minimumVertex = *min_element(notVisitedVertices.begin(), notVisitedVertices.end(), CompareValue());
        // ...
}

∴ O(V^2)

 

[풀이2]

(1) 배열 -> 최소 힙 생성 == 2V

(2) 우선순위 큐 getMin() == O(1)

(3) 새 원소 삽입 또는 우선순위 변경 == O(E log V)

 

while (mstSet.size() < V) {
  // find minimum cut vertex
  const Node minimumNode = priorityQueue.top();
  priorityQueue.pop();
  if (mstSet.find(minimumNode.nodeNumber) != mstSet.end()) continue;
  // ...
}

∴ O (E log V)

 

풀이 1은 1.6초가 나왔었다. 시간이 절반으로 줄어든 모습

 

※ Tip

애석하게도 C++ stl 에서 기본 제공하는 우선순위 큐는 change priority (== decreaseKey) 를 제공하지 않는다.

 

 

 

Reference

STL Priority Queue for Structure or Class - GeeksforGeeks

 

Prim's algorithm using priority_queue in STL - GeeksforGeeks