【正文】 取的邊的兩個頂點是否屬于同一個連通分量。 （ 6）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 1,2）并畫出此邊，其權重為 5。 （ 4）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,5）并畫出此邊，其權重為 3。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7）并畫出此邊，其權重為 1。 （ 3）如此反 復下去，直到所有頂點在同一個連通分量上為止。具體如下： （ 1） 構(gòu)造一個只有 n 個頂點沒有邊的非連通圖 T，圖中的每個頂點為一個連通分量。每次挑選邊成功了即畫出此邊。 Kruskal 算法通常是在已知 V(MST)=V(G)， E(MST)的初態(tài)為空時對圖 G 進行相關處理的到最小生成樹的。 存第 k 個頂點的數(shù)據(jù)和相應邊的權值到 MST 中，并將lowCost[k]置為 1，表示第 k 個頂點從集合 V(G)－ V(MST)加入了集合V(MST)中 當?shù)?k 個頂點加入到集合 V(MST)后，若存 在一條邊 (k,j)，其中 k 是集合 V(MST)的頂點， j是集合 V(G)－ V(MST)的頂點，且邊 (k,j)權值較原先 lowCost[j]的代價更小，則用這個權值修正原先 lowCost[j]中的權值。 （ 3）循環(huán) n1次 lowCost 中尋找具有最小權值的邊。 （ 2） MST頂點初始值 ={序號為 0的頂點 }，其邊所在的結(jié)構(gòu)體數(shù)組 E[n1]的值也為空。這里僅給出語言描述的實現(xiàn)過程，源代碼的實現(xiàn)在后面的附錄中將會給出。 至此圖 G中所有的點均已添加到了 V(MST)，最小生成樹生成完畢，其權值為 16。 （ 5）集合 V(MST)此時已經(jīng)有五個頂點了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權值為 4 的邊添加到 E(MST)中，并將頂點 6 添加到 V(MST)中并畫出此邊。 （ 3）集合 V(MST)此時已經(jīng)有三個頂點了，即 3，找到與之相連的符合條件的邊 (v2,v4)將權值為 2 的邊添加到 E(MST)中，并將頂點 4 添加到 V(MST)中并畫出此邊。 下面主要通過題目中給出的例子（如圖 1）對 prime 算法進行詳細的解析： （ 1）將 1 作為起始頂點添加到 V(MST)，找到與之相連的符合條件的邊 (v1,v2)，將權值為 5 的邊添加到 E(MST)中，并將頂點 2 添加到V(MST)中并畫出此邊。 （ 2） (vi,vj)是關聯(lián)于 V(MST)中頂點的邊中權值最小的邊。此時 (vi,vj)一定均未加入 E(MST)。然后，依次選出 n1 條符合以下條件的邊(vi,vj)。 Prime算法的具體過程如下： 設最小生成樹中點的集合 V(MST)和邊的集合 E(MST)的初態(tài)均為空。 對于無向連通圖 G（ V,E），在 prime 算法中，將圖 G 頂點集合分為兩個集合 V1（ G）和 V2（ G）， V1（ G）用來存儲當前已經(jīng)遍歷到的頂點，即最小生成樹中的頂點 V(MST)， V2（ G） 用來存儲還沒有遍歷到的頂點。 二．詳細設計與實現(xiàn) Prime 算法的基本思想是以圖中的某一個頂點作為起始頂點，然后從起始頂點出發(fā)不斷的從還沒有遍歷到的頂點中選擇與已經(jīng)遍歷到的頂點存在之間權值最小邊的頂點，并將新遍歷的點不斷的添加到已經(jīng)遍歷的頂點集合中。 對于算法運行時的動態(tài)顯示運行過程這一要求主要通過將相關的畫圓、畫線等相關畫圖 的操作扦插到相關的算法中，在算法的運行過程中再通過對相關條件的判斷從而決定是否執(zhí)行畫圓、畫線等操作。設計與實現(xiàn)中由于所體現(xiàn)的重點不同，因此下面的說明主要圍繞著此題的重點，即最小生成樹的生成過程。 在深度優(yōu)先搜索算法（ BreadthFirstSearch）中使用了棧這一數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)邊的連通分量的查詢，對廣度優(yōu)先搜索算法(DepthFirstSearch)的實現(xiàn)使用了隊列這一數(shù)據(jù)結(jié)構(gòu)，這里的隊列和棧都是通過編程實現(xiàn)。 Windows07，開發(fā)工具 VC++系統(tǒng)總體設計 由于這是對圖進行相關的操作，因此涉及圖的存儲問題，在這里使用的是鄰接矩陣這一數(shù)據(jù)結(jié) 構(gòu)來實現(xiàn)圖的存儲。 對于運用圖形學的知識實現(xiàn)算法的動態(tài)運行效果。 方案選擇通過對題目的分析，對于如何將廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運用到對邊通分量進行查詢和合并中有不同的結(jié)合方法。 為了更好、更生動的表示這些算法的運算過程，在這里如果使用動態(tài)顯示算法的求解過程將會是最好的選擇。通過這些利用知識實現(xiàn)Kruskal 算法和 Prim 算法從而得到圖的最小生成樹。較高的要求是在邊通分量的查詢與合并的過程中，采用廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法，并進行分析和比較算法時間復雜度。 基本的要求是實現(xiàn)兩種算 法：通過實現(xiàn) Kruskal 算法和 Prim 算法來得到圖的最小生成樹。例如：要在 n 個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同；另一個目標是要使鋪設光纜的總費用最低。軟件綜合實習報告（合集） 第一篇：軟件綜合實習報告 軟件綜合實習報告 題目：最小生成樹算法 院（系）： 計算機學院 專 業(yè)： 計算機科學與技術 姓 名： 班級學號： 2021年 9月 12 日 目錄一．系統(tǒng)需求分析與總體設計 ............................................................................1 需 求 分析?????????????????????????????????????????? 1 問 題 描述???????????????????????????????????????? 1 問 題 分析???????????????????????????????????????? 1 方 案 選擇???????????????????????????????????????? 1 開 發(fā) 平臺??????????????????????? ????????????????? 2 系 統(tǒng) 總 體 設計?????????????????????????????????????? .2 二．詳細設計與系統(tǒng)實現(xiàn) .......................................................................................2 算 法 動 態(tài) 演 示模?? .?????? .??????????????????????? .2 基 本 思想???????????????????????????????????????? 2 設 計 與 實現(xiàn)?????????????????????????????????????? ..3 Kruskal 算 法 動 態(tài) 演 示 模塊??????????????????????????? .4 基 本 思想???????????????????????????????????????? 4 設 計 與 實現(xiàn)??????????????????? ???????????????????? 4 并 查 集 實 現(xiàn) kruskal 算 法 動 態(tài) 演 示 模塊?????????????????? ..4 基 本 思想???????????????????????????????????????? 5 設 計 與 實現(xiàn)??????????????????????????????????????? 5 深 度 優(yōu) 先 搜 索 實 現(xiàn) Kruskal 算 法 動 態(tài) 演 示 模塊???????????? .6 基 本 思想???????????????????????????????????????? 6 設 計 與 實現(xiàn)??????????????????????????????????????? 7 廣度優(yōu)先搜索實現(xiàn) Kruskal 算法動態(tài)演示模塊???????????? .7 基 本 思想???????????????????????????????????????? 7 設 計 與 實現(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)需求分析與總體設計 需求分析 問題描述在一個具有幾個頂點的連通圖 G 中，如果存在子圖 G包含 G 中所有頂點和一部分邊，且不形成回路，則稱 G為圖 G 的生成樹，代價最小生成樹則稱為最小生成樹（ MinimalSpanningTree）。 許多應用問題都是一個求無向連通圖的最小生成樹問題。這就需要找到帶權的最小生成樹。并對兩種算法進行分析和比較。 測試數(shù)據(jù)如下： 圖（ 1） 問題分析通過問題的描述，可知這一道題目主要涉及，面向?qū)ο蟮姆治雠c設計，數(shù)據(jù)結(jié)構(gòu)和算法。除此之外，在最小生成樹的求解過程中會對邊通分量進行查詢和合并，由題可知要對邊 通 分 量 進 行 查 詢 和 合 并 要 使 用 廣 度 優(yōu) 先 搜 索 算 法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法。對于不同的算法其求解最小生成樹時運算的效率是不同的，因此還需要對各種算法時間復雜度進行分析和比較， 從而更加深入的理解算法，從而方便我們在不同的場合采用不同的實現(xiàn)算法。在這里我選擇了將這三種搜索算法融合到 Kruskal算法，因為我覺得在 Kruskal算法對邊通分量進行查詢和合并中使用這三種方法 更合理且更容易實現(xiàn)，因此也實現(xiàn)了將這三種搜索算法融合到 Kruskal 算法從而實現(xiàn)對圖的最小生成樹的查找。可以知道使用MFC 通過單文檔畫圖來實現(xiàn)算法動態(tài)顯示運行效果或者使用對話框來實現(xiàn)算法動態(tài)顯示運行效果，為了方便起見，我選擇的是通過 MFC 建立單文檔來實現(xiàn)這一效果。在對圖進行相關操作尋找最小生成樹時，得到的生成樹中的邊采用的是結(jié)構(gòu)體的存儲方式，在實現(xiàn)的過程