Things to be discussed here.

  • Prim’s Algorithms
  • Practice Problem

The prerequisite for this article is “Introduction to Minimum Spanning Tree & Kruskal Algorithm“, as most of the concept related to Minimum Spanning Tree is already discussed there.

Prim’s Algorithm

Prim’s Algorithm is also a Greedy Algorithm to find MST. In Prim’s Algorithm, we grow the spanning tree from a starting position by adding a new vertex. In Kruskal’s Algorithm, we add an edge to grow the spanning tree and in Prim’s, we add a vertex.

Algorithm:

  • Store the graph in an Adjacency List of Pairs.
  • Maintain a min Priority Queue (pq) that sorts edge based on min edge cost. This will be used to determine the next node to visit and the edge used to get there.
  • Start the algorithm on any node s, mark as visited, and iterate over all edges of s, adding them to the (pq).
  • While the (pq) is not empty and the MST has not been formed, dequeue the next cheapest edge from the (pq).
  • If the dequeued edge is outdated ( means that the node it points has already been visited) then skip it and dequeue the next edge. Otherwise mark the current node as visited and add the selected edge to the MST.
  • Iterate over the new current node’s edges and add all its edges to the (pq). 
  • Do not add edges to the (pq) which points the already visited nodes.

Here is a Video from Youtube which explains the above algorithm.

Implementation in C++

In this implementation I have just found the Minimum Cost, you need to manipulate the code to store the MST Edges. If you find this difficult and need implementation for this then do Comment.

This Implementation is for Lazy Version of Prims. Later, when we will study Fibbinacci Heap in our Data Structure then we will be implementing Eager Version of Prim’s Algorithm.

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int prims(vector<vector<pii> > adjList, bool visited[], int n, int m, int s) {
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push(make_pair(0, s));
    vector<pair<int, pii> > mst;  // Data Structure to store your MST Edges.
    int minCost = 0;
    while (!pq.empty()) {
        int p = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if (visited[p]) continue;
        visited[p] = true;
        minCost += cost;

        // Write your code to store the MST edges here.

        for (int i = 0; i < adjList[p].size(); i++) {
            if (!visited[adjList[p][i].first]) {
                pq.push(make_pair(adjList[p][i].second, adjList[p][i].first));
            }
        }
    }
    return minCost;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii> > adjList(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adjList[u].push_back(make_pair(v, w));
        adjList[v].push_back(make_pair(u, w));
    }
    // Now in prims we select any arbitrary node as starting node.
    // Here we will be taking node 1 as starting node.
    bool visited[n + 1];
    for (int i = 1; i <= n; i++) visited[i] = false;
    cout << "The cost of Minimum Spanning Tree: "
         << prims(adjList, visited, n, m, 1) << "\n";
    return 0;
}

Input:

7 9
1 2 10
2 4 40
3 4 25
1 3 15
4 5 35
2 5 30
5 6 10
5 7 8
6 7 9

Output:

The cost of Minimum Spanning Tree: 97

Application and Practice Problem is the same for both Kruskal’s Algorithm and Prim’s Algorithm.

Applications:

  • In electronic circuit design to minimize the wire length.
  • To find routing path in networks
  • Airplane network routes.
  • Network Design etc.

Practice Problem

  1. Lazy Student ( 605B )
  2. The child and zoo ( 437D )
  3. Minimum Spanning Tree for each Edge ( 609E )
  4. Edges in MST ( 160D )

That’s all for this article, in the next session we will be discussing Directed Graphs and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA

Leave a Reply