實(shí)習(xí)三-求無(wú)向連通圖的生成樹(shù)

實(shí)習(xí)三求無(wú)向連通圖的生成樹(shù)需求分析問(wèn)題描述:若要在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ù)，其中，以課本8.7節(jié)中的等價(jià)類(lèi)表示構(gòu)造生成樹(shù)過(guò)程中的連通分量。(2)利用普里姆算法求網(wǎng)的最小生成樹(shù)。(3)以文本文件形式輸出生成樹(shù)中各條邊以及他們的權(quán)值。設(shè)計(jì)(1)設(shè)計(jì)思想：創(chuàng)建鄰接矩陣存儲(chǔ)結(jié)構(gòu)。本程序主要分為兩個(gè)模塊：創(chuàng)建鄰接矩陣模塊，最小生成樹(shù)模塊。創(chuàng)建鄰接矩陣模塊：以鄰接矩陣的存儲(chǔ)形式創(chuàng)建無(wú)向網(wǎng)。最小生成樹(shù)模塊：生成最小生成樹(shù)，輸出其各條邊及權(quán)值。(2)概要設(shè)計(jì)：int型LocateVex函數(shù)判斷權(quán)值在矩陣的位置；聲明CraeteGraph函數(shù)創(chuàng)建鄰接矩陣；聲明kruskal函數(shù)用于生成最小生成樹(shù)；聲明main函數(shù)為程序調(diào)用步驟。(3)設(shè)計(jì)詳細(xì)：a.將程序分為兩個(gè)模塊：B.主函數(shù)流程圖：c.最小生成樹(shù)流程圖(4)調(diào)試分析：--變量沒(méi)定義就使用解決：定義完變量在使用。--子函數(shù)嵌套定義；解決：子函數(shù)單獨(dú)定義，可調(diào)用。--使用數(shù)組是越界；解決：注意數(shù)組的值，注意不能越界。用戶手冊(cè)：a.主頁(yè)面：b.輸入頂點(diǎn)數(shù)及邊數(shù)的信息：c.輸入頂點(diǎn)信息：d.輸入頂點(diǎn)及權(quán)值：(6)測(cè)試結(jié)果：輸出最小生成樹(shù)及權(quán)值：(7)源程序：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX100#defineMAX_VERTEXNUM20typedefcharVertex[MAX];//頂點(diǎn)字符串typedefintAdjmatrix[MAX_VERTEXNUM][MAX_VERTEXNUM];//鄰接矩陣typedefstruct//定義圖{ Vertexvexs[MAX_VERTEXNUM]; Adjmatrixarcs; intvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,Vertexu)//判斷權(quán)值在矩陣的位置{ inti; for(i=0;i<G->vexnum;++i) { if(strcmp(G->vexs[i],u)==0) returni; } return-1;}voidCreateGraph(MGraph*G)//創(chuàng)建鄰接矩陣{ inti,j,k,w; Vertexva,vb; printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：（用空格隔開(kāi)）\n"); scanf("%d%d",&G->vexnum,&G->arcnum); printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的信息：（用空格隔開(kāi)）\n",G->vexnum); for(i=0;i<G->vexnum;++i) scanf("%s",G->vexs[i]); for(i=0;i<G->vexnum;++i) for(j=0;j<G->vexnum;++j) G->arcs[i][j]=MAX; printf("請(qǐng)輸入%d條邊的兩個(gè)頂點(diǎn)及權(quán)值：（用空格隔開(kāi)）\n",G->vexnum); for(k=0;k<G->arcnum;++k) { scanf("%s%s%d*c",va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G->arcs[i][j]=G->arcs[j][i]=w; }}voidkruskal(MGraphG)//最小生成樹(shù){ intset[MAX_VERTEXNUM],i,j; intk=0,a=0,b=0,min=G.arcs[a][b]; for(i=0;i<G.vexnum;++i) set[i]=i; printf("最小生成樹(shù)的各條邊及權(quán)值為：\n"); while(k<G.vexnum-1) { for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j]; a=i; b=j; } if(set[a]!=set[b]) { printf("%s-%s-%d\n",G.vexs[a],G.vexs[b],G.arcs[a][b]); k++; for(i=0;G.vexnum;i++) if(set[i]==set[b]) set[i]=set[a]; min=G