最小生成樹實驗報告(共6頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、實驗?zāi)康?. 通過上機程序，進(jìn)一步加深對最小生成樹的理解。2. 掌握Kruskal算法。3. 學(xué)會用程序解決離散數(shù)學(xué)中的問題。4. 增強我們編寫程序的能力。二、實驗內(nèi)容求帶權(quán)無向聯(lián)通平面圖的最小生成樹三、實驗環(huán)境我的實驗依舊是在VC6.0實驗環(huán)境下完成的，而所設(shè)計的程序也在這個環(huán)境下通過了編譯，運行和測試。四、實驗原理和實現(xiàn)過程利用Kruskal算法求最小生成樹，原理如下：1. 選取最小權(quán)邊e1，置邊數(shù)jß1.2. i=n-1結(jié)束，否則轉(zhuǎn)c。3. 設(shè)已經(jīng)選擇的邊為e1,e2,，ei,在G中選取不同于e1,e2,ei的邊，使e1,e2,，ei,ei+1中無

2、回路且ei+1是滿足此條件的最小邊。4. ißi+1，轉(zhuǎn)b。根據(jù)這個，還有以下思路：由G生成的最小生成樹T所包含的邊的集合1按非降序權(quán)重將E中的邊排序2建立n個單元素集（每個頂點一個）3最小生成樹的邊集合T初始為空4 .while |T|<n-15.令e(x,y)為E中的下一條邊6. if包含x的集合不是與包含y的集合不是同一個集合 then7.將e(x,y)加入到T8.將包含x的集合和包含y的集合合并9.end if10.end while五、實驗源代碼及分析#include<stdio.h>struct Edgeint from, to, weight; /定義

3、一個數(shù)據(jù)結(jié)構(gòu)，存放點和邊的關(guān)系以及邊的權(quán)值;Edge edge100, temp; /用定義的數(shù)據(jù)結(jié)構(gòu)來定義一個數(shù)組和一個變量int i, j, n, m;int p100; int seek(int x) /用來找出當(dāng)前端點所在集合編號if(px=x) return x;elsereturn px=seek(px);Int Kruskal()int x, y,k=0;for(i=0;i<100;i+) pi=i; for(i=0;i<m;i+) x=seek(edgek.from); /找出當(dāng)前邊兩個端點所在集合編號y=seek(edgek.to); if(x!=y) /如果在不

4、同集合，合并printf("(%d, %d): %dn",edgek.from, edgek.to, edgek.weight); /輸出這時的邊的端點和權(quán)值px=y;k+; return 0;int main()printf("Please input the number of the nodes and edges:n");scanf("%d%d",&n,&m); /輸入有n個節(jié)點m條邊printf("Please input the edges and its weight:n");for(

5、i=0;i<m;i+)scanf("%d%d%d",&edgei.from, &edgei.to, &edgei.weight); /輸入每一條邊的起點、終點和權(quán)值for(i=0;i<m-1;i+) /對邊的權(quán)值進(jìn)行從小到大的排列for(j=i+1;j<m;j+)if(edgei.weight>edgej.weight)temp=edgei;edgei=edgej; edgej=temp;printf("The minimum spanning tree is:n");Kruskal(); /調(diào)用Krusk

6、al算法return 0;其中運用seek函數(shù)找出當(dāng)前端點所在集合編號。運用Kruskal函數(shù)來實現(xiàn)求出最小生成樹的邊，并且依次輸出。在主函數(shù)中將各個邊按照權(quán)值的大小由小到大排序。六、輸入和輸出及結(jié)果的分析程序要求先輸入結(jié)點個數(shù)以及邊的個數(shù)，然后再依次輸入各邊的起點終點以及權(quán)值。輸出時則是輸出最小生成樹的邊的起點終點和權(quán)值。測試用例一：老師的用例。我們應(yīng)該輸入：8 ，13 然后輸入1 2 3，2 3 2，3 8 3，8 7 2，7 6 2，6 1 2，1 4 1，25 2，5 3 4，2 7 3，4 7 2，5 7 1其輸入如圖：其輸出如圖：測試用例二：輸入5 8 ；然后輸入1 2 1，2 3 2，3 4 2，4 5 3，5 1 2，1 4 3，5 2 1，2 4 2，如圖所示：輸出也是如下圖所示：經(jīng)過計算可以得知程序輸出