軟件綜合實習報告

　 題目：最小生成樹算法

　院（系）：

　計算機學院

　 專

　業(yè)：

　計算機科學與技術

　姓

　名：

　班級學號：

　2012 年 9 月 12 日

　目錄 一 ． 系統(tǒng)需求分析與總體設計

　............................................................................ 1

　1.1 需求分析 ……………………………………………………………………………………………………………… 1

　1.1.1 問題描述…………………………………………………………………………………………………………1

　1.1.2 問題分析…………………………………………………………………………………………………………1

　1.1.3 方案選擇…………………………………………………………………………………………………………1

　 1.1.4 開發(fā)平臺…………………………………………………………………………………………………………2

　 1.2 系統(tǒng)總體設計 ……………………………………………………………………………………………………. 2

　二 ． 詳細設計與系統(tǒng)實現

　....................................................................................... 2

　2.1 Prime 算法動態(tài)演示模 ……. ……………….……………………………………………………………. 2

　 2.1.1 基本思想…………………………………………………………………………………………………………2

　2.1.2 設計與實現……………………………………………………………………………………………………..3

　 2.2

　 Kruskal 算法動態(tài)演示模塊 ………………………………………………………………………. 4

　 2.2.1 基本思想…………………………………………………………………………………………………………4

　2.2.2 設計與實現………………………………………………………………………………………………………4

　 2.3

　并查集實現 kruskal 算法動態(tài)演示模塊 ……………………………………………….. 4

　 2.3.1 基本思想…………………………………………………………………………………………………………5

　2.3.2 設計與實現………………………………………………………………………………………………………5

　 2.4 深 度優(yōu)先搜索實現 Kruskal 算法動態(tài) 演示模塊 ………………………………. 6

　 2.4.1 基本思想…………………………………………………………………………………………………………6

　2.4.2 設計與實現………………………………………………………………………………………………………7

　 2.5

　廣度優(yōu)先搜索實現 Kruskal 算法動態(tài)演示模塊 ………………………………. 7

　 2.5.1 基本思想…………………………………………………………………………………………………………7

　2.5.2 設計與實現………………………………………………………………………………………………………8

　 2.6 畫圖模塊 ……………………………………………………………………………………………………………….. 8

　三 ．系統(tǒng)測試

　.................................................................................................................. 9

　3.1 測試數據 ……………………………………………………………………………… 9

　3.2Primme 的測試結果 ………………………………………….…………………… 9

　3.2Kruskal 算法的測試結果 ………………………………………….………..…. 10

　3.3 并查集實現Kruskal 算法的測試結果 ……………………………………. 10

　3.4 深度優(yōu)先搜索實現Kruskal 算法的測試結果 …………………………. 11

　3.5 廣度優(yōu)先搜索實現Kruskal 算法的測試結果 …………………………. 11

　3.6 效率分析 ……………………………………………………………………………. 12

　四 ． 總結

　........................................................................................................................... 12

　參考資料 ……………………………………………………………………………………………………………………. 13

　一． 系統(tǒng)需求分析與總體設計 1 1.1 需求分析

　1.1.1 問題描述 在一個具有幾個頂點的連通圖 G 中，如果存在子圖 G" 包含 G 中所有頂點和一部分邊，且不形成回路，則稱 G" 為圖 G 的生成樹，代價最小生成樹則稱為最小生成樹（Minimal Spanning Tree）。

　許多應用問題都是一個求無向連通圖的最小生成樹問題。例如：要在 n 個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同；另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。

　基本的要求是實現兩種算法：通過實現Kruskal算法和Prim算法來得到圖的最小生成樹。并對兩種算法進行分析和比較。較高的要求是在邊通分量的查詢與合并的過程中，采用廣度優(yōu)先搜索算法（Breadth First Search）、深度優(yōu)先搜索算法(Depth First Search)和并查集（Union-Find Set）這三種方法，并進行分析和比較算法時間復雜度。

　測試數據如下：

　圖（1）

　1.1.2 問題分析 通過問題的描述，可知這一道題目主要涉及，面向對象的分析與設計，數據結構和算法。通過這些利用知識實現 Kruskal 算法和 Prim 算法從而得到圖的最小生成樹。除此之外，在最小生成樹的求解過程中會對邊通分量進行查詢和合并，由題可知要對邊通分量進行查詢和合并要使用廣度優(yōu)先搜索算法（Breadth First Search）、深度優(yōu)先搜索算法(Depth First Search)和并查集（Union-Find Set）這三種方法。

　為了更好、更生動的表示這些算法的運算過程，在這里如果使用動態(tài)顯示算法的求解過程將會是最好的選擇。對于不同的算法其求解最小生成樹時運算的效率是不同的，因此還需要對各種算法時間復雜度進行分析和比較，從而更加深入的理解算法，從而方便我們在不同的場合采用不同的實現算法。

　1.1.3 方案選擇 通過對題目的分析，對于如何將廣度優(yōu)先搜索算法（Breadth First Search）、深度優(yōu)先搜132 5 4 6 5 6 5 2 4 4 7

　3 1 7 1

