#include <iostream.h> #include <conio.h> #define MAX_NODE 50 struct node{ int vertex; int weight; node *next; }; struct fringe_node{ int vertex; fringe_node *next; }; node *adj[MAX_NODE]; //For storing Adjacency list of nodes. int totNodes; //No. of Nodes in Graph. const int UNSEEN=1,FRINGE=2,INTREE=3; //status of node. int status[MAX_NODE];//status arr for maintaing status. fringe_node *fringe_list;//singly link list void createGraph(){ node *newl,*last; int neighbours; cout<<\"\\n\\n---Graph Creation---\\n\\n\"; cout<<\"Enter total nodes in graph : \"; cin>>totNodes; for(int i=1;i<=totNodes;i++){ last=NULL; cout<<\"Total Neighbours of \"<<i<<\" : \"; cin>>neighbours; for(int j=1;j<=neighbours;j++){ newl=new node; cout<<\"Neighbour #\"<<j<<\" : \"; cin>>newl->vertex; cout<<\"Weight #\"<<j<<\" : \"; cin>>newl->weight; newl->next=NULL; if(adj[i]==NULL) adj[i]=last=newl; else{ last->next = newl; last = newl; } } } } //Insert node in a fring_list at Begining. void Insert_Beg(int item){ fringe_node *newl; newl = new fringe_node; newl->vertex = item; newl->next = NULL; newl->next = fringe_list; fringe_list = newl; } //Delete element at pos position from fringe_list. void del(int pos){ //to points to previous node from where //to insert int i; fringe_node *tmp,*delnode; for(i=1,tmp=fringe_list; i < (pos-1); tmp=tmp->next,i++); delnode = tmp->next; tmp->next = tmp->next->next; delete(delnode); } void MST(){ int i,x,parent[MAX_NODE],edge_count,w,v; int min_wt,y,fringe_wt[MAX_NODE],stuck; node *ptr1; fringe_node *ptr2; fringe_list=NULL; for(i=1;i<=totNodes;i++) status[i]=UNSEEN; x=1; status[x]=INTREE; edge_count=0; stuck=0; while( (edge_count <= (totNodes-1)) && (!stuck)) { ptr1=adj[x]; while(ptr1!=NULL){ y=ptr1->vertex; w=ptr1->weight; if((status[y]==FRINGE) && (w<fringe_wt[y])) { parent[y]=x; fringe_wt[y]=w; } else if(status[y]==UNSEEN){ status[y]=FRINGE; parent[y]=x; fringe_wt[y]=w; Insert_Beg(y); } ptr1=ptr1->next; } if(fringe_list==NULL) stuck=1; else{ x=fringe_list->vertex; min_wt=fringe_wt[x]; ptr2=fringe_list->next; while(ptr2!=NULL){ w=ptr2->vertex; if(fringe_wt[w] < min_wt) { x=w; min_wt=fringe_wt[w]; } ptr2=ptr2->next; } del(x); status[x]=INTREE; edge_count++; } } for(x=2;x<=totNodes;x++) cout<<\"(\"<<x<<\",\"<<parent[x]<<\")\\n\"; } void main(){ clrscr(); cout<<\"*****Minimum Spaning Tree (MST)*****\\n\"; createGraph(); cout<<\"\\n===Minimum Spaning Tree===\\n\"; MST(); getch(); }