#include<iostream.h> #include<process.h> #define MAX 10 #define TEMP 0 #define PERM 1 #define FALSE 0 #define TRUE 1 #define infinity 9999 struct node { int predecessor; int dist; int status; }; struct edge { int u; int v; }; int create_graph(); void display(); int maketree(edge [],int *); int all_perm(node [] ); int adj[MAX][MAX]; int n; void main() { int i,j; int path[MAX]; int wt_tree,count; struct edge tree[MAX]; create_graph(); cout<<"Adjacency matrix is :\n"; count = maketree(tree,&wt_tree); cout<<"Weight of spanning tree is : "<<wt_tree; cout<<"Edges to be included in spanning tree are : \n"; for(i=1;i<=count;i++) { cout<<tree[i].u<<" -> \n"; cout<<tree[i].v<<"\n"; } } int create_graph() { int i,max_edges,origin,destin,wt; cout<<" Prism minimun spamming tree algorithm"; cout<< endl; cout<<"Enter number of vertices : "; cin>>n; max_edges=n*(n-1)/2; for(i=1;i<=max_edges;i++) { cout<<"Enter edge "<< i <<" (0 0 to quit) : "; cin>>origin; cout<<"\t"; cin>>destin; if((origin==0) && (destin==0)) break; cout<<"Enter weight for this edge : "; cin>>wt; if( origin > n || destin > n || origin<=0 || destin<=0) { cout<<"Invalid edge!\n"; i--; } else { adj[origin][destin]=wt; adj[destin][origin]=wt; } } if(i<n-1) { cout<<"Spanning tree is not possible\n"; exit(1); } } void display() { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cout<<"\t"<<adj[i][j]; cout<<"\n"; } } int maketree(edge tree[MAX],int *weight) { node state[MAX]; int i,k,min,count,current,newdist; int m; int u1,v1; *weight=0; for(i=1;i<=n;i++) { state[i].predecessor=0; state[i].dist = infinity; state[i].status = TEMP; } state[1].predecessor=0; state[1].dist = 0; state[1].status = PERM; current=1; count=0; while( all_perm(state) != TRUE ) { for(i=1;i<=n;i++) { if ( adj[current][i] > 0 && state[i].status == TEMP ) { if( adj[current][i] < state[i].dist ) { state[i].predecessor = current; state[i].dist = adj[current][i]; } } } min=infinity; for(i=1;i<=n;i++) { if(state[i].status == TEMP && state[i].dist < min) { min = state[i].dist; current=i; } } state[current].status=PERM; u1=state[current].predecessor; v1=current; count++; tree[count].u=u1; tree[count].v=v1; *weight=*weight+adj[u1][v1]; } return (count); } int all_perm(node state[MAX] ) { int i; for(i=1;i<=n;i++) if( state[i].status == TEMP ) return FALSE; else return TRUE; cout<< " Press e to exit"; cin>>"e"; }
This is been coded in borland C++ I dont know if it works in V++