　索算法(Depth First Search)和并查集（Union-Find Set）這三種方法運用到對邊通分量進行查詢和合并中有不同的結合方法。在這里我選擇了將這三種搜索算法融合到 Kruskal 算法，因為我覺得在 Kruskal 算法對邊通分量進行查詢和合并中使用這三種方法更合理且更容易實現，因此也實現了將這三種搜索算法融合到 Kruskal 算法從而實現對圖的最小生成樹的查找。

　對于運用圖形學的知識實現算法的動態(tài)運行效果�？梢灾�道使用 MFC 通過單文檔畫圖來實現算法動態(tài)顯示運行效果或者使用對話框來實現算法動態(tài)顯示運行效果，為了方便起見，我選擇的是通過 MFC 建立單文檔來實現這一效果。

　1.1.4 開發(fā)平臺 使用的系統(tǒng)是 Windows07 ， 開發(fā)工具 VC++6.0 2 1.2 系統(tǒng)總體設計

　由于這是對圖進行相關的操作，因此涉及圖的存儲問題，在這里使用的是鄰接矩陣這一數據結構來實現圖的存儲。在對圖進行相關操作尋找最小生成樹時，得到的生成樹中的邊采用的是結構體的存儲方式，在實現的過程中相關變量和數據的存儲也主要通過數組、結構體來實現了。

　在深度優(yōu)先搜索算法（Breadth First Search）中使用了棧這一數據結構來實現邊的連通分量的查詢，對廣度優(yōu)先搜索算法(Depth First Search)的實現使用了隊列這一數據結構，這里的隊列和棧都是通過編程實現。

　這里主要分為六個模塊，即 prime 算法模塊、kruskal 算法模塊、用并查集實現 kruskal算法的模塊、kruskal 算法和深度優(yōu)先搜索算法結合的模塊、kruskal 算法和廣度優(yōu)先搜索算法結合的模塊以及畫圖操作的相關模塊。設計與實現中由于所體現的重點不同，因此下面的說明主要圍繞著此題的重點，即最小生成樹的生成過程。

　對于最小生成樹生成過程中邊相關變量的存儲均是通過定義一個邊（edge）的結構體變量進行存儲的，而關于點的存儲則是通過定義數組進行相應的存儲，由于不同的實現方法采用的初始值不一樣，因此使用的數組會有所不同。

　對于算法運行時的動態(tài)顯示運行過程這一要求主要通過將相關的畫圓、畫線等相關畫圖的操作扦插到相關的算法中，在算法的運行過程中再通過對相關條件的判斷從而決定是否執(zhí)行畫圓、畫線等操作。在這些算法運行過程中實現的畫圖操作主要通過調用一個公用的函數進行畫圖的相關操作。

　二． 詳細設計與實現 e 2.1 Prime 算法動態(tài)演示模塊

　2.1.1 基本思想

　 Prime 算法的基本思想是以圖中的某一個頂點作為起始頂點，然后從起始頂點出發(fā)不斷 的從還沒有遍歷到的頂點中選擇與已經遍歷到的頂點存在之間權值最小邊的頂點，并將新遍歷的點不斷的添加到已經遍歷的頂點集合中。通過這樣的一個遍歷過程與畫圖的相關操作結合來實現最小生成樹生成過程的動態(tài)演示。

　 對于無向連通圖 G（V,E），在 prime 算法中，將圖 G 頂點集合分為兩個集合 V1（G）和V2（G），V1（G）用來存儲當前已經遍歷到的頂點，即最小生成樹中的頂點 V(MST)，V2（G）

　用來存儲還沒有遍歷到的頂點。對于已經選擇的頂點之間的邊存儲在最小生成樹的邊的集合中 E(MST)。

　Prime 算法的具體過程如下：

　設最小生成樹中點的集合 V(MST)和邊的集合 E(MST)的初態(tài)均為空。首先從圖 G 的頂點 集 V(G)中任選一個頂點，把它加到最小生成樹 MST 的頂點集 V(MST)中。然后，依次選出 n-1條符合以下條件的邊(vi,vj)。

�。�1）(vi,vj)?E(G)，v 是 V(MST)的頂點，而 vj 是還未加入 V(MST)的頂點。此時(vi,vj) 一定均未加入 E(MST)。通過判斷先找出所有這樣的邊 。

�。�2）(vi,vj)是關聯于 V(MST)中頂點的邊中權值最小的邊。選出滿足該條件的邊，將

　 vj 加入 V(MST)，(vi,vj)加入 E(MST) ，之后畫出相應的邊和新添加進去的頂點。

　下面主要通過題目中給出的例子（如圖 1）對 prime 算法進行詳細的解析：

�。�1）將 1 作為起始頂點添加到 V(MST)，找到與之相連的符合條件的邊(v1,v2)，將權值為 5 的邊添加到 E(MST)中，并將頂點 2 添加到 V(MST)中并畫出此邊。

�。�2）集合 V(MST)此時已經有兩個頂點了，即 1、2，找到與之相連的符合條件的邊(v2,v3) 將權值為 1 的邊添加到 E(MST)中，并將頂點 3 添加到 V(MST)中并畫出此邊。

�。�3）集合 V(MST)此時已經有三個頂點了，即 1、2、3，找到與之相連的符合條件的邊(v2,v4)將權值為 2 的邊添加到 E(MST)中，并將頂點 4 添加到 V(MST)中并畫出此邊。

