圖的最小生成樹的實(shí)現(xiàn)(Kruskal算法)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說明書圖的最小生成樹的實(shí)現(xiàn)（Kruskal算法）學(xué)生姓名學(xué)號(hào)班級(jí)成績指導(dǎo)教師計(jì)算機(jī)科學(xué)與技術(shù)系2011年3月4日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書題目圖的最小生成樹的實(shí)現(xiàn)（Kruskal算法）學(xué)生姓名學(xué)號(hào)指導(dǎo)教師評(píng)語及成績成績：教師簽名：年月曰答辯教師評(píng)語及成績成績：教師簽名：年月曰教研室意見總成績：室主任簽名：年月曰注：指導(dǎo)教師成績60%，答辯成績40%，總成績合成后按五級(jí)制記入。摘要設(shè)計(jì)了一種圖的最小生成樹的實(shí)現(xiàn)程序。本程序的算法按照克魯斯卡爾算法的思想，采用圖的鄰接矩陣法存儲(chǔ)圖的頂點(diǎn)和邊。納入權(quán)值最小的邊作為最小生成樹的一部分，如遇回路則舍棄準(zhǔn)備納入的邊，直到圖的所有頂點(diǎn)被遍歷。

2、該程序采用VC+作為軟件開發(fā)環(huán)境，簡單易行又節(jié)省時(shí)間。關(guān)鍵詞：圖;最小生成樹；克魯斯卡目錄TOC o 1-5 h z HYPERLINK l bookmark2 課題描述1 HYPERLINK l bookmark4 問題分析和任務(wù)定義2 HYPERLINK l bookmark6 邏輯設(shè)計(jì)3 HYPERLINK l bookmark8 流程圖4 HYPERLINK l bookmark10 程序編碼7 HYPERLINK l bookmark12 程序調(diào)試結(jié)果11 HYPERLINK l bookmark14 結(jié)果分析13 HYPERLINK l bookmark16 總結(jié)14參考文獻(xiàn)15

3、課題描述本次課程設(shè)計(jì)題目是：圖的最小生成樹的實(shí)現(xiàn)（Kruskal算法）。要求按照克魯斯卡爾的算法思想編寫一個(gè)新的程序，實(shí)現(xiàn)圖的最小生成樹的生成。Kruskal算法就是把所有的邊按權(quán)值從小到大排序，然后依次把各個(gè)點(diǎn)加入到最小樹的集合中去，但是在加入的過程中不能有回路。自主完成程序的編譯與調(diào)試，畫出流程圖，并對(duì)此次課程設(shè)計(jì)過程中出現(xiàn)的問題和自己掌握的東西做一個(gè)詳細(xì)的分析總結(jié)。問題分析和任務(wù)定義本課題涉及圖的創(chuàng)建，存儲(chǔ)及最小生成樹問題。所謂最小生成樹，就是給定一個(gè)無向圖，挑選若干條邊，連成一個(gè)樹行圖（無圈），使得所選邊的權(quán)至和最小。該程序的算法是生成圖的最小生成數(shù)，而且算法必須遵循克魯斯卡爾思想，即

4、納入圖中權(quán)值最小的邊作為最小生成樹的一部分，繼續(xù)納入權(quán)值次小的邊，直到圖中所有頂點(diǎn)被遍歷，如納入邊的過程中構(gòu)成回路則舍棄該邊，否則納入。邏輯設(shè)計(jì)該程序主要由六大塊組成，包括構(gòu)造最小生成樹數(shù)組、排序、交換權(quán)值、構(gòu)造最小生成樹、查找、還有主函數(shù)。如下圖3.1所示：圖的最小生成樹的實(shí)現(xiàn)（Kruskal算法）構(gòu)造最小生成樹數(shù)組交換權(quán)值構(gòu)造最小生成樹圖3.1程序模塊圖1 4流程圖該程序的流程圖如圖4.1所示：i=1T.ivexnumjvexnumJ+l+i=1iarcnumYI+-Y-J=1SidebySideNiprintf（”鄰接矩陣為:n）;inti,j,n,m;beginG-Aarqijtl.a

5、djhGarcji.adj=O:SidebySide圖4.1流程圖 1)圖4.2流程圖Yf=parentf;returnf; 5程序編碼#include#include#defineM20#defineMAX20typedefstructintbegin;intend;intweight;edge;typedefstructintadj;intweight;AdjMatrixMAXMAX;typedefstructAdjMatrixarc;intvexnum,arcnum;MGraph;voidCreatGraph(MGraph*);/函數(shù)申明voidsort(edge*,MGraph*);v

