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 &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;limits&gt;
#include &lt;list&gt;
#include &lt;queue&gt;

class Graph
{

    struct Vertex
    {
        std::size_t id;
        int distance = std::numeric_limits&lt;int&gt;::max();
        Vertex * parent = nullptr;

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

    using pair_ = std::pair&lt;std::size_t, int&gt;;
    std::vector&lt;Vertex&gt; vertices = {};

    //adjacency list , store src, dest, and weight
    std::vector&lt; std::vector&lt; pair_&gt; &gt; adj_list;
    //to store unprocessed vertex min-priority queue
    std::priority_queue&lt; pair_, std::vector&lt;pair_&gt;,
                         std::greater&lt;pair_&gt; &gt; 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);
    adj_list.resize(size);
    for (int i = 0; i &lt; size; i++)
    {
        vertices.emplace_back(i);
    }
}

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

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

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

        int flag = 0, i = src;
        for (auto&amp; it : adj_list[i])
        {
            if (it.first == dest)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            adj_list[src].push_back( {dest, weight} );
        }
        else
        {
            throw std::logic_error("Existing edge");
        }

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

void Graph::prim(std::size_t vertex)
{
    vertices[vertex].distance = 0;
    vertices[vertex].parent = &amp;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();

        for (auto&amp; ver: adj_list[curr_vertex])
        {
            auto&amp; next_dist = vertices[ver.first].distance;
            const auto curr_dist = ver.second;
            if (curr_dist &lt; next_dist)
            {
                next_dist = curr_dist;
                //make src vertex parent of dest vertex
                vertices[ver.first].parent = &amp;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.add_edge(0, 1, 4);
    grp.add_edge(0, 2, 8);
    grp.add_edge(1, 2, 11);
    grp.add_edge(1, 3, 8);
    grp.add_edge(3, 4, 2);
    grp.add_edge(4, 2, 7);
    grp.add_edge(2, 5, 1);
    grp.add_edge(5, 4, 6);
    grp.add_edge(3, 6, 7);
    grp.add_edge(3, 8, 4);
    grp.add_edge(5, 8, 2);
    grp.add_edge(6, 7, 9);
    grp.add_edge(6, 8, 14);
    grp.add_edge(7, 8, 10);
    grp.prim(0);
    std::cout &lt;&lt; "The total cost is : " &lt;&lt; grp.minimum_cost() &lt;&lt; "\n";
}
1. Keeping references to potentially dangling pointers

I can see a potential problem with the line

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


if the std::vector&lt;Vertex&gt; 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&lt;std::unique_ptr&lt;Vertex&gt;&gt; vertices;


instead of keeping copies of the Vertex instances.

Then you can change 

vertices[ver.first].parent = &amp;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&lt;Vertex&gt; 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 &lt;&lt; "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.