�。�4）集合 V(MST)此時已經有四個頂點了，即 1、2、3、4，找到與之相連的符合條件的邊(v4,v5)將權值為 3 的邊添加到 E(MST)中，并將頂點 5 添加到 V(MST)中并畫出此邊。

�。�5）集合 V(MST)此時已經有五個頂點了，即 1、2、3、4、5，找到與之相連的符合條件的邊(v4,v6)將權值為 4 的邊添加到 E(MST)中，并將頂點 6 添加到 V(MST)中并畫出此邊。

�。�6）集合 V(MST)此時已經有六個頂點了，即 1、2、3、4、5、6，找到與之相連的符合條件的邊(v6,v7)將權值為1的邊添加到E(MST)中，并將頂點7添加到V(MST)中并畫出此邊。

　至此圖 G 中所有的點均已添加到了 V(MST)，最小生成樹生成完畢，其權值為 16。

　2.1.2 設計與實現 對于 prime 算法的動態(tài)演示，主要是關乎兩個函數的實現一個是畫圖函數的實現，另 外一個就是如何判斷何時進行畫圖操作并進行相關操作的畫圖函數，在這里主要通過兩個函數實現一個是與 Kruskal 算法動態(tài)實現的公用的畫圖操作函數，另外一個就是 prime 算法尋找最小生成樹的實現。這里僅給出語言描述的實現過程，源代碼的實現在后面的附錄中將會給出。

　Prime 算法的設計與實現 如下所述：

　（1）對所畫區(qū)域刷新。

　（2）

　MST 頂點初始值={序號為 0 的頂點}，其邊所在的結構體數組 E[n-1]的值也為空。lowCost的初始值為鄰接矩陣中第0行的值，這樣初始時lowCost中就存放了從集合V(MST)中頂點 0 到集合 V(G)－V(MST)中各個頂點的權值 。

　（3）循環(huán) n-1 次 2.1 從 lowCost 中尋找具有最小權值的邊。根據 lowCost 的定義，這樣的邊其一個頂點必然為集合 V(MST)中的頂點，其另一個頂點（設第 k 個頂點）必然為集合 V(G)－V(MST)中的頂點 ，將相應的邊添加到 E[n-1]中。

　2.2 存第 k 個頂點的數據和相應邊的權值到 MST 中，并將 lowCost[k]置為-1，表示第k 個頂點從集合 V(G)－V(MST)加入了集合 V(MST)中

　2.3 當第 k 個頂點加入到集合 V(MST)后，若存在一條邊(k,j)，其中 k 是集合 V(MST)的頂點，j 是集合 V(G)－V(MST)的頂點，且邊(k,j)權值較原先 lowCost[j]的代價更小，則用這個權值修正原先 lowCost[j]中的權值。

　2.4 當最小生成樹生成完畢時，則調用 Draw（E）函數畫出生成的過程。

　l 2.2 Kruskal 算法動態(tài)演示模塊

　2.2.1 基本思想 Kruskal 算法通常是在已知 V(MST)=V(G)，E(MST)的初態(tài)為空時對圖 G 進行相關處理的到最小生成樹的。首先將圖中所有邊按權值遞增順序排列，依次選定取權值較小的邊，但要求后面選取的邊不能與前面選取的邊構成回路，若構成回路，則放棄該條邊，再去選后面權值較大的邊。每次挑選邊成功了即畫出此邊。在 n 個頂點的圖中，選夠 n-1 條邊即可。具體如下：

�。�1）

　構造一個只有 n 個頂點沒有邊的非連通圖 T，圖中的每個頂點為一個連通分量。

�。�2）

　在原圖 G 中的邊中選擇具有最小權值的邊，若該邊的兩個頂點落在不同的連 通分量上，則將此邊加入到 T 中；否則，則將此邊舍去（此后永不選入此邊），重新選擇一條權值最小的邊并進行畫圖的操作處理。

�。�3）如此反復下去，直到所有頂點在同一個連通分量上為止。

　下面主要通過題目中給出的例子（如圖 1）對 kruskal 算法進行詳細的解析：

�。�1）在圖 G 的邊的集合 E 中按存儲次序選擇權值最小的邊，即（2,3）由于邊（2,3）在（6,7）前面存儲，所以此處選擇的邊（2,3）并畫出此邊，其權重為 1。

�。�2）在圖 G 的邊的集合 E 中按存儲次序選擇權值最小的邊，即（6,7）由于邊（6,7）在（2,3）后面存儲，所以后選擇邊（6,7）并畫出此邊，其權重為 1。

�。�3）在圖 G 的邊的集合 E 中選擇權值最小的邊（2,4）并畫出此邊，其權重為 2。

�。�4）在圖 G 的邊的集合 E 中選擇權值最小的邊（4,5）并畫出此邊，其權重為 3。

�。�5）在圖 G 的邊的集合 E 中選擇權值最小的邊（4,6）并畫出此邊，其權重為 4。

�。�6）在圖 G 的邊的集合 E 中選擇權值最小的邊（1,2）并畫出此邊，其權重為 5。

　至此通過 kruskal 算法得到最小生成樹及生成過程，其最小生成樹的權值為 16。

