WAP TO IMPLEMENT PRIM’s ALGORITHM - Algorithm Design and Analysis Lab file

WAP TO IMPLEMENT PRIM’s ALGORITHM

#include<iostream.h>

#define MAX 10

class prims

{

            private : int cost[MAX][MAX], tree[MAX][MAX];

                          int n;

            public  : void readmatrix();

                          int spanningtree(int);

                          void display(int);

};

void prims :: readmatrix()

{

            int i, j;

            cout << "\nEnter the number of vertices in the Graph : ";

            cin  >> n;

            cout << "\nEnter the Cost matrix of the Graph\n\n";

            for (i = 1; i <= n; i++)

                        for (j = 1; j <= n; j++)

                                    cin >> cost[i][j];

}

int prims :: spanningtree(int src)

{

            int visited[MAX], d[MAX], parent[MAX];

            int i, j, k, min, u, v, stcost;

            for (i = 1; i <= n; i++)

            {

                        d[i] = cost[src][i];

                        visited[i] = 0;

                        parent[i] = src;

            }

            visited[src] = 1;

            stcost = 0;

            k = 1;

            for (i = 1; i < n; i++)

            {

                        min = 999;

                        for (j = 1; j <= n; j++)

                        {

                                    if (!visited[j] && d[j] < min)

                                    {

                                                min = d[j];

                                                u = j;

                                    }

                        }

                        visited[u] = 1;

                        stcost = stcost + d[u];

                        tree[k][1] = parent[u];

                        tree[k++][2] = u;

                        for (v = 1; v <= n; v++)

                                    if (!visited[v] && (cost[u][v] < d[v]))

                                    {

                                                d[v] = cost[u][v];

                                                parent[v] = u;

                                    }

            }

            return (stcost);

}

void prims :: display(int cost)

{

            int i;

            cout << "\nThe Edges of the Mininum Spanning Tree are\n\n";

            for (i = 1; i < n; i++)

                        cout << tree[i][1] << " " << tree[i][2] << endl;

            cout << "\nThe Total cost of the Minimum Spanning Tree is : " << cost;

}

void main()

{

            int source, treecost;

            prims pri;

            pri.readmatrix();

            cout << "\nEnter the Source : ";

            cin  >> source;

            treecost = pri.spanningtree(source);

            pri.display(treecost);

}

Output :