實(shí)驗(yàn)七-克魯斯卡算法生成最小樹(shù)

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