Prim's Algorithm C++

Question

I'm implementing a simple version of Prim's algorithm in C++ and having some difficulty translating the algorithm to work with my very basic graph implementation.

I have a struct for edges as follows:

struct edge 
{
    int src;
    int dest;
    int weight;
};

I simply push the edges to a vector in the graph class. I'm not sure if this is the best way to implement Prim's but it seems to be optimal for my end result which is being able to simply print out the amount of vertices visitTed and the total weight of the minimal spanning tree.

I think I understand the basic idea of Prim's but I have questions on a few points. All I'm asking for is a push in the right direction. Pseudocode specific to my usage would be ideal though.

1) Pick a starting vertex

2) In a while loop from the source vertex to all others, add the edge weights to a heap of some sort (this is confusing to me, some algorithms say to initialize to infinity but STL priority queue doesn't have a reserve method...)

3) Get the lowest edge (pop from priority queue or in my poorly thought out implementation traverse the vector for the lowest value...)

4) If the destination of the lowest value has been visited, throw that edge away and try the next. If not, add the edge to the minimum spanning tree and mark it visited.

I don't have much code and am getting to a point of diminishing returns, so any advice is appreciated. Here's what I got:

vector<edge> graph::prims(int source, vector<edge> vt)
{
    int current;
    vector<bool> visited(numVert, false);
    vector<unsigned int> minWeight;
    minWeight.reserve(numVert);

    // Intilize minWeight to a large number
    for(int j=0; j < numEdges; j++)
    {
        minWeight[j] = 0xffffffff;
    }

    current = source; 

    // Will this even work? What if I pick the nth node...
    while (current <= numEdges)
    {
        // This should add the edge weights to the current vertex 
        // to a vector so the minimum can be found
        for(int i = 0; i < numVert; i++)
        {
            if(vt[i].src == current && visted[i] == false)
            {
                minWeight.push_back(vt[i].weight);
            }
        }
    }

    // Need to finish Prim's


    return vt;
}

I've been trying to get code off the internet and modify all day and it got me nowhere. So I finally decided to attempt it myself. It's not much but this took me about two hours...

My code can be found on Google Drive.

Answer 1

//Prims Algorithm implementation using matrix in simpler way

#include<iostream>
#include<limits.h>
using namespace std;
int n=5;

//Min Node will return the node having minimum weight
int min_node(int matrix[5][5],bool visited[5]){
    int result;
    int min_value=INT_MAX;

    for(int i=0;i<n;i++){
        if(visited[i]){
            for(int j=0;j<n;j++){
                if(matrix[i][j]<min_value && !visited[j]){//If the node is not in visited array then consider it,otherwise not,
                                                            //to avoid the loop in the minimum spanning tree
                    min_value=matrix[i][j];//update the min value
                    result=i*10 + j;
                }//endl inner if structure
            }//end inner for loop
        }//end outer if structure
    }//end outer for loop

    return result;
}

int main(){
cout<<"Hello world\n";
int matrix[5][5]={
                    {0,18,15,0,0},
                    {18,0,12,0,13},
                    {15,12,0,20,0},
                    {0,0,20,0,11},
                    {0,13,0,11,0}
                };

//Display the matrix
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)
        cout<<matrix[i][j]<<"\t";
     cout<<"\n";
}

//Make the disconnected node weight = MAX
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        if(matrix[i][j]==0)
            matrix[i][j]=INT_MAX;
    }
}

//Take an visited array
bool visited[5];
//Make all the entries of visited array false
for(int i=0;i<5;i++)
    visited[i]=false;

int source;
cout<<"Enter the source vertex\n";
cin>>source;

visited[source]=true;

//Tree having 'n' vertices will have 'n-1' edges in the minimum spanning tree
int t=4;
while(t>0){
    int result=min_node(matrix,visited);
    int i=result/10;
    int j=result%10;
    visited[j]=true;//Now add the new node the visited, to consider the its edeges in the condition
    cout<<"Path "<<i<<"- "<<j<<" ="<<matrix[i][j]<<endl;

t--;
}

return 0;
}

Answer 2

I've had a look through your code and it seems like your design is incomplete in some areas. Let's take a look.

Your graph class looks like this:

class graph {
public:
        ... function prototypes ...
private:
        int numVert;
        int numEdges;
};

This class declaration is missing some rather important information: in particular, while the number of vertices and the number of edges is stored, no information about the vertices or edges belonging to a given graph instance is ever stored.

You already have edge and city structs that can be used for edges and vertices respectively. These can be stored in std::vector<...> members of your graph class, and - if you are careful to preserve the relevant orderings - you can address these by numerical index and be (mostly) fine. Once you've done that, you can tweak addEdge and addCity such that they actually do what they should - that is, add a edge or a vertex, respectively, to the graph instance.

Another thing to think about is how you actually want to store your edges. The 'best' approach depends on the nature of the problem, but for most applications, it suffices to store edges either in a structure keyed by vertex ID (e.g. a std::map<std::vector<...> > instance), or as a subfield in each vertex object (e.g. by adding a std::vector<...> member field to your city class).

---

This aside, let's address the actual algorithm you're trying to implement.

Prim's algorithm is, at its heart, iterated application of this rule:

Add to the candidate minimum spanning tree the minimal-weight edge connecting some vertex inside the tree to some vertex outside.

That is, at each step, we do this:

• Consider the vertices in the tree we have built up so far; call this set A. (At the very beginning, this is a single vertex of your choice. At the end, this is the vertex set of the connected component containing the initial vertex; if your graph is connected, this is all the vertices.)
• Consider the vertices in our graph that are not in the tree; call this set B.
• Look at all possible edges connecting any vertex in set A with any vertex in set B (in graph-theory language. the cut-set of the cut (A, B) of your graph). If there are none, you're done. Otherwise, pick the edge among these with the smallest weight and add it to the tree.

You can prove that, given that the original graph is connected, this algorithm produces a spanning tree with minimal total edge weight. Try to justify this to yourself.

---

So, where are you right now? While I can't read your mind, I can tell you what your code is telling me:

• You're trying to keep track of the set of vertices you've already visited.
  • This is good; you'll need that.
• You're trying to keep track of the cut-set, i.e. the edges exiting the visited set.
  • You'll need this as well.
  • I'm not sure why you're using only a std::vector<unsigned int> for this purpose, since for a given edge you need to track three quantities: the 'from' vertex, the 'to' vertex, and the weight. You might want a std::vector<edge> instead for this purpose.
• It looks like you're trying to populate this set.
  • You may need to redo this bit, depending on whether you change the layout of your data structures.
  • The main idea - find edges running from visited nodes to unvisited nodes - is there, but I'm not sure the approach the current code is suggesting is going to work.

So, what's missing from the algorithm?

• Once you have a valid cut-set, you need to find the edge in the set with the lowest weight.
• You need to add this edge to the return set.
• You need to mark the vertex this edge connects to as visited. Call this node N.
• You need to update the cut-set. In particular, any edges connecting N to the vertices previously visited need to be removed, and any edges connecting N to some unvisited vertex need to be added.

---

I hope this helps you out. If you're confused about anything, need some more explanation, or think something I've said is inaccurate or incorrect, let me know and I'll update this answer.