生成樹實驗報告

篇一：最小生成樹實驗報告

北京理工大學軟件學院

一、實驗目的

1. 通過上機程序，進一步加深對最小生成樹的理解。 2. 掌握Kruskal算法。

3. 學會用程序解決離散數學中的問題。 4. 增強我們編寫程序的能力。

二、實驗內容

求帶權無向聯通平面圖的最小生成樹

三、實驗環境

我的實驗依舊是在VC6.0實驗環境下完成的，而所設計的程序也在這個環境下通過瞭編譯，運行和測試。

四、實驗原理和實現過程

利用Kruskal算法求最小生成樹，原理如下： 1. 選取最小權邊e1，置邊數j?1. 2. i=n-1結束，否則轉c。

3. 設已經選擇的邊為e1,e2,……，ei,在G中選取不同於e1,e2,……ei的邊，

使｛e1,e2,……，ei,ei+1｝中無回路且ei+1是滿足此條件的最小邊。 4. i?i+1，轉b。

根據這個，還有以下思路：

由G生成的最小生成樹T所包含的邊的集合 1．按非降序權重將E中的邊排序 2．建立n個單元素集每個頂點一個) 3．最小生成樹的邊集合T初始為空 4 .while |T|<n-1

5.令e(x,y)為E中的下一條邊

6. if包含x的集合不是與包含y的集合不是同一個集合 then 7.將e(x,y)加入到T

8.將包含x的集合和包含y的集合合並 9.end if

10.end while

五、實驗源代碼及分析