实验五.Kruskal算法的设计.doc

[实验目的]
根据算法设计需要, 掌握连通网的灵活表示方法;
掌握最小生成树的Kruskal算法;
基本掌握贪心算法的一般设计方法;
进一步掌握集合的表示与操作算法的应用.
[预习要求]
认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;
设计Kruskal算法实验程序.
实验目的: 
1. 根据算法设计需要, 掌握连通网的灵活表示方法;
2. 掌握最小生成树的Kruskal算法;
3. 基本掌握贪心算法的一般设计方法;
4. 进一步掌握集合的表示与操作算法的应用.
实验内容: 
  编写 Kruskal 算法程序求最小生成树.
程序关键代码: 
 
void CreatGraph(MGraph *G)// 构件图
{int i, j,n, m;
 fscanf(fp1,"%d,%d",&G->um,&G->vexnum);// 输入边数和顶点数
 for(i=1;i<=G->vexnum;i++)// 初始化图
  for(j=1;j<=G->vexnum;j++)
  G->arc[i][j].tag=0;// 初始化adj值
 for(i=1;i<=G->um;i++)// 输入边和权值 
 {
  fscanf(fp1,"%d-%d",&n,&m);
  G->arc[n][m].tag=1; 
  fscanf(fp1,"%d",&G->arc[n][m].weight);
 }}
 
void Swapn(edge *edges,int i,int j)// 交换权值以及边的头和尾 
{ int temp;  
  temp=edges[i].begin;  
  edges[i].begin=edges[j].begin;
  edges[j].begin=temp;
  temp=edges[i].end;  
  edges[i].end=edges[j].end;
  edges[j].end=temp;
  temp = edges[i].weight;  
  e
dges[i].weight=edges[j].weight;
  edges[j].weight=temp;
} 
 
void sort(edge edges[],MGraph *G)// 对权值进行排序 
{int i,j;
 for(i=1;i<G->um;i++)
  for(j=i+1;j<=G->um;j++)
  if(edges[i].weight>edges[j].weight)
  Swapn(edges,i,j);
 fprintf(fp2," 按权值从小到大排序后的各边及其权值:\n");
 fprintf(fp2," 边权值\n");
 for(i=1;i<=G->um;i++)
  fprintf(fp2,"(%d,%d) %d\n",edges[i].begin,edges[i].end,edges[i].weight);
}
 
int Find(int *parent,int f) 
{while(parent[f]>0) // 去掉回路
  f=parent[f];  
 ret