《实验七 克鲁斯卡算法生成最小树》由会员分享，可在线阅读，更多相关《实验七 克鲁斯卡算法生成最小树（5页珍藏版）》请在金锄头文库上搜索。
1、实验七 图的应用-最小生成树问题 -克鲁斯卡尔算法一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。问题描述若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。基本要求1利用克鲁斯卡尔算法求网的最小生成树。2要求输出各条边及它们的权值。14 6 1 23 5 2 3 465二、测试结果 最小生成树14 1 23 5 2 3 4653、 程序代码#include#include#define MAX_VERTEX_NUM 20typedef int Vertex
2、Type;typedef int QElemType;typedef int InfoType;/* 结构体部分 */typedef struct ArcNode int adjvex; /该弧指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 InfoType *info; /该弧相关信息指针ArcNode;typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附于该顶点的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjL
3、ist vertices; int vexnum,arcnum; /弧的顶点数和弧数 int kind; /弧的类型ALGraph; typedef int VRType;typedef struct int begin,end; VRType cost;EDGE; /* 函数操作部分 */void Swapn(EDGE *edges,int i,int j) int temp; temp=edgesi.begin; edgesi.begin=edgesj.begin; edgesj.begin=temp; temp=edgesi.end; edgesi.end=edgesj.end; edg
4、esj.end=temp; temp=edgesi.cost; edgesi.cost=edgesj.cost; edgesj.cost=temp; void Sort(EDGE *edges,ALGraph G) int i,j; for(i=1;i=G.vexnum;+i) for(j=i;jedgesj.cost) Swapn(edges,i,j); int Find(int *parents,int f) while(parentsf0) f=parentsf; return (f); void MiniSpanTree_Kruskal(ALGraph G) int i,v1,v2,v
5、alue,bnf,edf; int parentsMAX_VERTEX_NUM; EDGE edgesMAX_VERTEX_NUM; printf(请输入顶点和边的数量：n); scanf(%d%d,&G.vexnum,&G.arcnum); for(i=1;i=G.arcnum;+i) printf(请输入第%d条边的两个顶点和权值：n,i); scanf(%d%d%d,&v1,&v2,&value); edgesi.begin=v1; edgesi.end=v2; edgesi.cost=value; Sort(edges,G); for(i=1;i=G.vexnum;+i) parentsi=0; printf(n结果是：n); for(i=1;i=G.vexnum;+i) bnf=Find(parents,edgesi.begin); edf=Find(parents,edgesi.end); if(bnf!=edf) parentsbnf=edf; printf(Arc(%d,%d):%dn,edgesi.begin,edgesi.end,edgesi.cost); /* 主函数部分 */void main() ALGraph G; MiniSpanTree_Kruskal(G);
