【正文】 ??????????????? .2 基 本 思想???????????????????????????????????????? 2 設(shè) 計 與 實現(xiàn)?????????????????????????????????????? ..3 Kruskal 算 法 動 態(tài) 演 示 模塊?? ????????????????????????? .4 基 本 思想???????????????????????????????????????? 4 設(shè) 計 與 實現(xiàn)??????????????????????????????????????? 4 并 查 集 實 現(xiàn) kruskal 算 法 動 態(tài) 演 示 模塊?????????????????? ..4 基 本 思想???????????????????????????????????????? 5 設(shè) 計 與 實現(xiàn)??????????????????????????????????????? 5 深 度 優(yōu) 先 搜 索 實 現(xiàn) Kruskal 算 法 動 態(tài) 演 示 模塊???????????? .6 基 本 思想???????????????????????????????????????? 6 設(shè) 計 與 實現(xiàn)??????????????????????????????????????? 7 廣度優(yōu)先搜索實現(xiàn) Kruskal 算法動態(tài)演示模塊???????????? .7 基 本 思想???????????????????????????????????????? 7 設(shè) 計 與 實現(xiàn)??????????????????????????????????????? 8 畫 圖 模塊?????????????????????????????????????????? ..8 三．系統(tǒng)測試 ..................................................................................................................9 測 試 數(shù)據(jù)?????????????????????????????? 9 的 測 試 結(jié)果???????????????? .???????? 9 算 法 的 測 試 結(jié)果???????????????? .??? ..? .10 并 查 集 實 現(xiàn) Kruskal 算 法 的 測 試 結(jié)果?????????????? .10 深 度 優(yōu) 先 搜 索 實 現(xiàn) Kruskal 算 法 的 測 試 結(jié)果????? ????? .11 廣 度 優(yōu) 先 搜 索 實 現(xiàn) Kruskal 算 法 的 測 試 結(jié)果?????????? .11 效 率 分析?????????????????????????????.12 四．總結(jié) ...........................................................................................................................12 參 考 資料????????????? ??????????????????????????????? .13 一．系統(tǒng)需求分析與總體設(shè)計 需求分析 問題描述在一個具有幾個頂點的連通圖 G 中，如果存在子圖 G包含 G 中所有頂點和一部分邊，且不形成回路，則稱 G為圖 G 的生成樹，代價最小生成樹則稱為最小生成樹（ MinimalSpanningTree）。通過這些利用知識實現(xiàn)Kruskal 算法和 Prim 算法從而得到圖的最小生成樹。 Windows07，開發(fā)工具 VC++系統(tǒng)總體設(shè)計 由于這是對圖進行相關(guān)的操作，因此涉及圖的存儲問題，在這里使用的是鄰接矩陣這一數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)圖的存儲。 二．詳細設(shè)計與實現(xiàn) 模塊 Prime 算法的基本思想是以圖中的某一個頂點作為起始頂點，然后從起始頂點出發(fā)不斷的從還沒有遍歷到的頂點中選擇與已經(jīng)遍歷到的頂點存在之間權(quán)值最小邊的頂點，并將新遍歷的點不斷的添加到已經(jīng)遍歷的頂點集合中。此時 (vi,vj)一定均未加入 E(MST)。 （ 5）集合 V(MST)此時已經(jīng)有五個頂點了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權(quán)值為 4 的邊添加到 E(MST)中，并將頂點 6 添加到 V(MST)中并畫出此邊。 （ 3）循環(huán) n1次 lowCost 中尋找具有最小權(quán)值的邊。具體如下： （ 1） 構(gòu)造一個只有 n 個頂點沒有邊的非連通圖 T，圖中的每個頂點為一個連通分量。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 1,2）并畫出此邊，其權(quán)重為 5。 （ 5）當(dāng)最小生成樹生成完畢時，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權(quán)值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）其權(quán)重為 1。通過判斷畫出發(fā)生改變的集合 { 4}。此時集合變?yōu)?{ 7}。這里定義一個 parent[n]的數(shù)組， parent[i]中存儲的就是結(jié)點i 所在的樹中的結(jié)點 i父親結(jié)點的序號，并查集的初始化中所有的 結(jié)點的 parent值均為 1，即每個結(jié)點就是根節(jié)點，只包含它本身這一個元素。 深度優(yōu)先搜索實現(xiàn) lKruskal算法動態(tài)演示模塊 基本思想深度優(yōu)先搜索主要是在圖的遍歷中使用此方法對整個圖進行遍歷來訪問整個圖中所有節(jié)點的一種遍歷方法。同時通過深度優(yōu)先搜索對這兩個結(jié)點分別進行判斷及標(biāo)記已經(jīng)訪問過了。同時通過深度優(yōu)先搜索對這兩個結(jié)點分別進行判斷及標(biāo)記已經(jīng)訪問過了。這樣處理可以減少樹中深層次元素的個數(shù)，減少后續(xù)查找時間。 （ 1）對所畫區(qū)域進行刷新。通過判斷畫出發(fā)生改變的集合 { 7}。 （ 4）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 2,4）并畫出此邊，其權(quán)重為 2。 下面通過題目的例子（如圖 1）對 kruskal 算法利用并查集實現(xiàn)過程中相應(yīng)集合的變化進行了詳細的解析： （ 1）最初的集合有 7個，這 7個集合中均只有一個元素分別為 {1}、{2}、 {3}、 {4}、 {5}、 {6}、 {7}。 （ 3）判斷找到的邊的數(shù)目是否小于頂點的數(shù)目減一，即 n1，如果是則從沒有被選中的邊中選取權(quán)值最小的邊，如果放入存儲邊的集合中不構(gòu)成回路則添加進去，否則舍去此邊。 （ 4）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,5）并畫出此邊，其權(quán)重為 3。每次挑選邊成功了即畫出此邊。 （ 2） MST頂點初始值 ={序號為 0的頂點 }，其邊所在的結(jié)構(gòu)體數(shù)組 E[n1]的值也為空。 （ 3）集合 V(MST)此時已經(jīng)有三個頂點了，即 3，找到與之相連的符合條件的邊 (v2,v4)將權(quán)值為 2 的邊添加到 E(MST)中，并將頂點 4 添加到 V(MST)中并畫出此邊。然后，依次選出 n1 條符合以下條件的邊(vi,vj)。 對于算法運行時的動態(tài)顯示運行過程這一要求主要通過將相關(guān)的畫圓、畫線等相關(guān)畫圖的操作扦插到相關(guān)的算法中，在算法的運行過程中再通過對相關(guān)條件的判斷從而決定是否執(zhí)行畫圓、畫線等操作。 對于運用圖形學(xué)的知識實現(xiàn)算法的動態(tài)運行效果。較高的要求是在邊通分量的查詢與合并的過程中，采用廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法，并進行分析和比較算法時間復(fù)雜度。雖然最后做的和自己最初設(shè)想的有所差異，但是題目中的要求我都完成了，還是小有成就感的。 雖然通過例子實現(xiàn)了使用題目中要求的算法來求解最小生成樹，但是沒能實現(xiàn)給用戶一個友好的界面來方便求解各種不同的圖的最小生成樹，只能通過改變程序里面相關(guān)的存儲變量來實現(xiàn)對不同圖的最小生成樹的求解。因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅在于對頂點訪問的順序不同。通過此圖并結(jié)合上面對并查集的分析可知與其運行一致。 畫圖區(qū)域的刷新主要是為了實現(xiàn)同一塊區(qū)域可以畫多次不同的運行過程，有兩個函數(shù)承擔(dān)。 （ 2）查找與合并：在廣度優(yōu)先搜索中首先判斷是否需要標(biāo)記此節(jié)點，如果需要標(biāo)記此節(jié)點則將此節(jié)點標(biāo)記為以訪問過，并添加到已經(jīng)訪問過的結(jié)點的集合中；如果是要進行判斷兩個結(jié)點是不是都已經(jīng)訪問過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結(jié)點所在的集合中是否有另一個結(jié)點，如果存在則舍棄當(dāng)前所選擇的邊，否則選擇此邊為最小生成樹的一邊。對于廣度優(yōu)先搜索方法的實現(xiàn)這里使用的方法是通過利用隊列這一數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的。 （ 2）對已經(jīng)排好序的邊進行選擇，對沒有訪問過的最小權(quán)值的邊的兩個結(jié)點進行判斷，檢查是否已經(jīng)被訪問過了，如果有一個沒有被訪問過，則將和此邊相應(yīng)的頂點進行深度優(yōu)先搜索的判斷之后進行標(biāo)記，同時存儲所選擇的這個邊 和相應(yīng)的頂點。 至此通過利用深度優(yōu)先搜索進行邊通分量查詢的 kruskal 算法運行完畢，通過對比可知和使用普通的查 找算法得到的運行結(jié)果是一致的。同時通過深度優(yōu)先搜索對著兩個 結(jié)點分別進行判斷是否需要標(biāo)記，可知點 4 此時被標(biāo)記訪問過了。其基本思想是：對于一個無向連通圖，從某一個起始結(jié)點 vi 出發(fā)，訪問與它相連的一個結(jié)點 vj，且 vi、 vj這兩個結(jié)點之間的邊（ vi、 vj）是所有以 vi 為連接結(jié)點的邊中權(quán)值最小的；然后再從 vj 出發(fā)尋找與 vj 相連的頂點，且它們之間的邊是所有以 vi 為連接結(jié)點的邊中權(quán)值最小的，不斷的重復(fù)直到找到訪問完所有的結(jié)點為止。在此函數(shù)中如果只靠一個循環(huán)來得到結(jié)果，則對于合并中得到的層次比較深的集合，查找會很費時。 至此 kruskal 算法利用并查集查找、合并的過程結(jié)束，通過kruskal算法得到最小生成樹及生成過程，其最小生成樹的權(quán)值為 16。此時集合變?yōu)?{1}、 { 5}、 { 7}。通過判斷畫出發(fā)生改變的集合 { 3}。最初把每一個對象看做是一個單元集合，然后依次按順序讀入一個等價對后，將等價對中的兩個元素所在的集合合并。 模塊設(shè)計與實現(xiàn) Kruskal 算法的實現(xiàn)主要包含兩個部分，即帶權(quán) 值的邊的排序和判斷選取的邊的兩個頂點是否屬于同一個連通分量。 （ 3）如此反 復(fù)下去，直到所有頂點在同一個連通分量上為止。 存第 k 個頂點的數(shù)據(jù)和相應(yīng)邊的權(quán)值到 MST 中，并將lowCost[k]置為 1，表示第 k 個頂點從集合 V(G)－ V(MST)加入了集合V(MST)中 當(dāng)?shù)?k 個頂點加入到集合 V(MST)后，若存 在一條邊 (k,j)，其中 k 是集合 V(MST)的頂點， j是集合 V(G)－ V(MST)的頂點，且邊 (k,j)權(quán)值較原先 lowCost[j]的代價更小，則用這個權(quán)值修正原先 lowCost[j]中的權(quán)值。 至此圖 G中所有的點均已添加到了 V(MST)，最小生成樹生成完畢，其權(quán)值為 16。 （ 2） (vi,vj)是關(guān)聯(lián)于 V(MST)中頂點的邊中權(quán)值最小的邊。 對于無向連通圖 G（ V,E），在 prime 算法中，將圖 G 頂點集合分為兩個集合 V1（ G）和 V2（ G）， V1（ G）用來存儲當(dāng)前已經(jīng)遍歷到的頂點，即最小生成樹中的頂點 V(MST)， V2（ G） 用來存儲還沒有遍歷到的頂點。 在深度優(yōu)先搜索算法（ BreadthFirstSearch）中使用了棧這一數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)邊的連通分量的查詢，對廣度優(yōu)先搜索算法(DepthFirstSearch)的實現(xiàn)使用了隊列這一數(shù)據(jù)結(jié)構(gòu)，這里的隊列和棧都是通過編程實現(xiàn)。 為了更好、更生動的表示這些算法的運算過程，在這里如果使用動態(tài)顯示算法的求解過程將會是最好的選擇。例如：要在 n 個城市之間鋪設(shè)光纜，主要目標(biāo)是要使這 n 個城市的任意兩個之間都可以通信，但鋪設(shè)光纜的費用很高，且各個城市之間鋪設(shè)光纜的費用不同；另一個目標(biāo)是要使鋪設(shè)光纜的總費用最低。并對兩種算法進行分析和比較。在這里我選擇了將這三種搜索算法融合到 Kruskal算法，因為我覺得在 Kruskal算法對邊通分量進行查詢和合并中使用這三種方法 更合理且更容易實現(xiàn)，因此也實現(xiàn)了將這三種搜索算法融合到 Kruskal 算法從而實現(xiàn)對圖的最小生成樹的查找。