Prim’s Algorithm and Minimum Spanning Tree in C++

For this sample C++ assignment, the expert is demonstrating to students the implemention of Prim’s algorithm to find a minimum spanning tree. Initial graph is given in the form of a dense graph represented as an adjacency cost matrix. It is mentioned that it is not compulsory for the costs in graph to follow euclidian metric or triangle inequality. In this example minimum spanning tree has to be found out  starting at node 0. A print out of minimum spanning tree also has to be taken.

SOLUTION: –

#include “prim.hpp”

#include <bits/stdc++.h>

#include <stdio.h>

#include <limits.h>

using namespace std;

//Number of vertices in the graph

#define V 100

/* A utility function to find the vertex with minimum key value,

from the set of vertices not yet included in MST. */

int MST::minKey( int key[100], bool mstSet[100] , int num_nodes){

// Initialize min value

int min = INT_MAX, min_index;

for (int v = 0; v < num_nodes; v++)

if (mstSet

[v]

== false && key

[v]

< min)

min = key

[v]

, min_index = v;

return min_index;

}

vector <pair<int,pair<int,int>>>  temp;

vector<pair<int,int> > to_out;

bool still_there(){

for (int i = 0; i < temp.size(); i++)

{

if(temp[i].second.second == 0) return 1;

}

return 0;

}

void get_next(int num ){

for (int i = 0; i < temp.size(); i++)

{

if(temp[i].second.second) continue;

if(temp[i].first == num)

{

temp[i].second.second = 1;

to_out.push_back({temp[i].first , temp[i].second.first});

get_next(temp[i].second.first );

}

}

}

bool comp(pair<int ,pair<int , int> > a , pair<int ,pair<int , int> > b)

{

if(a.first == b.first)

return a.second.first > b.second.first ;

return a.first < b.first;

}

//A utility function to print the constructed MST in the parent[]

string  MST::printMST(int parent[100], int graph[100][100] , int num_nodes , bool first){

stringstream  out;

temp.clear();

to_out.clear();

vector<pair<int,int>> col;

for (int i = 1; i < num_nodes; i++)

temp.push_back({parent[i] , {i, 0}});

sort(temp.begin(), temp.end() , comp);

// while(still_there())

get_next(0);

out << “\n”;

for( int i=0 ;i < (first ? (to_out.size()/2) : to_out.size()) ;i++)

out<< to_out[i].first << ” ” << to_out[i].second << “\n”;

out << “\n”;

return out.str();

}

/* Function to construct and pritn MST for a graph represneted

using adjacency maxtrix representation */

string  MST::primMST(int graph[100][100] , int num_nodes, bool first){

// Array to store constructed MST

int parent[V];

// Key values used to pick minimum weight edge in cut

int key[V];

// To represent set of vertices not yet included in MST

bool mstSet[V];

// Initialize all keys as INFINITE

for (int i = 0; i < num_nodes; i++)

key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first vertex.

key[0] = 0;

parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

for (int count = 0; count < num_nodes – 1; count++)

{

// Pick the minimum key vertex from the

// set of vertices not yet included in MST

int u = minKey(key, mstSet , num_nodes);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.

// Consider only those vertices which are not

// yet included in MST

for (int v = 0; v < num_nodes; v++)

// graph[u]

[v]

is non zero only for adjacent vertices of m

// mstSet

[v]

is false for vertices not yet included in MST

// Update the key only if graph[u]

[v]

is smaller than key

[v]

if (graph[u]

[v]

&& mstSet

[v]

== false && graph[u]

[v]

< key

[v]

)

parent

[v]

= u, key

[v]

= graph[u]

[v]

;

}

// print the constructed MST

return printMST(parent, graph, num_nodes , first);

}

#include <bits/stdc++.h>

#include “prim.hpp”

using namespace std;

int main(int argc, char* argv[]) {

// parse the expected input

// first, the number of nodes for the complete graph part

int num_nodes;

int graph [100][100];

string first , second;

std::cin >> num_nodes;

for (int i = 0; i < num_nodes; i++)

{

for (int j = 0; j < num_nodes; j++)

{

cin >> graph[i][j];

}

}

first = MST::primMST(graph  , num_nodes , 1);

// last bit until newline from last cin followed by a blank line

std::string skip;

cin.ignore();

std::getline(std::cin, skip);

std::getline(std::cin, skip);

// read in the new edges

// parse input lines until I find newline3

std::string line;

while( std::getline(std::cin, line) && line.size() ) {

std::stringstream ss(line);

int from;

int to;

int cost;

ss >> from;

ss >> to;

ss >> cost;

graph[to][from] = graph[from][to] = cost;

}

second = MST::primMST(graph  , num_nodes , 0);

puts(“”);

cout << first;

cout << second;

return 0;

}