最小生成樹的Kruskal算法實驗報告.doc

《最小生成樹的Kruskal算法實驗報告.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、大連民族學院計算機科學與工程學院實驗報告實驗題目：最小生成樹的Kruskal算法課程名稱：離散數(shù)學實驗類型：□演示性□驗證性□操作性■設計性□綜合性專業(yè)：軟件工程班級：111學生姓名：xx學號：xx實驗日期：2012年12月6-28日實驗地點：金石灘校區(qū)機房201實驗學時：10學時實驗成績：指導教師：焉德軍姜楠2012年12月28日[實驗原理]設所給定無向連通加權圖具有n個結(jié)點，m條邊，首先，將各條邊的權按從小到大的順序排序。然后依次將這些邊按所給圖的結(jié)構(gòu)放到生成樹中去。如果在放置某一條邊時，使得生成樹形成回路，則刪除這條邊。這樣，直至生成樹具有n-1條

2、邊時，我們所得到的就是一棵最小生成樹。[實驗內(nèi)容]給定無向連通加權圖，編程設計求出其一棵最小生成樹。[實驗目的]通過算法設計并編程實現(xiàn)求出給定無向連通加權圖的一棵最小生成樹，加深學生對求最小生成樹的Kruskal算法的理解。[實驗步驟]（1）邊依小到大順序得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é)束。具體程序的C++實現(xiàn)如下：#include

3、stream>usingnamespacestd;constintMaxVertex=20;constintMaxEdge=100;constintMaxSize=100;structEdgeType{intfrom;intto;intweight;};structEdgeGraph{charvertex[MaxVertex];EdgeTypeedge[MaxEdge];intvertexNum;intedgeNum;};intFindRoot(intparent[],intv);voidInputInfo();voidKruskal(EdgeGraph

4、G){intvex1,vex2,f,t;inti,num;intparent[MaxVertex];for(i=0;i

5、m;t=G.edge[i].to;cout<<"("<-1){t=parent[t];}returnt;}voidInputInfo(){EdgeGraphG;cou

6、t<<"PleaseinputvertexNum,edgeNum:"<>G.vertexNum>>G.edgeNum;cout<<"Pleaseinputtheinformationofedges:"<>G.vertex[i];}cout<<"Pleaseinputthisedgeattachestwoverticessubscriptanditsweight"<>G.edge[j

7、].from>>G.edge[j].to>>G.edge[j].weight;}Kruskal(G);}intmain(){InputInfo();system("pause");return0;}實驗過程中遇到的問題及解決過程比如不知道如何存儲邊集數(shù)組，以及比知道如何聲明一些變量，函數(shù)和怎樣去調(diào)用Kruskal函數(shù)……解決：通過設置結(jié)構(gòu)體EdgeType與結(jié)構(gòu)體EdgeGraph的聯(lián)合來存儲邊集，因為在剛開始我在主函數(shù)中用EdgeGraph聲明變量G，來作為形參去調(diào)用Kruskal(G)，編譯時就會警告未被初始化的G，的程序出錯，后來我將Kruskal

8、(G)在InputInfo()中調(diào)用，因為InputInfo()函數(shù)中聲明了變量