图的应用-最小生成树问题之克鲁斯卡尔算法

图的应用——最小生成树问题之克鲁斯卡尔算法一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。[问题描述]若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。[基本要求]1．利用克鲁斯卡尔算法求网的最小生成树。2．要求输出各条边及它们的权值。114461232352346565二、测试结果最小生成树11441232352346565程序代码#include<stdio.h>#include<malloc.h>#defineMAX_VERTEX_NUM20typedefintVertexType;typedefintQElemType;typedefintInfoType;/******************************结构体部分****************************/typedefstructArcNode{intadjvex;//该弧指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附于该顶点的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//弧的顶点数和弧数intkind;//弧的类型}ALGraph;typedefintVRType;typedefstruct{intbegin,end;VRTypecost;}EDGE;/******************************函数操作部分****************************/voidSwapn(EDGE*edges,inti,intj){inttemp;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].cost;edges[i].cost=edges[j].cost;edges[j].cost=temp;}voidSort(EDGE*edges,ALGraphG){inti,j;for(i=1;i<=G.vexnum;++i)for(j=i;j<=G.vexnum;++j)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);}intFind(int*parents,intf){while(parents[f]>0)f=parents[f];return(f);}voidMiniSpanTree_Kruskal(ALGraphG){inti,v1,v2,value,bnf,edf;intparents[MAX_VERTEX_NUM];EDGEedges[MAX_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);edges[i].begin=v1;edges[i].end=v2;edges[i].cost=value;}Sort(edges,G);for(i=1;i<=G.vexnum;++i)parents[i]=0;printf("\n结果是：\n");for(i=1;i<=G.vexnum;++i){bnf=Find(parents,edges[i].begin);edf=Find(parents,edges[i].end);if(bnf!=edf){parents[bnf]=edf;printf("Arc(%d,%d):%d\n",edges[i].begin,edges[i].end,edges[i].cost);}}