//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();
}

评论