　2.2.1 模塊設計與實現 Kruskal 算法的實現主要包含兩個部分，即帶權值的邊的排序和判斷選取的邊的兩個頂點是否屬于同一個連通分量。因此首先將圖 G 的頂點集合 V 分為 n 個等價類，每個等價類包括一個頂點；然后以權值的大小為順序處理各條邊，如果某條邊連接兩個不同等價類的頂點，則這條邊被添加到 MST（選取的邊不與前面選取的邊構成回路），兩個等價類被合并為一個；反復執(zhí)行此過程，直到只剩下一個等價類。

　kruskal 算法的設計與實現如下所述（具體的代碼實現見附錄）：

�。�1）對所畫區(qū)域進行刷新。

�。�2）設置查找到的頂點集合 find[n]所有的值為-1，存儲邊的集合 E[n-1]為空集。

�。�3）判斷找到的邊的數目是否小于頂點的數目減一，即 n-1，如果是則從沒有被選中的邊中選取權值最小的邊，如果放入存儲邊的集合中不構成回路則添加進去，否則舍去此邊。

�。�4）如果不符合（2）中的判斷則不斷的重復直到選取的邊等于 n-1。

�。�5）當最小生成樹生成完畢時，則調用 Draw（E）函數畫出生成的過程。

　3 2.3 并查集實現 l kruskal 算法動態(tài)演示模塊

　2.3.1 基本思想 并查集處理問題的主要思想是在處理時使用搜索與合并運算對相關集合進行處理。最初 把每一個對象看做是一個單元集合，然后依次按順序讀入一個等價對后，將等價對中的兩個元素所在的集合合并。在此過程中不斷的重復使用一個搜索運算，從而確定此元素在哪一個集合中，當讀入一個等價對 A≡B 時，首先檢測 A 和 B 是不是屬于同一個集合，如果是，則不用合并；如果不是，則使用一個合并運算把 A 和 B 合并到同一個集合中，使得這兩個集合中的任意兩個元素都是等價的（依據等價的傳遞性）。

　在此處實現 Kruskal 算法時主要使用并查集對相關頂點進行搜索和合并，從而實現了使用并查集實現 Kruskal 算法。在程序中也實現了并查集的動態(tài)演示，通過 Kruskal 算法調用并查集的函數，在函數中 對相關的頂點信息進行判斷從而實施相應的畫圖操作。

　下面通過題目的例子（如圖 1）對 kruskal 算法利用并查集實現過程中相應集合的變化進行了詳細的解析：

�。�1）最初的集合有 7 個，這 7 個集合中均只有一個元素分別為{1}、{2}、{3}、{4}、{5}、{6}、{7}。畫出初始狀態(tài)。

�。�2）在圖 G 的邊的集合 E 中按存儲次序選擇權值最小的邊，即（2,3）由于邊（2,3）在（6,7）前面存儲，所以此處選擇的邊（2,3）其權重為 1。此時集合變?yōu)閧1}、{2、3}、{4}、 {5}、{6}、{7}。通過判斷畫出發(fā)生改變的集合{2、3}。

�。�3）在圖 G 的邊的集合 E 中按存儲次序選擇權值最小的邊，即（6,7）由于邊（6,7）在（2,3）后面存儲，所以后選擇邊（6,7），其權重為 1。此時集合變?yōu)閧1}、{2、3}、{4}、 {5}、{6、7}。通過判斷畫出發(fā)生改變的集合{6、7}。

�。�4）在圖 G 的邊的集合 E 中選擇權值最小的邊（2,4）并畫出此邊，其權重為 2。此時集合變?yōu)閧1}、{2、3、4}、{5}、{6、7}。通過判斷畫出發(fā)生改變的集合{2、3、4}。

　（5）在圖 G 的邊的集合 E 中選擇權值最小的邊（4,5）并畫出此邊，其權重為 3。此時集合變?yōu)閧1}、{2、3、4、5}、{6、7}。通過判斷畫出發(fā)生改變的集合{2、3、4、5}。

　（6）在圖 G 的邊的集合 E 中選擇權值最小的邊（4,6）并畫出此邊，其權重為 4。此時集合變?yōu)閧1}、{2、3、4、5、6、7}。通過判斷畫出發(fā)生改變的集合{2、3、4、5、6、7}。

�。�7）在圖 G 的邊的集合 E 中選擇權值最小的邊（1,2）并畫出此邊，其權重為 5。此時集合變?yōu)閧1、2、3、4、5、6、7}。通過判斷畫出發(fā)生改變的集合{1、2、3、4、5、6、7}。

　至此 kruskal 算法利用并查集查找、合并的過程結束，通過 kruskal 算法得到最小生成樹及生成過程，其最小生成樹的權值為 16。

　2.3.2 設計與實現 Kruskal 算法利用并查集實現查找、合并的設計與實現也是首先選擇權值最小的邊，其次是利用并查集來對所要選擇的那些頂點進行查找、合并。在 Kruskal 使用并查集時首先對其進行邊集合的排序，接著利用并查集對圖 G 中的頂點進行初始化，每一個頂點當做一個集合，同時給其一個相關的變量標志其集合中頂點的數目；然后利用并查集判斷此時的頂點所在集合是不是相同，如果不相同則合并這兩個頂點所在的集合。

