【正文】 度 優(yōu) 先 搜 索 算 法（ BreadthFirstSearch），通過(guò)使用棧實(shí)現(xiàn)了在邊通分量的查詢(xún)與合并的過(guò)程中，深度優(yōu)先搜索算法 (DepthFirstSearch)。 這讓我意識(shí)到學(xué)習(xí)到的知識(shí)一定要活用才能創(chuàng)造出更好的方法，只是使用它通常的用途是遠(yuǎn)遠(yuǎn)不夠的。 雖然做的時(shí)候還是很多都不熟悉，但是我知道如果我不嘗試這去做的話就真的什么也做不出來(lái)了。雖然最后做的和自己最初設(shè)想的有所差異，但是題目中的要求我都完成了，還是小有成就感的。所以通過(guò) 這次的實(shí)習(xí)，讓我認(rèn)識(shí)到只要去嘗試，去努力沒(méi)有什么是不可以做的。 參考文獻(xiàn)： [1]朱戰(zhàn)立，數(shù)據(jù)結(jié)構(gòu) — 使用 c 語(yǔ)言（第四版），電子工業(yè)出版社2021年 11 月 [2]王桂平、王衍、任嘉辰，圖論算法理論、實(shí)現(xiàn)及應(yīng)用，北京大學(xué)出版社， 2021 年 1月 [3]孫鑫、余安萍， VC++深入詳解，電子工業(yè)出版社 2021年 5月 第二篇：軟件綜合實(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）。 許多應(yīng)用問(wèn)題都是一個(gè)求無(wú)向連通圖的最小生成樹(shù)問(wèn)題。例如：要在 n 個(gè)城市之間鋪設(shè)光纜，主要目標(biāo)是要使這 n 個(gè)城市的任意兩個(gè)之間都可以通信，但鋪設(shè)光纜的費(fèi)用很高，且各個(gè)城市之 間鋪設(shè)光纜的費(fèi)用不同；另一個(gè)目標(biāo)是要使鋪設(shè)光纜的總費(fèi)用最低。這就需要找到帶權(quán)的最小生成樹(shù)。 基本的要求是實(shí)現(xiàn)兩種算法：通過(guò)實(shí)現(xiàn) Kruskal 算法和 Prim 算法來(lái)得到圖的最小生成樹(shù)。并對(duì)兩種算法進(jìn)行分析和比較。較高的要求是在邊通分量的查詢(xún)與合并的過(guò)程中，采用廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法，并進(jìn)行分析和比較算法時(shí)間復(fù)雜度。 測(cè)試數(shù)據(jù)如下： 圖（ 1） 問(wèn)題分析通過(guò)問(wèn)題的描述，可知這一道題目主要涉及，面向?qū)ο蟮姆治雠c設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)和算法。通過(guò)這些利用知識(shí)實(shí)現(xiàn)Kruskal 算法和 Prim 算法從而得到圖的最小生成樹(shù)。除此之外，在最小生成樹(shù)的求解過(guò)程中會(huì)對(duì)邊通分量進(jìn)行查詢(xún)和合并，由題可知要對(duì)邊 通 分 量 進(jìn) 行 查 詢(xún) 和 合 并 要 使 用 廣 度 優(yōu) 先 搜 索 算 法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法。 為了更好、更生動(dòng)的表示這些算法的運(yùn)算過(guò)程，在這里如果使用動(dòng)態(tài)顯示算法的求 解過(guò)程將會(huì)是最好的選擇。對(duì)于不同的算法其求解最小生成樹(shù)時(shí)運(yùn)算的效率是不同的，因此還需要對(duì)各種算法時(shí)間復(fù)雜度進(jìn)行分析和比較，從而更加深入的理解算法，從而方便我們?cè)诓煌膱?chǎng)合采用不同的實(shí)現(xiàn)算法。 方案選擇通過(guò)對(duì)題目的分析，對(duì)于如何將廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運(yùn)用到對(duì)邊通分量進(jìn)行查詢(xún)和合并中有不同的結(jié)合方法。在這里我選擇了將這三種搜索算法融合到 Kruskal算法，因?yàn)槲矣X(jué)得在 Kruskal算法對(duì)邊通分量進(jìn)行查詢(xún)和合并中使用這三種方法更合理且更容易實(shí)現(xiàn)，因此也實(shí)現(xiàn)了將這三種搜索算法融合到 Kruskal 算法從而實(shí)現(xiàn)對(duì)圖的最小生成樹(shù)的查找。 對(duì)于運(yùn)用圖形學(xué)的知識(shí)實(shí)現(xiàn)算法的動(dòng)態(tài)運(yùn)行效果?？梢灾朗褂肕FC 通過(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)這一效果。 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ǔ)。在對(duì)圖進(jìn)行相關(guān)操作尋找最小生成樹(shù)時(shí)，得到的生成樹(shù)中的邊采用的是結(jié)構(gòu)體的存儲(chǔ)方式，在實(shí)現(xiàn)的過(guò)程中相關(guān)變量和數(shù)據(jù)的存儲(chǔ)也主要通過(guò)數(shù)組、結(jié)構(gòu)體來(lái)實(shí)現(xiàn)了。 在深度優(yōu)先搜索算法（ BreadthFirstSearch）中使用 了棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)邊的連通分量的查詢(xún)，對(duì)廣度優(yōu)先搜索算法(DepthFirstSearch)的實(shí)現(xiàn)使用了隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)，這里的隊(duì)列和棧都是通過(guò)編程實(shí)現(xiàn)。 這里主要分為六個(gè)模塊，即 prime 算法模塊、 kruskal 算法模塊、用并查集實(shí)現(xiàn) kruskal算法的模塊、 kruskal算法和深度優(yōu)先搜索算法結(jié)合的模塊、 kruskal 算法和廣度優(yōu)先搜索算法結(jié)合的模塊以及畫(huà)圖操作的相關(guān)模塊。設(shè)計(jì)與實(shí)現(xiàn)中由于所體現(xiàn)的重點(diǎn)不同，因此下面的說(shuō)明主要圍繞著此題的重點(diǎn)，即最小生成樹(shù)的生成過(guò)程。 對(duì)于最小生成樹(shù)生 成過(guò)程中邊相關(guān)變量的存儲(chǔ)均是通過(guò)定義一個(gè)邊（ edge）的結(jié)構(gòu)體變量進(jìn)行存儲(chǔ)的，而關(guān)于點(diǎn)的存儲(chǔ)則是通過(guò)定義數(shù)組進(jìn)行相應(yīng)的存儲(chǔ)，由于不同的實(shí)現(xiàn)方法采用的初始值不一樣，因此使用的數(shù)組會(huì)有所不同。 對(duì)于算法運(yùn)行時(shí)的動(dòng)態(tài)顯示運(yùn)行過(guò)程這一要求主要通過(guò)將相關(guān)的畫(huà)圓、畫(huà)線等相關(guān)畫(huà)圖的操作扦插到相關(guān)的算法中，在算法的運(yùn)行過(guò)程中再通過(guò)對(duì)相關(guān)條件的判斷從而決定是否執(zhí)行畫(huà)圓、畫(huà)線等操作。在這些算法運(yùn)行過(guò)程中實(shí)現(xiàn)的畫(huà)圖操作主要通過(guò)調(diào)用一個(gè)公用的函數(shù)進(jìn)行畫(huà)圖的相關(guān)操作。 二．詳細(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)集合中。通過(guò)這樣的一個(gè)遍歷過(guò)程與畫(huà)圖的相關(guān)操作結(jié)合來(lái)實(shí)現(xiàn)最小生成樹(shù)生成過(guò)程的動(dòng)態(tài)演示。 對(duì)于無(wú)向連通圖 G（ V,E），在 prime 算法中，將圖 G 頂點(diǎn)集合分為兩個(gè)集合 V1（ G）和 V2（ G）， V1（ G）用來(lái)存儲(chǔ)當(dāng)前已經(jīng)遍歷到的頂點(diǎn)，即最小生成樹(shù)中的頂點(diǎn) V(MST)， V2（ G） 用來(lái)存儲(chǔ)還沒(méi)有遍歷到的頂點(diǎn)。對(duì)于已經(jīng)選擇的頂點(diǎn)之間的邊存儲(chǔ)在最小生成樹(shù)的邊的集合中 E(MST)。 Prime算法的具體過(guò)程如下： 設(shè)最小生成樹(shù)中點(diǎn)的集合 V(MST)和邊的集合 E(MST)的初態(tài)均為空。首先從圖 G 的頂點(diǎn)集 V(G)中任選一個(gè)頂點(diǎn)，把它加到最小生成樹(shù)MST 的頂點(diǎn)集 V(MST)中。然后，依次選出 n1 條符合以下條件的邊(vi,vj)。 （ 1） (vi,vj) E(G)， v是 V(MST)的頂點(diǎn)，而 vj是還未加入 V(MST)的頂點(diǎn)。此時(shí) (vi,vj)一定均未加入 E(MST)。通過(guò)判斷先找出所有這樣的邊。 （ 2） (vi,vj)是關(guān)聯(lián)于 V(MST)中頂點(diǎn)的邊中權(quán)值最小的邊。選出滿(mǎn)足該條件的邊，將 vj 加入 V(MST)， (vi,vj)加入 E(MST)，之后畫(huà)出相應(yīng)的邊和新添加進(jìn)去的頂點(diǎn)。 下面主要通過(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à)出此邊。 （ 2）集合 V(MST)此時(shí)已經(jīng)有兩個(gè)頂點(diǎn)了，即 2，找到與之相連的符合條件的邊 (v2,v3)將權(quán)值為 1的邊添加到 E(MST)中，并將頂點(diǎn)3 添加到 V(MST)中并畫(huà)出此邊