Minimum Spanning Tree using Prim’s Algorithm

What is Spanning Tree?

The idea behind minimum spanning trees is simple: given a graph with weighted edges, find a tree of edges with the minimum total weight. What is a spanning tree? A graph that satisfies these three properties: connected, acyclic, and consisting of |V| – 1 edges. (In fact, any two of the three conditions imply the third condition.)

What this means in practice is that a spanning tree is a collection of edges that connect any two nodes via a single path. It’s probably easiest to understand a tree using the definition that a tree is both connected and acyclic; think about binary trees–every node in the tree is reachable, so it’s connected, and there are no cycles because you can’t go back up the tree.

Prim’s Algorithm:

Prim’s algorithm closely resembles Dijkstra’s algorithm because they both rely on a similar approach of finding the “next closest” vertex. Prim’s algorithm slowly grows a minimum spanning tree, starting from a single vertex and adding in new edges that link the partial tree to a new vertex outside of the tree.

Using the cut property, we know that if we have a partial tree, then to add a new vertex to the tree, all we actually need to do is find the vertex that is closest to the tree (the elements in the tree and the elements outside the tree are the two sets in the cut property, so we just choose the smallest edge bridging the two).

Download Source Code:
[adinserter block=”1″]

Download: prims.c

Program for Minimum Spanning Tree in C++ using Prim’s Algo.

#include <iostream>
using namespace std;

#define ROW 7
#define COL 7
#define infi 5000  //infi for infinity

class prims
{
   int graph[ROW][COL],nodes;
   public:
   prims();
   void createGraph();
   void primsAlgo();
};

prims :: prims()
{
    for(int i=0;i<ROW;i++)
        for(int j=0;j<COL;j++)
            graph[i][j]=0;
}

void prims :: createGraph()
{
    int i,j;
    cout<<"Enter Total Nodes : ";
    cin>>nodes;
    cout<<"nnEnter Adjacency Matrix : n";
    for(i=0;i<nodes;i++)
        for(j=0;j<nodes;j++)
        cin>>graph[i][j];

    //Assign infinity to all graph[i][j] where weight is 0.for(i=0;i<nodes;i++){
        for(j=0;j<nodes;j++)
    {
        if(graph[i][j]==0)
            graph[i][j]=infi;
        }
}


void prims :: primsAlgo()
{
    int selected[ROW],i,j,ne; //ne for no. of edges
    int min,x,y;

    for(i=0;i<nodes;i++)
        selected[i]=false;

    selected[0]=true;
    ne=0;

    while(ne < nodes-1)
    {
        min=infi;
        for(i=0;i<nodes;i++)
        {
            if(selected[i]==true){
                for(j=0;j<nodes;j++){
                    if(selected[j]==false){
                        if(min > graph[i][j])
                        {
                            min=graph[i][j];
                            x=i;
                            y=j;
                        }
                    }
                }
            }
        }
        selected[y]=true;
        cout<<"n"<<x+1<<" --> "<<y+1;
        ne=ne+1;
    }
}

int main()
{
    prims MST;
    cout<<"nPrims Algorithm to find Minimum Spanning Treen";
    MST.createGraph();
    MST.primsAlgo();
    return 0;
}

OUTPUT: