圖的應(yīng)用——最小生成樹問題之克魯斯卡爾算法一、實驗?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識。2、熟練掌握圖的存儲結(jié)構(gòu)。3、掌握如何應(yīng)用圖解決各種實際問題。[問題描述]若要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價建設(shè)這個通信網(wǎng)，是一個網(wǎng)的最小生成樹問題。[基本要求]1．利用克魯斯卡爾算法求網(wǎng)的最小生成樹。2．要求輸出各條邊及它們的權(quán)值。114461232352346565二、測試結(jié)果最小生成樹11441232352346565程序代碼#include<stdio.h>#include<malloc.h>#defineMAX_VERTEX_NUM20typedefintVertexType;typedefintQElemType;typedefintInfoType;/******************************結(jié)構(gòu)體部分****************************/typedefstructArcNode{intadjvex;//該弧指向的頂點的位置structArcNode*nextarc;//指向下一條弧的指針I(yè)nfoType*info;//該弧相關(guān)信息指針}ArcNode;typedefstructVNode{VertexTypedata;//頂點信息ArcNode*firstarc;//指向第一條依附于該頂點的指針}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//弧的頂點數(shù)和弧數(shù)intkind;//弧的類型}ALGraph;typedefintVRType;typedefstruct{intbegin,end;VRTypecost;}EDGE;/******************************函數(shù)操作部分****************************/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("請輸入頂點和邊的數(shù)量：\n");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=1;i<=G.arcnum;++i){printf("請輸入第%d條邊的兩個頂點和權(quán)值：\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結(jié)果是：\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);}}