實驗七圖的應用---最小生成樹問題-----克魯斯卡爾算法一、實驗目的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);}