## Sunday, October 30, 2011

### C program for prims minimum spanning tree algorithm

prims minimum spanning tree algorithm

#include<iostream.h>

#define MAX 10

class prims
{
private : int cost[MAX][MAX], tree[MAX][MAX];
int n;
int spanningtree(int);
void display(int);
};

{
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;
}

int main()
{
int source, treecost;
prims pri;