【正文】 發(fā)工具 VC++系統(tǒng)總體設(shè)計 由于這是對圖進行相關(guān)的操作，因此涉及圖的存儲問題，在這里使用的是鄰接矩陣這一數(shù)據(jù)結(jié) 構(gòu)來實現(xiàn)圖的存儲。通過這些利用知識實現(xiàn)Kruskal 算法和 Prim 算法從而得到圖的最小生成樹。軟件綜合實習報告（合集） 第一篇：軟件綜合實習報告 軟件綜合實習報告 題目：最小生成樹算法 院（系）： 計算機學院 專 業(yè)： 計算機科學與技術(shù) 姓 名： 班級學號： 2021年 9月 12 日 目錄一．系統(tǒng)需求分析與總體設(shè)計 ............................................................................1 需 求 分析?????????????????????????????????????????? 1 問 題 描述???????????????????????????????????????? 1 問 題 分析???????????????????????????????????????? 1 方 案 選擇???????????????????????????????????????? 1 開 發(fā) 平臺??????????????????????? ????????????????? 2 系 統(tǒng) 總 體 設(shè)計?????????????????????????????????????? .2 二．詳細設(shè)計與系統(tǒng)實現(xiàn) .......................................................................................2 算 法 動 態(tài) 演 示模?? .?????? .??????????????????????? .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）。 測試數(shù)據(jù)如下： 圖（ 1） 問題分析通過問題的描述，可知這一道題目主要涉及，面向?qū)ο蟮姆治雠c設(shè)計，數(shù)據(jù)結(jié)構(gòu)和算法?？梢灾朗褂肕FC 通過單文檔畫圖來實現(xiàn)算法動態(tài)顯示運行效果或者使用對話框來實現(xiàn)算法動態(tài)顯示運行效果，為了方便起見，我選擇的是通過 MFC 建立單文檔來實現(xiàn)這一效果。在這些算法運行過程中實現(xiàn)的畫圖操作主要通過調(diào)用一個公用的函數(shù)進行畫圖的相關(guān)操作。 （ 1） (vi,vj) E(G)， v是 V(MST)的頂點，而 vj是還未加入 V(MST)的頂點。 （ 4）集合 V(MST)此時已經(jīng)有四個頂點了，即 4，找到與之相連的符合條件的邊 (v4,v5)將權(quán)值為 3的邊添加到 E(MST)中，并將頂點 5 添加到 V(MST)中并畫出此邊。 lowCost 的初始值為鄰接矩陣中第 0 行的值，這樣初始時lowCost 中就存放了從集合 V(MST)中頂點 0 到集 合 V(G)－ V(MST)中各個頂點的權(quán)值。在 n 個頂點的圖中，選夠 n1條邊即可。 （ 5）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫出此邊，其權(quán)重為 4。 （ 4）如果不符合（ 2）中的判斷則不斷的重復(fù)直到選取的邊等于n1。畫出初始狀態(tài)。此時集合變?yōu)?{1}、 { 4}、 {5}、 { 7}。 （ 7）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 1,2）并畫出此邊，其權(quán)重為 5。 （ 2）初始化過程：為了方便并查集的描述與實現(xiàn)，通常把先后加入到一個集合中的元素表示成一個樹形結(jié)構(gòu)，并用根節(jié)點來代表這個集合。在每一次的合并過程結(jié)束時，將會畫出合并之后的集合。 （ 2）繼續(xù)向下查找得到邊（ 6,7），判斷點 6 和點 7 是否已經(jīng)訪問過了，由于數(shù)組 check 中相應(yīng)的值為 0，因此合并這兩個結(jié)點，得到新的集合 { 7}。 （ 6）繼續(xù)向下查找得到邊（ 5,6），判斷點 5 和點 6 是否已經(jīng)訪問過了得知已經(jīng)被訪問過了，因此得到不進行集合的合并，繼續(xù)向下查找相應(yīng)的邊。 （ 1）棧： 這里使用到的與棧相關(guān)的操作主要有棧中數(shù)據(jù)的初始化StackInitiate、將數(shù)據(jù)壓入棧的操作 StackPush、將數(shù)據(jù)彈出棧的操作 StackPop、判斷棧是否為空的操作 StackNotEmpty 和得到棧頂元素的操作 StackTop。通常是利用隊列這一數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)圖中結(jié)點的遍歷。因此主要包含兩個方面，即隊列這一數(shù)據(jù)結(jié)構(gòu)中相關(guān)函數(shù)的設(shè)計與實現(xiàn)，以及如何實現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設(shè)計與實現(xiàn)。 （ 5）當最小生成樹生成完畢時，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 圖（ 3） 通過上面 prime 算法的解析結(jié)果和運行結(jié)果發(fā)現(xiàn)其運行結(jié)果與分析中應(yīng)該得到的結(jié)果是一致的，由于畫圖和判斷中采用的有延長運行時間的函數(shù)，因此這里只通過理論分析得出 prime算法的運行效率。因此在實現(xiàn)的過程中應(yīng)該盡量選擇效率比較高的方法來實現(xiàn)算法。對于使用 kruskal 算法和深度優(yōu)先搜索結(jié)合的算法，對邊的遍歷至多是 e 此故其總代價為 O(n^2*e)。因為在學習數(shù)據(jù)結(jié)構(gòu)的時只知道廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)是用來遍歷圖的，平時沒有在搜索的過程中使用此種算法，不知道該從何下手，通過老師的講解多多少少悟出了點，之后反復(fù) 的思考最終通過使用隊列實現(xiàn)了在邊通分量的 查 詢 與 合 并 的 過 程 中 ， 采 用 廣 度 優(yōu) 先 搜 索 算 法（ BreadthFirstSearch），通過使用棧實現(xiàn)了在邊通分量的查詢與合并的過程中，深度優(yōu)先搜索算法 (DepthFirstSearch)。這就需要找到帶權(quán)的最小生成樹。對于不同的算法其求解最小生成樹時運算的效率是不同的，因此還需要對各種算法時間復(fù)雜度進行分析和比較，從而更加深入的理解算法，從而方便我們在不同的場合采用不同的實現(xiàn)算法。 這里主要分為六個模塊，即 prime 算法模塊、 kruskal 算法模塊、用并查集實現(xiàn) kruskal算法的模塊、 kruskal算法和深度優(yōu)先搜索算法結(jié)合的模塊、 kruskal 算法和廣度優(yōu)先搜索算法結(jié)合的模塊以及畫圖操作的相關(guān)模塊。對于已經(jīng)選擇的頂點之間的邊存儲在最小生成樹的邊的集合中 E(MST)。選出滿足該條件的邊，將 vj 加入 V(MST)， (vi,vj)加入 E(MST)，之后畫出相應(yīng)的邊和新添加進去的頂點。 設(shè)計與實現(xiàn)對于 prime 算法的動態(tài)演示，主要是關(guān)乎兩個函數(shù)的實現(xiàn)一個是畫圖函數(shù)的實現(xiàn)，另外一個就是如何判斷何時進行畫圖操作并進行相關(guān)操作的畫圖函數(shù)，在這里主要通過兩個函數(shù)實現(xiàn)一個是與 Kruskal 算法動態(tài)實現(xiàn)的公用的畫圖操作函數(shù)，另外一個就是 prime 算法尋找最小生成樹的實現(xiàn)。 當最小生成樹生成完畢時，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 下面主要通過題目中給出的例子（如圖 1）對 kruskal 算法進行詳細的解析： （ 1）在圖 G的邊的集合 E中按存儲次序選擇權(quán)值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）并畫出此邊，其權(quán)重為 1。因此首先將圖 G 的頂點集合 V 分為 n 個等價類，每個等價類包括一個頂點；然后以權(quán)值的大小為順序處理各條邊，如果某條邊連接兩個不同等價類的頂點，則這條邊被添加到 MST（選取的邊不與前面選取的邊構(gòu)成回路），兩個等價類被合并為一個；反復(fù)執(zhí)行此過程，直到只剩下一個等價類。在此過程中不斷的重復(fù)使用一個搜索運算，從而確定此元素在哪一個集合中，當讀入一個等價對 A≡ B 時，首先檢測 A 和 B是不是屬于同一個集合，如果是，則不用合并；如果不是，則使用一個合并運算把 A 和 B 合并到同一個集合中，使得這兩個集合中的任意兩個元素都是等價的（依 據(jù)等價的傳遞性）。 （ 3）在圖 G的邊的集合 E中按存儲次序選擇權(quán)值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇 邊（ 6,7），其權(quán)重為 1。通過判斷畫出發(fā)生改變的集合 { 5}。 設(shè)計與實現(xiàn) Kruskal 算法利用并查集實現(xiàn)查找、合并的設(shè)計與實現(xiàn)也是首先選擇權(quán)值最小的邊，其次是利用并查集來對所要選擇的那些頂點進行查找、合并。這里通過壓縮路徑的方法來加快后續(xù)的查找速度，主要是通過增加一個 while 循環(huán)，每次都把從結(jié)點 i 到集合根節(jié)點的路徑上經(jīng)過的結(jié)點直接設(shè)置為根結(jié)點的子結(jié)點。 在這個算法的實現(xiàn)過程中，邊通分量的查找雖然是深度優(yōu) 先搜索為主，但是是以最小生成樹的的生成過程為主，因此這里所采用的畫圖操做運行的情況和使用一般的方法實現(xiàn) kruskal 算法的運行過程是一樣的，在這里不再給予詳細的說明，如有必要則可以參照 kruskal的生成最小生成樹的