# Prim's Algorithm - Minimum Spanning Tree

I have implemented Prim's Algorithm from Introduction to Algorithms. I have observed that the code is similar to Dijkstra's Algorithm, so I have used my Dijkstra's Algorithm implementation.

Please review this code and suggest improvements.

To compile on Linux: g++ -std=c++14 prims.cpp

#include <iostream>
#include <map>
#include <limits>
#include <list>
#include <queue>

class Graph
{

struct Vertex
{
std::size_t id;
int distance = std::numeric_limits<int>::max();
Vertex * parent = nullptr;

Vertex(std::size_t id) : id(id) {}
};

using pair_ = std::pair<std::size_t, int>;
std::vector<Vertex> vertices = {};

//adjacency list , store src, dest, and weight
//to store unprocessed vertex min-priority queue
std::priority_queue< pair_, std::vector<pair_>,
std::greater<pair_> > unprocessed;

public:
Graph(std::size_t size);
void add_edge(std::size_t src, std::size_t dest, int weight);
void prim(std::size_t vertex);
std::size_t  minimum_cost() ;
};

Graph::Graph(std::size_t size)
{
vertices.reserve(size);
for (int i = 0; i < size; i++)
{
vertices.emplace_back(i);
}
}

void Graph::add_edge(std::size_t src , std::size_t dest, int weight)
{
if(weight >= 0)
{
if (src == dest)
{
throw std::logic_error("Source and destination vertices are same");
}

if (src < 0 || vertices.size() <= src)
{
throw std::out_of_range("Enter correct source vertex");
}

if (dest < 0 || vertices.size() <= dest)
{
throw std::out_of_range("Enter correct destination vertex");
}

int flag = 0, i = src;
{
if (it.first == dest)
{
flag = 1;
break;
}
}
if (flag == 0)
{
}
else
{
throw std::logic_error("Existing edge");
}

}
else
{
std::cerr << "Negative weight\n";
}
}

void Graph::prim(std::size_t vertex)
{
vertices[vertex].distance = 0;
vertices[vertex].parent = &vertices[vertex];

unprocessed.push( std::make_pair(vertices[vertex].distance, vertex) );
while (!unprocessed.empty())
{
int curr_vertex_dist = unprocessed.top().first;
std::size_t curr_vertex = unprocessed.top().second;
unprocessed.pop();

{
auto& next_dist = vertices[ver.first].distance;
const auto curr_dist = ver.second;
if (curr_dist < next_dist)
{
next_dist = curr_dist;
//make src vertex parent of dest vertex
vertices[ver.first].parent = &vertices[curr_vertex];
unprocessed.push( std::make_pair(next_dist, ver.first));
}
}
}
}

std::size_t  Graph::minimum_cost()
{
std::size_t cost = 0;
for (auto vertex: vertices)
{
cost = cost + vertex.distance;
}
return cost;
}

int main()
{
Graph grp(9);
grp.prim(0);
std::cout << "The total cost is : " << grp.minimum_cost() << "\n";
}


### 1. Keeping references to potentially dangling pointers

I can see a potential problem with the line

vertices[ver.first].parent = &vertices[curr_vertex];


if the std::vector<Vertex> vertices would be reorganised due to changes in length. The address you take there isn't stable.

Maybe a better solution would be to keep a

std::vector<std::unique_ptr<Vertex>> vertices;


instead of keeping copies of the Vertex instances.

Then you can change

vertices[ver.first].parent = &vertices[curr_vertex];


to

vertices[ver.first].parent = vertices[curr_vertex].get();


Since all the vertices are in private scope of the Graph class the std::unique_ptr<Vertex> instances stored to the vertices vector will never invalidate, as long you guarantee to remove all child Vertex instances when a parent Vertex instane is removed from the graph (Well, that's not an operation in question here, but needs to be considered for production code).

### 2. Inconsistent error handling

Here

else
{
std::cerr << "Negative weight\n";
}


you just use kind of errorneous input being reported to the console, while you throw exceptions for other cases.

For this condition you should rather do

• throwing an exception
• applying an assert() call in 1st place
• clarify from the function signature

If Negative weight is erroneous input you should make that clear in 1st place:

  void Graph::add_edge(std::size_t src , std::size_t dest, unsigned weight)
// ^^^^^^^^


This way violations would be covered by the compiler, before runtime detects that flaw.

### 3. Storing unnecessary information

In your code example parent is never used besides storing the information. I am aware that you might have been simplified the actual usage of parent with this review question, but with the code context you give, that member variable doesn't make any sense.

• I do not understand. Here we are making a node/vertex as a parent to other node/vertex. Nov 16, 2019 at 8:42
• @coder As mentioned, the address you take there isn't stable. It points to an element address in that std::vector. As soon this std::vector will be resized, that address is invalidated. Nov 16, 2019 at 8:46
• @coder I realized that using std::reference_wrapper won't work either. std::unique_ptr seems to be the right tool to express ownership here. Nov 16, 2019 at 9:12
• std::unique_ptr is not the right tool. The right tool is std::size_t. The problem with the invalidation of iterators/references can be completely alleviated by storing the index of the member and not a reference to it. The only thing necessary is then to call operator[] Nov 16, 2019 at 12:17
• @miscco Feel free to write another answer with some example code. Nov 16, 2019 at 12:24