　并查集的實現主要包含三個方面，即并查集的初始化、查找和集合的合并，下面主要介紹并查集這三個過程的設計與實現。

�。�1）對所畫區(qū)域進行刷新。

�。�2）初始化過程：為了方便并查集的描述與實現，通常把先后加入到一個集合中的元素表示成一個樹形結構，并用根節(jié)點來代表這個集合。這里定義一個 parent[n]的數組，parent[i]中存儲的就是結點 i 所在的樹中的結點 i 父親結點的序號，并查集的初始化中所有的

　結點的 parent 值均為-1，即每個結點就是根節(jié)點，只包含它本身這一個元素。

�。�3）查找：主要是查找并返回結點 i 所屬集合的根節(jié)點。在此函數中如果只靠一個循環(huán)來得到結果，則對于合并中得到的層次比較深的集合，查找會很費時。這里通過壓縮路徑的方法來加快后續(xù)的查找速度，主要是通過增加一個 while 循環(huán)，每次都把從結點 i 到集合根節(jié)點的路徑上經過的結點直接設置為根結點的子結點。

�。�4）合并：兩個集合合并時，任何一方均可作為另一方的子孫。在這里采用的是加權合并，即把兩個集合中元素個數少的根結點作為元素個數多的根節(jié)點的子結點。這樣處理可以減少樹中深層次元素的個數，減少后續(xù)查找時間。在每一次的合并過程結束時，將會畫出合并之后的集合。

　2.4 深度優(yōu)先搜索實現 l Kruskal 算法動態(tài)演示模塊

　2.4.1 基本思想 深度優(yōu)先搜索主要是在圖的遍歷中使用此方法對整個圖進行遍歷來訪問整個圖中所有節(jié)點的一種遍歷方法。通常是利用遞歸來實現圖中結點的遍歷。其基本思想是：對于一個無向連通圖，從某一個起始結點 vi 出發(fā)，訪問與它相連的一個結點 vj，且 vi、vj 這兩個結點之間的邊（vi、vj）是所有以 vi 為連接結點的邊中權值最小的；然后再從 vj 出發(fā)尋找與 vj 相連的頂點，且它們之間的邊是所有以 vi 為連接結點的邊中權值最小的，不斷的重復直到找到訪問完所有的結點為止。

　在這個算法的實現過程中，邊通分量的查找雖然是深度優(yōu)先搜索為主，但是是以最小生成樹的的生成過程為主，因此這里所采用的畫圖操做運行的情況和使用一般的方法實現kruskal 算法的運行過程是一樣的，在這里不再給予詳細的說明，如有必要則可以參照 kruskal的生成最小生成樹的過程。對于深度優(yōu)先搜索方法的實現這里使用的方法是通過利用棧這一數據結構來實現的。下面僅給出在邊已經通過權值大小進行排序之后，邊通分量的查找的過程和查找之后集合的合并情況 （1）得到圖 G 中最小權值的邊（2,3），因為（2,3）排在（6,7）的前面，所以先判斷它的兩個結點，判斷點 2 和點 3 是否已經訪問過了，由于數組 check 中相應的值為 0，說明沒有被訪問過，因此合并這兩個結點為一個集合{2、3}。同時通過深度優(yōu)先搜索對這兩個結點分別進行判斷及標記已經訪問過了。

�。�2）繼續(xù)向下查找得到邊（6,7），判斷點 6 和點 7 是否已經訪問過了，由于數組 check中相應的值為 0，因此合并這兩個結點，得到新的集合{6、7}。同時通過深度優(yōu)先搜索對這兩個結點分別進行判斷及標記已經訪問過了。

　 （3）繼續(xù)向下查找得到邊（2,4），判斷點 2 和點 4 是否已經訪問過了得知點 2 已經被訪問過了，點 4 沒有，因此得到新的集合{2,、3、4}。同時通過深度優(yōu)先搜索對著兩個結點分別進行判斷是否需要標記，可知點 4 此時被標記訪問過了。

　 （4）繼續(xù)向下查找得到邊（4,5），判斷點 4 和點 5 是否已經訪問過了得知點 4 已經被訪問過了，點 5 沒有，因此得到新的集合{2,、3、4、5}。同時通過深度優(yōu)先搜索對著兩個結點分別進行判斷是否需要標記，可知點 5 此時被標記訪問過了。

�。�5）繼續(xù)向下查找得到邊（4,6），判斷點 4 和點 6 是否已經訪問過了得知點 4 已經被訪問過了，點 6 沒有，因此得到新的集合{2,、3、4、5、6、7}。同時通過深度優(yōu)先搜索對著兩個結點分別進行判斷是否需要標記則知均不需要。

�。�6）繼續(xù)向下查找得到邊（5,6），判斷點 5 和點 6 是否已經訪問過了得知已經被訪問過了，因此得到不進行集合的合并，繼續(xù)向下查找相應的邊。

�。�7）繼續(xù)向下查找得到邊（1,2），判斷點 1 和點 2 是否已經訪問過了得知點 2 已經被

　訪問過了，點 1 沒有，因此得到新的集合{1、2,、3、4、5、6、7}。同時通過深度優(yōu)先搜索對著兩個結點分別進行判斷是否需要標記，可知點 1 此時被標記訪問過了。

　至此通過利用深度優(yōu)先搜索進行邊通分量查詢的 kruskal 算法運行完畢，通過對比可知和使用普通的查找算法得到的運行結果是一致的。

　2.4.2 設計與實現 在這里采用 Kruskal 算法得到最小生成樹的過程中，在對邊連通分量的查詢時使用了深度優(yōu)先搜索的方法來查詢當前得到的具有最下權值的邊的兩個頂點是不是已經存在于被訪問過的結點的集合中，如果是的則進行下一次查詢，否則的話則將沒有訪問過的結點加入已經訪問過的結點的集合中。

　深度優(yōu)先搜索的實現主要利用棧這一數據結構來實現。因此主要包含兩個方面，即棧這一數據結構中相關函數的設計與實現，以及如何實現深度優(yōu)先搜索算法判斷變量通分量的設計與實現。由于對棧已經比較熟悉，在這里僅作簡要的說明。

　（1）棧：

　這里使用到的與棧相關的操作主要有棧中數據的初始化 StackInitiate、將數據壓入棧的操作 StackPush、將數據彈出棧的操作 StackPop、判斷棧是否為空的操作StackNotEmpty 和得到棧頂元素的操作 StackTop。

�。�2）查找與合并：在深度優(yōu)先搜索中首先判斷是否需要標記此節(jié)點，如果需要標記此節(jié)點則將此節(jié)點標記為以訪問過，并添加到已經訪問過的結點的集合中，并將相應的邊存入E[]中；如果是要進行判斷兩個結點是不是都已經訪問過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結點所在的集合中是否有另一個結點，如果存在則舍棄當前所選擇的邊，否則選擇此邊為最小生成樹的一邊。

　下面給出 kruakal 算法利用深度優(yōu)先搜索進行邊連通分量查詢和合并從而得到最小生成樹的的設計與實現步驟：

�。�1）對所畫區(qū)域進行刷新。

�。�2）對已經排好序的邊進行選擇，對沒有訪問過的最小權值的邊的兩個結點進行判斷，檢查是否已經被訪問過了，如果有一個沒有被訪問過，則將和此邊相應的頂點進行深度優(yōu)先搜索的判斷之后進行標記，同時存儲所選擇的這個邊和相應的頂點。

�。�3）如果都已經被訪問過了，則利用深度優(yōu)先搜索判斷這兩個節(jié)點是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進行標記，并畫出此邊和相對應的點。

�。�4）選擇下一條沒有被訪問過的邊重新進行（1）、（2）的判斷，直到所有的頂點均已被訪問過且在同一個集合中，即已經添加到了最小生成樹中則最小生成樹生成完畢。

　（5）當最小生成樹生成完畢時，則調用 Draw（E）函數畫出生成的過程。

　2.5 廣度優(yōu)先搜索實現 l Kruskal 算法動態(tài)演示模塊

　2.5.1 基本思想 廣度優(yōu)先搜索主要是在圖的遍歷中使用此方法對整個圖進行遍歷來訪問整個圖中所有節(jié)點的一種遍歷方法。通常是利用隊列這一數據結構來實現圖中結點的遍歷。其基本思想是：對于一個無向連通圖，從某一個起始結點 vi 出發(fā)，依次訪問與它相連的所有未訪問過的結點 vj1、vj2……vjn，然后在順序訪問 vj1、vj2……vjn 的所有還未訪問過的鄰接頂點；再從這些鄰接頂點出發(fā)，再訪問它們的所有未訪問過的鄰接頂點，……，不斷重復直到圖 G 中所有的頂點都被訪問過為止。

　kruskal 算法利用廣度優(yōu)先搜索進行邊通分量的查詢和合并的的實現過程中，邊通分量的查找和合并雖然是廣度優(yōu)先搜索為主，但是總體是以最小生成樹的的生成過程為主，因此

　這里所采用的畫圖操做運行的情況和使用一般的方法實現 kruskal 算法的運行過程是一樣的，在這里不再給予詳細的說明，如有必要則可以參照 kruskal 的生成最小生成樹的過程。對于廣度優(yōu)先搜索方法的實現這里使用的方法是通過利用隊列這一數據結構來實現的。

　這里采用的廣度優(yōu)先搜索主要是用來檢索邊的鄰接頂點是不是在同一個集合中，由于使用 kruskal 算法時最初已經對邊進行了一個排序，所以每一次所選用的邊和通過廣度優(yōu)先搜索對鄰接頂點進行判斷的結果是一樣的，在這里不再給予詳細的說明，kruskal 算法結合廣度優(yōu)先搜索具體的運算過程和 kruskal 算法結合深度優(yōu)先搜索的運算過程是一樣的，在這里不再列出。由于本題的重點是最小生成樹的生成，在這里不再給出廣度優(yōu)先搜索具體的搜索過程。

　2.5.2 設計與實現 在這里采用 Kruskal 算法得到最小生成樹的過程中，在對邊連通分量的查詢時使用了廣度優(yōu)先搜索的方法來查詢當前得到的具有最下權值的邊的兩個頂點是不是已經存在于被訪問過的結點的集合中，如果是的則進行下一次查詢，否則的話則將沒有訪問過的結點加入已經訪問過的結點的集合中。

　廣度優(yōu)先搜索的實現主要利用隊列這一數據結構來實現。因此主要包含兩個方面，即隊列這一數據結構中相關函數的設計與實現，以及如何實現深度優(yōu)先搜索算法判斷變量通分量的設計與實現。由于對隊列已經比較熟悉，在這里僅作簡要的說明。

�。�1）隊列：

　這里使用到的與隊列相關的操作主要有棧中數據的初始化 QueueInitiate、將數據存入隊列的操作 QueueAppend、將數據從隊列中刪除的操作 QueueDelete、判斷隊列是否為空的操作 QueueNotEmpty。

　（2）查找與合并：在廣度優(yōu)先搜索中首先判斷是否需要標記此節(jié)點，如果需要標記此節(jié)點則將此節(jié)點標記為以訪問過，并添加到已經訪問過的結點的集合中；如果是要進行判斷兩個結點是不是都已經訪問過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結點所在的集合中是否有另一個結點，如果存在則舍棄當前所選擇的邊，否則選擇此邊為最小生成樹的一邊。

　下面給出 kruakal 算法利用廣度優(yōu)先搜索進行邊連通分量查詢和合并從而得到最小生成樹的的設計與實現步驟：

�。�1）對所畫區(qū)域進行刷新。

�。�2）對已經排好序的邊進行選擇，對沒有訪問過的最小權值的邊的兩個結點進行判斷，檢查是否已經被訪問過了，如果有一個沒有被訪問過，則將和此邊相應的頂點進行廣度優(yōu)先搜索的判斷之后進行標記，同時畫出所選擇的這個邊和相應的頂點。

�。�3）如果都已經被訪問過了，則利用廣度優(yōu)先搜索判斷這兩個節(jié)點是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進行標記，并畫出此邊和相對應的點。

�。�4）選擇下一條沒有被訪問過的邊重新進行（1）、（2）的判斷，直到所有的頂點均已被訪問過且在同一個集合中，即已經添加到了最小生成樹中則最小生成樹生成完畢。

�。�5）當最小生成樹生成完畢時，則調用 Draw（E）函數畫出生成的過程。

　2.6 畫圖模塊

　這一模塊主要是實現如何動態(tài)的演示程序運行的效果，主要涉及的有三個方面，第一個方面是使用不同的算法實現最小生成樹的繪制過程，第二個方面是畫圖區(qū)域的刷新，第三個方面是并查集的繪制過程。

　對于最小生成樹的繪制過程有一個函數承擔，主要是實現程序在調用 prime 算法、kruskal 算法、深度優(yōu)先搜索實現的 kruskal 算法和廣度優(yōu)先搜索實現的 kruskal 算法的過程中

　相關運行過程的繪制，此處主要通過判斷最小生成樹中所存儲的邊來進行繪制。

　畫圖區(qū)域的刷新主要是為了實現同一塊區(qū)域可以畫多次不同的運行過程，有兩個函數承擔。由于并查集的繪制和最小生成樹的繪制沒有太大的關聯，因此在這里采用了單獨繪制并查集實現 kruskal 算法中并查集的合并過程。

　三． 系統(tǒng)測試 3.1 測試數據

　 圖（2）

　上圖是利用程序直接得到的原圖形，此測試數據中有七個頂點，有十條邊。通過這些可知其生成的最小生成樹只能有七個頂點、六條邊。通過觀察可知這六條邊應為（2,3）、（6,7）、（2,4）、（4,5）、（4,6）、（1,2）。

　3.2Primme 的測試結果

　 圖（3）

　通過上面 prime 算法的解析結果和運行結果發(fā)現其運行結果與分析中應該得到的結果是一致的，由于畫圖和判斷中采用的有延長運行時間的函數，因此這里只通過理論分析得出prime 算法的運行效率。

　 3.2Kruskal 算法的測試結果

　 圖(4)

　 通過上面 kruskal 算法的解析結果和運行結果發(fā)現其運行結果與分析中應該得到的結果是一致的，由于畫圖和判斷中采用的有延長運行時間的函數，因此這里只通過理論分析得出kruskal 算法的運行效率。

　3.3 并查集實現 Kruskal 算法的測試結果

　圖(5)

　 此圖中首先給出了最初集合的狀況，緊接著給出了每一次進行邊通分量查找合并過程中發(fā)生變化的集合的狀況。通過此圖并結合上面對并查集的分析可知與其運行一致。

　3.4 深度優(yōu)先搜索實現 Kruskal 算法的測試結果

　圖（6）

　在這里沒有對深度優(yōu)先搜索的過程給予動態(tài)顯示，主要是模擬了深度優(yōu)先搜索實現kruskal 算法的過程，也即最小生成樹的生成過程。通過對比前兩種 kruskal 算法的實現過程可知其運行是一致的。

　3.5 廣度優(yōu)先搜索實現 Kruskal 算法的測試結果

　圖（7）

　 通過與其他方法實現 kruska 算法進行對比，可知結果是一致的。由此也說明一個問題，即對于使用不同的方法來實現這一算法，改變的只是其效率，但是整體的運行情況是不會發(fā)生改變的。因此在實現的過程中應該盡量選擇效率比較高的方法來實現算法。

　對于廣度優(yōu)先搜索每個頂點至多進一次隊列。遍歷圖的過程實質上是通過邊或弧找鄰接 點的過程。因此廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅在于對頂點訪問的順序不同。對于使用 kruskal 算法和深度優(yōu)先搜索結合的算法，對邊的遍歷至多是 e 次，故其總代價為 O(n^2*e)。

　3.6 效率分析 Prime 算法實現的函數主要是一個兩重循環(huán)，其中每一重循環(huán)的次數均為頂點個數 n，所以該算法的時間復雜度為 O(n^2)。

　Kruskal 算法的時間復雜度與選取的排序函數有關，這里采用的是不是對其進行排序 而是在每一次循環(huán)中找余下的邊中權值最小的邊，找到最小的邊之后將對其相應的點進行標記，已知點的個數為 n 邊的個數為 e，所以它的時間復雜度為最壞的情況下為 O(e^2)，如果邊已經很有序的話，也就是最好的情況下的時間復雜度為 O(n^2)。

　Kruskal 運用并查集實現中使用了路徑壓縮，Find 和 UNION 函數幾乎是常數假設可能對幾乎所有邊都判斷過了，則最壞情況下算法時間代價為 O(eloge)，即堆排序的時間通常情況下只找了接近頂點數目那么多邊的情況下，MST 就已經生成，時間代價接近于 O(nloge)

　 深度優(yōu)先搜索對每一條邊處理一次，每個頂點訪問一次以鄰接矩陣作存儲結構：處理所 有的邊需 O(n n^2)的時間 ，故總代價為 O(n^2)。對于使用 kruskal 算法和深度優(yōu)先搜索結合的算法，對邊的遍歷至多是 e 此故其總代價為 O(n^2*e)。

　四． 總結 這個題目的主要要求是通過使用不同的算法求出圖的最小生成樹，并且通過畫圖動態(tài)的顯示出來其不同的算法在求解最小生成樹時的運行步驟。在我的程序中已經實現了對給出的這一例子使用 Prime 算法、Kruskal 算法求解最小生成樹的運算過程的動態(tài)顯示，除此之外，對于還實現了在邊通分量的查詢與合并的過程中，采用廣度優(yōu)先搜索算法（Breadth First Search）、深度優(yōu)先搜索算法(Depth First Search)和并查集（Union-Find Set）三種方法來實現對此例中圖的最小生成樹的求解，主要是將這三種搜索方法與 Kruakal 結合來實現對最小生成樹的求解。

　 雖然通過例子實現了使用題目中要求的算法來求解最小生成樹，但是沒能實現給用戶一個友好的界面來方便求解各種不同的圖的最小生成樹，只能通過改變程序里面相關的存儲變量來實現對不同圖的最小生成樹的求解。同時由于對于作圖這方面不是很熟練，沒能實現對圖的動態(tài)擴充，所以只能是實現對一定數目，一定邊數的圖的求解。為了我的程序更加完美我會繼續(xù)努力，從而實現圖的動態(tài)擴充，同時讓程序更為簡練。

　 在最初選擇題目的時候，總是覺得自己對使用 MFC 來畫圖這一方面不是很熟悉，擔心自己做不出來。在實現在邊通分量的查詢與合并的過程中，采用廣度優(yōu)先搜索算法（Breadth

　First Search）、深度優(yōu)先搜索算法(Depth First Search)和并查集（Union-Find Set）三種方法來實現對此例中圖的最小生成樹的求解，這一方面最初也是相當的糾結，不知道該從什么方面下手。因為在學習數據結構的時只知道廣度優(yōu)先搜索算法（Breadth First Search）、深度優(yōu)先搜索算法(Depth First Search)是用來遍歷圖的，平時沒有在搜索的過程中使用此種算法，不知道該從何下手，通過老師的講解多多少少悟出了點，之后反復的思考最終通過使用隊列實現了在邊通分量的查詢與合并的過程中，采用廣度優(yōu)先搜索算法（Breadth First Search），通過使用棧實現了在邊通分量的查詢與合并的過程中，深度優(yōu)先搜索算法(Depth First Search)。

　這讓我意識到學習到的知識一定要活用才能創(chuàng)造出更好的方法，只是使用它通常的用途是遠遠不夠的。

　雖然做的時候還是很多都不熟悉，但是我知道如果我不嘗試這去做的話就真的什么也做不出來了。雖然最后做的和自己最初設想的有所差異，但是題目中的要求我都完成了，還是小有成就感的。所以通過這次的實習，讓我認識到只要去嘗試，去努力沒有什么是不可以做的。

　 參考文獻：

　[1]朱戰(zhàn)立，數據結構—使用 c 語言（第四版），電子工業(yè)出版社 2010 年 11 月 [2]王桂平、王衍、任嘉辰，圖論算法理論、實現及應用，北京大學出版社，2011 年 1 月 [3]孫鑫、余安萍，VC++深入詳解，電子工業(yè)出版社 2011 年 5 月

相關熱詞搜索：實習報告 綜合 軟件