1、精選優(yōu)質(zhì)文檔-傾情為你奉上計(jì)算機(jī)科學(xué)與工程學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目： Kruskal算法求最小生成樹 課程名稱： 離散數(shù)學(xué) 實(shí)驗(yàn)類型： 設(shè)計(jì)性 專業(yè)： 軟件工程 班級(jí)： 學(xué)生姓名： 學(xué)號(hào)： 實(shí)驗(yàn)日期： 2011 年 12 月 8 日 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)學(xué)時(shí)： 實(shí)驗(yàn)成績(jī)：指導(dǎo)教師： 年 月 日實(shí)驗(yàn)題目 Kruskal算法求最小生成樹實(shí)驗(yàn)原理設(shè)所給定無(wú)向連通加權(quán)圖具有n個(gè)結(jié)點(diǎn)，m條邊，首先，將各條邊的權(quán)按從小到大的順序排序。然后依次將這些邊按所給圖的結(jié)構(gòu)放到生成樹中去。如果在放置某一條邊時(shí)，使得生成樹形成回路，則刪除這條邊。這樣，直至生成樹具有n-1條邊時(shí)，我們所得到的就是一棵最小生成樹。實(shí)驗(yàn)步驟（1）

2、 邊依小到大順序得l1，l2，lm。（2） 置初值：S，0i，1j。（3） 若i=n-1，則轉(zhuǎn)（6）。（4） 若生成樹邊集S并入一條新的邊lj之后產(chǎn)生的回路，則j+1j，并轉(zhuǎn)（4）。（5） 否則，i+1i；ljS（i）；j+1j，轉(zhuǎn)（3）。（6） 輸出最小生成樹S。（7） 結(jié)束。實(shí)驗(yàn)中遇到的問(wèn)題及解決辦法(1) 出現(xiàn)回路:在前幾次測(cè)試時(shí),總會(huì)出現(xiàn)回路,經(jīng)過(guò)動(dòng)態(tài)跟蹤檢查出是在合并兩個(gè)連通分量時(shí)沒有考慮該結(jié)點(diǎn)是否同時(shí)在兩個(gè)連通分量中，導(dǎo)致合并后形成回路。解決辦法是增加一個(gè)尋找頂點(diǎn)的雙親直到根結(jié)點(diǎn)，如果根結(jié)點(diǎn)相同表明會(huì)形成回路不添加該邊。(2) 生成的并不是最小生成樹：原因在于開始手動(dòng)排序權(quán)值后輸入

3、的邊，一旦不按權(quán)值由小到大輸入邊，就不會(huì)產(chǎn)生最小生成樹。解決辦法，增加一個(gè)以權(quán)值為關(guān)鍵值的排序函數(shù)，將邊排序，然后再調(diào)用最小生成樹函數(shù)。問(wèn)題得以解決。(3) 出現(xiàn)多邊的情況，即在此形成回路：動(dòng)態(tài)跟蹤得知，忽略了最小生成樹的一條重要特征：最后所剩邊數(shù)應(yīng)為 頂點(diǎn)數(shù)-1 增加一個(gè)if判斷語(yǔ)句結(jié)束循環(huán)后問(wèn)題解決。程序清單及運(yùn)行結(jié)果 #include <iostream>using namespace std;const int MaxVertex = 20; /圖中最大頂點(diǎn)數(shù)const int MaxEdge = 100; /圖中最大邊數(shù)int FindRoot(int parent,in

4、t v);struct EdgeType int from; /邊的起點(diǎn)int to; /邊的終點(diǎn)int weight; /權(quán)值;struct EdgeGraphchar vertexMaxVertex; /頂點(diǎn)的數(shù)據(jù)類型為 charEdgeType edgeMaxEdge; /存放邊的數(shù)組int vertexNum; /圖的頂點(diǎn)數(shù)int edgeNum; /圖的邊數(shù)int parentMaxVertex;void Sort(EdgeType ed,int E)/權(quán)值排序int i,j;EdgeType p;for(i=0; i<E; +i)/趟次for(j=0;j<E-i-1;

5、+j)/沒趟比較次數(shù)if(edj.weight >= edj+1.weight)p = edj+1;edj+1 = edj;edj = p;/最小生成樹代碼實(shí)現(xiàn)主體部分void Kruskal(EdgeGraph G)int parentMaxVertex;int i;int num; int vex1;int vex2;for (i=0; i<G.vertexNum; i+)parenti = -1;for (num = 0,i = 0; i<G.edgeNum; i+) vex1 = FindRoot(parent,G.edgei.from); vex2 = FindRo

6、ot(parent,G.edgei.to); if (vex1 != vex2) cout << "(" <<G.vertex G.edgei.from <<" "<< G.vertexG.edgei.to << ")" << endl; /輸出生成的邊 parentvex2 = vex1 ; num+; if (num = G.vertexNum-1) return ; /求頂點(diǎn)的雙親一直到根int FindRoot(int parent,int v)while

7、 (parentv != -1) if (parentv > -1) v = parentv; return v;/主函數(shù)int main(int argc ,char *argv) EdgeGraph eg;char x,y; cout <<""<<endl;cout <<"請(qǐng)輸入圖的頂點(diǎn)數(shù)，和邊數(shù)： "<<endl;cout <<" "cin >> eg.vertexNum >> eg.edgeNum; cout <<"

8、請(qǐng)輸入各頂點(diǎn)的值： "<<endl;cout <<" "for (int j =0; j<eg.vertexNum; j+)cin >>eg.vertexj;cout <<"請(qǐng)分別輸入"<<eg.edgeNum<<"條邊各邊的起點(diǎn)，終點(diǎn)，及其權(quán)值： "<<endl;for (int i=0;i<eg.edgeNum;i+)cout <<" "cin >>x>>y>>

9、;eg.edgei.weight;for(int m= 0;m<eg.vertexNum;m+)if(eg.vertexm=x)eg.edgei.from= m; if(eg.vertexm=y) eg.edgei.to= m; Sort(eg.edge,eg.edgeNum);cout <<"最小生成樹為："<<endl;Kruskal(eg);return 0;程序運(yùn)行示例： 實(shí)驗(yàn)總結(jié)此次的設(shè)計(jì)是自己對(duì)已學(xué)知識(shí)的一個(gè)總結(jié)和升華，我在此過(guò)程中不但應(yīng)用了所學(xué)的知識(shí)，而且還結(jié)合數(shù)據(jù)結(jié)構(gòu)等書籍，以完成設(shè)計(jì)的需要，在設(shè)計(jì)的過(guò)程中我深深體會(huì)到，為了實(shí)現(xiàn)一個(gè)模塊的代碼、為了一個(gè)設(shè)計(jì)的實(shí)現(xiàn)思想、經(jīng)常絞盡腦汁來(lái)達(dá)到設(shè)計(jì)所要達(dá)到目的的艱辛，而且通過(guò)這次的實(shí)驗(yàn)，我也發(fā)現(xiàn)了自己還有很多地方有待