【正文】 對(duì)于一個(gè)無(wú)向連通圖，從某一個(gè)起始結(jié)點(diǎn) vi 出發(fā)，依次訪問(wèn)與它相連的所有未訪問(wèn)過(guò)的結(jié)點(diǎn) vj vj2?? vjn，然后在順序訪問(wèn) vj vj2?? vjn的所有還未訪問(wèn)過(guò)的鄰接頂點(diǎn)；再?gòu)倪@些鄰接頂點(diǎn)出發(fā)，再訪問(wèn)它們的所有未訪問(wèn)過(guò)的鄰接頂點(diǎn)，??，不斷重復(fù)直到圖 G 中所有的頂點(diǎn)都被訪問(wèn)過(guò)為止。 （ 4）選擇下一條沒(méi)有被訪問(wèn)過(guò)的邊重新進(jìn)行（ 1）、（ 2）的判斷，直到所有的頂點(diǎn)均已被訪問(wèn)過(guò)且在同一個(gè)集合中，即已經(jīng)添加到了最小生成樹(shù)中則最小生成樹(shù)生成完畢。 （ 2）查找與合并：在深度優(yōu)先搜索中首先判斷是否需要標(biāo)記此節(jié)點(diǎn)，如果需要標(biāo)記此節(jié)點(diǎn)則將此節(jié)點(diǎn)標(biāo)記為以訪問(wèn)過(guò)，并添加到已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)的集合中，并將相應(yīng)的邊存入 E[]中；如果是要進(jìn)行判斷兩個(gè)結(jié)點(diǎn)是不是都已經(jīng)訪問(wèn) 過(guò)了，及是否屬于同一個(gè)集合利用棧來(lái)不斷的搜索其中一個(gè)結(jié)點(diǎn)所在的集合中是否有另一個(gè)結(jié)點(diǎn)，如果存在則舍棄當(dāng)前所選擇的邊，否則選擇此邊為最小生成樹(shù)的一邊。 深度優(yōu)先搜索的實(shí)現(xiàn)主要利用棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。 （ 7）繼續(xù)向下查找得到邊（ 1,2），判斷點(diǎn) 1 和點(diǎn) 2 是否已經(jīng)訪問(wèn)過(guò)了得知點(diǎn) 2 已經(jīng)被 訪問(wèn)過(guò)了，點(diǎn) 1 沒(méi)有，因此得到新的集合 { 2,、 7}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)著兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記，可知點(diǎn) 5 此時(shí)被標(biāo)記訪問(wèn)過(guò)了。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)這兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷及標(biāo)記已經(jīng)訪問(wèn)過(guò)了。對(duì)于深度優(yōu)先搜索方法的實(shí)現(xiàn)這里使用的方法是通過(guò)利用棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。 深度優(yōu)先搜索實(shí)現(xiàn) lKruskal算法動(dòng)態(tài)演示模塊 基本思想深度優(yōu)先搜索主要是在圖 的遍歷中使用此方法對(duì)整個(gè)圖進(jìn)行遍歷來(lái)訪問(wèn)整個(gè)圖中所有節(jié)點(diǎn)的一種遍歷方法。 （ 4）合并：兩個(gè)集合合并時(shí)，任何一方均可作為另一方的子孫。這里定義一個(gè) parent[n]的數(shù)組， parent[i]中存儲(chǔ)的就是結(jié)點(diǎn)i 所在的樹(shù)中的結(jié)點(diǎn) i父親結(jié)點(diǎn)的序號(hào)，并查集的初始化中所有的 結(jié)點(diǎn)的 parent值均為 1，即每個(gè)結(jié)點(diǎn)就是根節(jié)點(diǎn)，只包含它本身這一個(gè)元素。在 Kruskal 使用并查集時(shí)首先對(duì)其進(jìn)行邊 集合的排序，接著利用并查集對(duì)圖 G 中的頂點(diǎn)進(jìn)行初始化，每一個(gè)頂點(diǎn)當(dāng)做一個(gè)集合，同時(shí)給其一個(gè)相關(guān)的變量標(biāo)志其集合中頂點(diǎn)的數(shù)目；然后利用并查集判斷此時(shí)的頂點(diǎn)所在集合是不是相同，如果不相同則合并這兩個(gè)頂點(diǎn)所在的集合。此時(shí)集合變?yōu)?{ 7}。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫(huà)出此邊，其權(quán)重為 4。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 4}。此時(shí)集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 { 7}。 （ 2）在圖 G的邊的集合 E中按存儲(chǔ)次序選擇權(quán)值 最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲(chǔ)，所以此處選擇的邊（ 2,3）其權(quán)重為 1。 在此處實(shí)現(xiàn) Kruskal 算法時(shí)主 要使用并查集對(duì)相關(guān)頂點(diǎn)進(jìn)行搜索和合并，從而實(shí)現(xiàn)了使用并查集實(shí)現(xiàn) Kruskal 算法。 （ 5）當(dāng)最小生成樹(shù)生成完畢時(shí)，則調(diào)用 Draw（ E）函數(shù)畫(huà)出生成的過(guò)程。 kruskal 算法的設(shè)計(jì)與實(shí)現(xiàn)如下所述（具體的代碼實(shí)現(xiàn)見(jiàn)附錄）： （ 1）對(duì)所畫(huà)區(qū)域進(jìn)行刷新。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 1,2）并畫(huà)出此邊，其權(quán)重為 5。 （ 2）在圖 G的邊的集合 E中按存儲(chǔ)次序選擇權(quán)值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲(chǔ)，所以后選擇邊（ 6,7）并畫(huà)出此邊，其權(quán)重為 1。具體如下： （ 1） 構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn)沒(méi)有邊的非連通圖 T，圖中的每個(gè)頂點(diǎn)為一個(gè)連通分量。 Kruskal 算法通常是在已知 V(MST)=V(G)， E(MST)的初態(tài)為空時(shí)對(duì)圖 G 進(jìn)行相關(guān)處理的到最小生成樹(shù)的。 （ 3）循環(huán) n1次 lowCost 中尋找具有最小權(quán)值的邊。這里僅給出語(yǔ)言描述的實(shí)現(xiàn)過(guò)程，源代碼的實(shí)現(xiàn)在后面的附錄中將會(huì)給出。 （ 5）集合 V(MST)此時(shí)已經(jīng)有五個(gè)頂點(diǎn)了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權(quán)值為 4 的邊添加到 E(MST)中，并將頂點(diǎn) 6 添加到 V(MST)中并畫(huà)出此邊。 下面主要通過(guò)題目中給出的例子（如圖 1）對(duì) prime 算法進(jìn)行詳細(xì)的解析： （ 1）將 1 作為起始頂點(diǎn)添加到 V(MST)，找到與之相連的符合條件的邊 (v1,v2)，將權(quán)值為 5 的邊添加到 E(MST)中，并將頂點(diǎn) 2 添加到V(MST)中并畫(huà)出此邊。此時(shí) (vi,vj)一定均未加入 E(MST)。 Prime算法的具體過(guò)程如下： 設(shè)最小生成樹(shù)中點(diǎn)的集合 V(MST)和邊的集合 E(MST)的初態(tài)均為空。 二．詳細(xì)設(shè)計(jì)與實(shí)現(xiàn) Prime 算法的基本思想是以圖中的某一個(gè)頂點(diǎn)作為起始頂點(diǎn)，然后從起始頂點(diǎn)出發(fā)不斷的從還沒(méi)有遍歷到的頂點(diǎn)中選擇與已經(jīng)遍歷到的頂點(diǎn)存在之間權(quán)值最小邊的頂點(diǎn)，并將新遍歷的點(diǎn)不斷的添加到已經(jīng)遍歷的頂點(diǎn)集合中。設(shè)計(jì)與實(shí)現(xiàn)中由于所體現(xiàn)的重點(diǎn)不同，因此下面的說(shuō)明主要圍繞著此題的重點(diǎn)，即最小生成樹(shù)的生成過(guò)程。 Windows07，開(kāi)發(fā)工具 VC++系統(tǒng)總體設(shè)計(jì) 由于這是對(duì)圖進(jìn)行相關(guān)的操作，因此涉及圖的存儲(chǔ)問(wèn)題，在這里使用的是鄰接矩陣這一數(shù)據(jù)結(jié) 構(gòu)來(lái)實(shí)現(xiàn)圖的存儲(chǔ)。 方案選擇通過(guò)對(duì)題目的分析，對(duì)于如何將廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運(yùn)用到對(duì)邊通分量進(jìn)行查詢(xún)和合并中有不同的結(jié)合方法。通過(guò)這些利用知識(shí)實(shí)現(xiàn)Kruskal 算法和 Prim 算法從而得到圖的最小生成樹(shù)。 基本的要求是實(shí)現(xiàn)兩種算 法：通過(guò)實(shí)現(xiàn) Kruskal 算法和 Prim 算法來(lái)得到圖的最小生成樹(shù)。軟件綜合實(shí)習(xí)報(bào)告（合集） 第一篇：軟件綜合實(shí)習(xí)報(bào)告 軟件綜合實(shí)習(xí)報(bào)告 題目：最小生成樹(shù)算法 院（系）： 計(jì)算機(jī)學(xué)院 專(zhuān) 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 姓 名： 班級(jí)學(xué)號(hào)： 2021年 9月 12 日 目錄一．系統(tǒng)需求分析與總體設(shè)計(jì) ............................................................................1 需 求 分析?????????????????????????????????????????? 1 問(wèn) 題 描述???????????????????????????????????????? 1 問(wèn) 題 分析???????????????????????????????????????? 1 方 案 選擇???????????????????????????????????????? 1 開(kāi) 發(fā) 平臺(tái)??????????????????????? ????????????????? 2 系 統(tǒng) 總 體 設(shè)計(jì)?????????????????????????????????????? .2 二．詳細(xì)設(shè)計(jì)與系統(tǒng)實(shí)現(xiàn) .......................................................................................2 算 法 動(dòng) 態(tài) 演 示模?? .?????? .??????????????????????? .2 基 本 思想???????????????????????????????????????? 2 設(shè) 計(jì) 與 實(shí)現(xiàn)?????????????????????????????????????? ..3 Kruskal 算 法 動(dòng) 態(tài) 演 示 模塊??????????????????????????? .4 基 本 思想???????????????????????????????????????? 4 設(shè) 計(jì) 與 實(shí)現(xiàn)??????????????????? ???????????????????? 4 并 查 集 實(shí) 現(xiàn) kruskal 算 法 動(dòng) 態(tài) 演 示 模塊?????????????????? ..4 基 本 思想???????????????????????????????????????? 5 設(shè) 計(jì) 與 實(shí)現(xiàn)??????????????????????????????????????? 5 深 度 優(yōu) 先 搜 索 實(shí) 現(xiàn) Kruskal 算 法 動(dòng) 態(tài) 演 示 模塊???????????? .6 基 本 思想???????????????????????????????????????? 6 設(shè) 計(jì) 與 實(shí)現(xiàn)??????????????????????????????????????? 7 廣度優(yōu)先搜索實(shí)現(xiàn) Kruskal 算法動(dòng)態(tài)演示模塊???????????? .7 基 本 思想???????????????????????????????????????? 7 設(shè) 計(jì) 與 實(shí)現(xiàn)??????????????????????????? ???????????? 8 畫(huà) 圖 模塊?????????????????????????????????????????? ..8 三．系統(tǒng)測(cè)試 ..................................................................................................................9 測(cè) 試 數(shù)據(jù)?????????????????????????????? 9 的 測(cè) 試 結(jié)果???????????????? .???????? 9 算 法 的 測(cè) 試 結(jié)果???????????????? .??? ..? .10 并 查 集 實(shí) 現(xiàn) Kruskal 算 法 的 測(cè) 試 結(jié)果?????????????? .10 深 度 優(yōu) 先 搜 索 實(shí) 現(xiàn) Kruskal 算 法 的 測(cè) 試 結(jié)果?????????? .11 廣 度 優(yōu) 先 搜 索 實(shí) 現(xiàn) Kruskal 算 法 的 測(cè) 試 結(jié)果?????????? .11 效 率 分析?????????????????????????????.12 四．總結(jié) ...........................................................................................................................12 參 考 資料???????????????????????????????????????????? .13 一．系統(tǒng)需求分析與總體設(shè)計(jì) 需求分析 問(wèn)題描述在一個(gè)具有幾個(gè)頂點(diǎn)的連通圖 G 中，如果存在子圖 G包含 G 中所有頂點(diǎn)和一部分邊，且不形成回路，則稱(chēng) G為圖 G 的生成樹(shù)，代價(jià)最小生成樹(shù)則稱(chēng)為最小生成樹(shù)（ MinimalSpanningTree）。這就需要找到帶權(quán)的最小生成樹(shù)。 測(cè)試數(shù)據(jù)如下： 圖（ 1） 問(wèn)題分析通過(guò)問(wèn)題的描述，可知這一道題目主要涉及，面向?qū)ο蟮姆治雠c設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)和算法。對(duì)于不同的算法其求解最小生成樹(shù)時(shí)運(yùn)算的效率是不同的，因此還需要對(duì)各種算法時(shí)間復(fù)雜度進(jìn)行分析和比較， 從而更加深入的理解算法，從而方便我們?cè)诓煌膱?chǎng)合采用不同的實(shí)現(xiàn)算法。可以知道使用MFC 通過(guò)單文檔畫(huà)圖來(lái)實(shí)現(xiàn)算法動(dòng)態(tài)顯示運(yùn)行效果或者使用對(duì)話框來(lái)實(shí)現(xiàn)算法動(dòng)態(tài)顯示運(yùn)行效果，為了方便起見(jiàn)，我選擇的是通過(guò) MFC 建立單文檔來(lái)實(shí)現(xiàn)這一效果。 這里主要分為六個(gè)模塊，即 prime 算法模塊、 kruskal 算法模塊、用并查集實(shí)現(xiàn) kruskal算法的模塊、 kruskal算法和深度優(yōu)先搜索算法結(jié)合的模塊、 kruskal 算法和廣度優(yōu)先搜索算法結(jié)合的模塊以及畫(huà)圖操作的相關(guān)模塊。在這些算法運(yùn)行過(guò)程中實(shí)現(xiàn)的畫(huà)圖操作主要通過(guò)調(diào)用一個(gè)公用的函數(shù)進(jìn)行畫(huà)圖的相關(guān)操作。對(duì)于已經(jīng)選擇的頂點(diǎn)之間的邊存儲(chǔ)在最小生成樹(shù)的邊的集合中 E(MST)。 （ 1） (vi,vj) E(G)， v是 V(