//kruskal 算法实现; #include"graph2.h"datagraph g2,g1;struct node{//定义结构体;  int weight;     };struct enode{ int v1,v2; int weight; int key;};enode edge[100];node pp[100];int keys[100];int n;int nweight;int ecount1=0,ncount,ecount=0,ecount3=0;//初始化; void change_weight(int weight1,int weight2)//改变节点的权值; {  for(int k=1;k<=n-ncount;k++)  if(pp[keys[k]].weight==weight1||pp[keys[k]].weight==weight2)  pp[keys[k]].weight=n; } void get_tree()//生成树函数; { int min,min1,min2; while(ecount!=ncount-1) {  int m=1000;  for(int i=1;i<=ecount1;i++)  if(edge[i].weight<m&&edge[i].key==0)//选择权值最小的边;   {m=edge[i].weight;min=i;}  visite_gnode(g2,edge[min].v1,1);   min1=edge[min].v1;  visite_gnode(g2,edge[min].v2,1);   min2=edge[min].v2;  Wait();  if(pp[min1].weight!=pp[min2].weight)  {                                        //copy 权值最小的边;   copy_edge(g2,edge[min].v1,edge[min].v2,g1);  display_edge(g1,edge[min].v1,edge[min].v2);  keys[++ecount3]=min1;  keys[++ecount3]=min2;  edge[min].key=1;  change_weight(pp[min1].weight,pp[min2].weight);//改变权值最小的边的节点;   n++;  Wait(); ecount++;  }     }  } void main(){   load_graph_file(g2,"graphs\\grpprim.grp");  display_graph("graph",g2);  copy_all_vertex(g2,g1,0,220);  disp_graph("tree",g1);  ncount=nodes(g2);  for(int k=1;k<=ncount;k++)  pp[k].weight=k;  for(int i=1;i<=ncount;i++)  for(int j=i;j<=ncount;j++)  if(have_edge(g2,i,j))  {     edge[++ecount1].weight=edge_weight(g2,i,j);  edge[ecount1].v1=i;     edge[ecount1].v2=j;   }  Wait();  n=ncount+1;  get_tree();  Wait();}

评论