6、oidMiniSpanTree(MGraph*);intFind(int*,int);voidSwapn(edge*,int,int);voidCreatGraph(MGraph*G)/構(gòu)件圖inti,j,n,m;printf(請(qǐng)輸入邊數(shù)和頂點(diǎn)數(shù):)；scanf(%d%d,&G-arcnum,&G-vexnum);for(i=1;ivexnum;i+)/初始化圖for(j=1;jvexnum;j+)G-arcij.adj=G-arcji.adj=0;for(i=1;i=G-arcnum;i+)/輸入邊和權(quán)值printf(n請(qǐng)輸入有邊的2個(gè)頂點(diǎn))；scanf(%d%d,&n,&m);while(

7、n0|nG-vexnum|marcnm.adj=G-arcmn.adj=1;getchar();printf(n請(qǐng)輸入%d與宀之間的權(quán)值：，n,m);scanf(%d,&G-arcnm.weight);printf(鄰接矩陣為：n);for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)printf(%d,G-arcij.adj);printf(n);voidsort(edgeedges,MGraph*G)/對(duì)權(quán)值進(jìn)行排序inti,j;for(i=1;iarcnum;i+)for(j=i+1;jarcnum;j+)if(edgesi.weightedgesj.weight

8、)Swapn(edges,i,j);printf(權(quán)排序之后的為：n);for(i=1;iarcnum;i+)edgesi.end,printf(%dn,edgesi.begin,edgesi.weight);voidSwapn(edge*edges,inti,intj)/交換權(quán)值以及頭和尾inttemp;temp=edgesi.begin;edgesi.begin=edgesj.begin;edgesj.begin=temp;temp=edgesi.end;edgesi.end=edgesj.end;edgesj.end=temp;temp=edgesi.weight;edgesi.weig

9、ht=edgesj.weight;edgesj.weight=temp;voidMiniSpanTree(MGraph*G)/生成最小生成樹inti,j,n,m;intk=1;intparentM;edgeedgesM;for(i=1;ivexnum;i+)for(j=i+1;jvexnum;j+)if(G-arcij.adj=1)edgesk.begin=i;edgesk.end=j;edgesk.weight=G-arcij.weight;k+;sort(edges,G);for(i=1;iarcnum;i+)parenti=0;printf(最小生成樹為：n);for(i=1;i=G-a

10、rcnum;i+)/核心部分n=Find(parent,edgesi.begin);m=Find(parent,edgesi.end);if(n!=m)parentn=m;edgesi.end,printf(0)f=parentf;returnf;intmain(void)/主函數(shù)MGraph*G;G=(MGraph*)malloc(sizeof(MGraph);if(G=NULL)printf(memoryallcationfailed,goodbye);exit(1);CreatGraph(G);MiniSpanTree(G);system(pause);return0; 6程序調(diào)試結(jié)果程

11、序調(diào)試結(jié)果如圖6.1，圖6.2所示：圖6.1結(jié)果運(yùn)行圖圖6.2結(jié)果運(yùn)行圖7結(jié)果分析程序運(yùn)行過程中出現(xiàn)的問題主要有：調(diào)試過程中必須以正確的格式輸入圖的頂點(diǎn)，以及邊的相關(guān)信息。必須要把與一個(gè)頂點(diǎn)相關(guān)的所有邊輸入結(jié)束再換下一個(gè)頂點(diǎn)，不能按任意方式輸入。否則將造成程序調(diào)試出錯(cuò)，無法達(dá)到預(yù)期的目的。該程序是以鄰接矩陣的方法創(chuàng)建和存儲(chǔ)圖的信息，必須要熟悉并掌握鄰接矩陣的相關(guān)知識(shí)，才能有效減少編程過程中出現(xiàn)不必要的麻煩和錯(cuò)誤?？唆斔箍査惴ǖ臅r(shí)間復(fù)雜度為O(eloge).8總結(jié)Kruskal算法就是把所有的邊按權(quán)值從小到大排序，然后依次把各個(gè)點(diǎn)加入到最小樹的集合中去，但是在加入的過程中要判斷是否有回路。唯一困難的問題就是這個(gè)，怎么判斷有沒有回路？用一個(gè)簡單的標(biāo)記方法。開辟一個(gè)新數(shù)組，大小和圖中點(diǎn)的個(gè)數(shù)一樣多，并初始化為點(diǎn)的對(duì)應(yīng)標(biāo)號(hào)。這個(gè)數(shù)組是記錄該點(diǎn)已經(jīng)在哪顆樹當(dāng)中。開始的時(shí)候自然是自己獨(dú)立的一顆樹，在每次加入一條邊的時(shí)候，判斷這條邊的2個(gè)點(diǎn)在數(shù)組中記錄的樹時(shí)候是一樣的，如果一樣，那就說明是在同一顆樹中，如果加入了會(huì)有回路，所以這條邊不能加入。而如果不同，那就把這2個(gè)點(diǎn)中其中一個(gè)點(diǎn)的權(quán)值變成另一個(gè)點(diǎn)的權(quán)值，表示在同一顆樹中，這樣，便解決了該問題。經(jīng)過兩個(gè)