?? mst.cpp
字號:
/******Don't forget to download*****
*****GRAPHICAL DATA FILE STRUCTURE*****
*****A approach to learn DFS Graphically*****
Only @ http://www.vivekpatel.cjb.net */
//Minimum Spaning Tree (MST)
//Programmed by : Vivek Patel
//URL : www.vivekpatel.cjb.net
//Email : vivek_patel9@rediffmail.com
#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();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -