prims.cpp

#include<bits/stdc++.h>

using namespace std;

int G[100][100],spanning[100][100],n;

int prims()
{
    int cost[100][100];
    int u,v,min_distance,distance[100],from[100];
    int visited[100],no_of_edges,i,min_cost,j;

    //create cost[][] matrix,spanning[][]
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
        {
            if(G[i][j]==0) cost[i][j]=999;
            else
            {
                cost[i][j]=G[i][j];
                spanning[i][j]=0;
            }
        }
    }
    //initialize visited[],distance[] and from[]
    distance[0]=0;
    visited[0]=1;

    for(i=1;i<n;i++)
    {
        distance[i]=cost[0][i];
        from[i]=0;
        visited[i]=0;
    }

    min_cost=0;        //cost of spanning tree
    no_of_edges=n-1;        //no. of edges to be added

    while(no_of_edges>0)
    {
        //find the vertex at minimum distance from the tree
        min_distance=999;
        for(i=1;i<n;i++){
            if(visited[i]==0&&distance[i]<min_distance)
            {
                v=i;
                min_distance=distance[i];
            }
        }
        u=from[v];

        //insert the edge in spanning tree
        spanning[u][v]=distance[v];
        spanning[v][u]=distance[v];
        no_of_edges--;
        visited[v]=1;

        //updated the distance[] array
        for(i=1;i<n;i++){
            if(visited[i]==0&&cost[i][v]<distance[i])
            {
                distance[i]=cost[i][v];
                from[i]=v;
            }
        }
        min_cost=min_cost+cost[u][v];
    }
    return(min_cost);
}

int main()
{
    int i,j,total_cost;
    cout <<"Enter the vertices :";
    cin >>n;
    cout <<"The matrix : " <<endl;
    for(i=0;i<n;i++) for(j=0;j<n;j++) cin >> G[i][j];

    total_cost=prims();
    cout <<"Spanning tree matrix :" <<endl;

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
             if(spanning[i][j]!=0)
             {
                cout <<"from "<<i<<"to "<<j<< " "<<spanning[i][j];
                spanning[j][i]=0;
             }

            cout <<endl;
    }
    cout << "MST is : "<<total_cost<<endl;
    return 0;
}