Algotree > Algorithms > Minimum Spanning Tree > Prim's Minimum Spanning Tree Algorithm in C++

Prim's Minimum Spanning Tree Algorithm in C++

Prim’s algorithm finds the cost of a minimum spanning tree from a weighted undirected graph.
The algorithm begins by randomly selecting a vertex and adding the least expensive edge from this vertex to the spanning tree. The algorithm continues to add the least expensive edge from the vertices already added to the spanning tree to make it grow and terminates when all the vertices are added to the spanning tree.
It is evident that the algorithm gets greedy by selecting the least expensive edge from the vertices already added to the spanning tree.

Algorithm : Prims minimum spanning tree ( Graph G, Souce_Node S )

1.  Create a priority queue Q to hold pairs of ( cost, node ).
2.  Push [ 0, S ] ( cost, node ) in the priority queue Q i.e Cost of reaching the node S from source node S is zero.
3.  While ( ! Q.empty() )
4.       Item = Q.top(); Q.pop()
5.       Cost C = item.first and Vertex V = item.second
6.       If the node V is not present in the spanning tree
7.           Add node V to the spanning tree.
8.           Cost of the spanning tree += Cost C
9.           For all the vertices adjacent to node V that are not in the spanning tree.
10.               Push pair of ( cost, adjacent node ) into the Q

Example of finding the minimum spanning tree using Prim’s algorithm Prims_MST

Time complexity : O ( ( E + V ) log ( V ) )

Why is the time complexity of Prim's algorithm O ( ( E + V ) log ( V ) ) ?

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>

typedef std :: pair<int,int> PII;
typedef std :: vector<PII> VPII;

int Prims_MST (int source_node, std :: vector<VPII> & graph){

    // The priority_queue stores the pair<weight, node>
    std :: priority_queue<PII, std :: vector<PII>, std :: greater<PII>> q;

    // The cost of the source node to itself is 0
    q.push(std :: make_pair(0, source_node));

    bool added[graph.size()];
    memset(added, false, sizeof(bool)*graph.size());

    int mst_cost = 0;

    while (!q.empty()) {

        // Select the item <cost, node> with minimum cost
        PII item;
        item = q.top();
        q.pop();

        int node = item.second;
        int cost = item.first;

        // If the node is node not yet added to the minimum spanning tree add it, and increment the cost.
        if (!added[node]) {
            mst_cost += cost;
            added[node] = true;

            // Iterate through all the nodes adjacent to the node taken out of priority queue.
            // Push only those nodes (weight,node) that are not yet present in the minumum spanning tree.
            for (auto & pair_cost_node : graph[node]) {
                int adj_node = pair_cost_node.second;
                if (added[adj_node] == false) {
                    q.push(pair_cost_node);
                }
            }
        }
    }
    return mst_cost;
}

int main(){

    // Outgoing edges from the node:<cost, adjacent_node> in graph 1.
    VPII from_node_zero_in_graph_1  = { {1,1}, {2,2}, {1,3}, {1,4}, {2,5}, {1,6} };
    VPII from_node_one_in_graph_1   = { {1,0}, {2,2}, {2,6} };
    VPII from_node_two_in_graph_1   = { {2,0}, {2,1}, {1,3} };
    VPII from_node_three_in_graph_1 = { {1,0}, {1,2}, {2,4} };
    VPII from_node_four_in_graph_1  = { {1,0}, {2,3}, {2,5} };
    VPII from_node_five_in_graph_1  = { {2,0}, {2,4}, {1,6} };
    VPII from_node_six_in_graph_1   = { {1,0}, {2,2}, {1,5} };

    int num_nodes = 7; // Nodes (0, 1, 2, 3, 4, 5, 6)

    std :: vector<VPII> graph_1;
    graph_1.resize(num_nodes);

    graph_1[0] = from_node_zero_in_graph_1;
    graph_1[1] = from_node_one_in_graph_1;
    graph_1[2] = from_node_two_in_graph_1;
    graph_1[3] = from_node_three_in_graph_1;
    graph_1[4] = from_node_four_in_graph_1;
    graph_1[5] = from_node_five_in_graph_1;
    graph_1[6] = from_node_six_in_graph_1;

    // Start adding nodes to minimum spanning tree with 0 as the souce node
    std :: cout << "Cost of the minimum spanning tree in graph 1 : " << Prims_MST(0, graph_1) << std :: endl;

    // Outgoing edges from the node:<cost, adjacent_node> in graph 2.
    VPII from_node_zero_in_graph_2  = { {4,1}, {1,2}, {5,3} };
    VPII from_node_one_in_graph_2   = { {4,0}, {2,3}, {3,4}, {3,5} };
    VPII from_node_two_in_graph_2   = { {1,0}, {2,3}, {8,4} };
    VPII from_node_three_in_graph_2 = { {5,0}, {2,1}, {2,2}, {1,4} };
    VPII from_node_four_in_graph_2  = { {3,1}, {8,2}, {1,3}, {3,5} };
    VPII from_node_five_in_graph_2  = { {3,1}, {3,4} };

    num_nodes = 6; // Nodes (0, 1, 2, 3, 4, 5)

    std :: vector<VPII> graph_2;
    graph_2.resize(num_nodes);

    graph_2[0] = from_node_zero_in_graph_2;
    graph_2[1] = from_node_one_in_graph_2;
    graph_2[2] = from_node_two_in_graph_2;
    graph_2[3] = from_node_three_in_graph_2;
    graph_2[4] = from_node_four_in_graph_2;
    graph_2[5] = from_node_five_in_graph_2;

    // Start adding nodes to minimum spanning tree with 0 as the souce node
    std :: cout << "Cost of the minimum spanning tree in graph 2 : " << Prims_MST(0, graph_2) << std :: endl;
    return 0;
}

Output

Cost of the minimum spanning tree in graph 1 : 6
Cost of the minimum spanning tree in graph 2 : 9

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"Weeks of coding can save you hours of planning."