【正文】 同時(shí)通過(guò)。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)這兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷及標(biāo)記已經(jīng)訪問(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)的。其基本思想是：對(duì)于一個(gè)無(wú)向連通圖，從某一個(gè)起始結(jié)點(diǎn) vi 出發(fā)，訪問(wèn)與它相連的一個(gè)結(jié)點(diǎn) vj，且 vi、 vj這兩個(gè)結(jié)點(diǎn)之間的邊（ vi、 vj）是所有以 vi 為連接結(jié)點(diǎn)的邊中權(quán)值最小的；然后再?gòu)?vj 出發(fā)尋找與 vj 相連的頂點(diǎn)，且它們之間的邊是所有以 vi 為連接結(jié)點(diǎn)的邊中權(quán)值最小的，不斷的重復(fù)直到找到訪問(wèn)完所有的結(jié)點(diǎ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)的一種遍歷方法。這樣處理可以減少樹(shù)中深層次元素的個(gè)數(shù)，減少后續(xù)查找時(shí)間。 （ 4）合并：兩個(gè)集合合并時(shí)，任何一方均可作為另一方的子孫。在此函數(shù)中如果只靠一個(gè)循環(huán)來(lái)得到結(jié)果，則對(duì)于合并中得到的層次比 較深的集合，查找會(huì)很費(fèi)時(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è)元素。 （ 1）對(duì)所畫區(qū)域進(jìn)行刷新。在 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)所在的集合。 至此 kruskal 算法利用并查集查找、合并的過(guò)程結(jié)束，通過(guò)kruskal算法得到最小生成樹(shù)及生成過(guò)程，其最小生成樹(shù)的權(quán)值為 16。此時(shí)集合變?yōu)?{ 7}。通過(guò)判斷畫出發(fā)生改變的集合 { 7}。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫出此邊，其權(quán)重為 4。此時(shí)集合變?yōu)?{1}、 { 5}、 { 7}。通過(guò)判斷畫出發(fā)生改變的集合 { 4}。 （ 4）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 2,4）并畫出此邊，其權(quán)重為 2。此時(shí)集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 { 7}。通過(guò)判斷畫出發(fā)生改變的集合 { 3}。 （ 2）在圖 G的邊的集合 E中按存儲(chǔ)次序選擇權(quán)值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲(chǔ)，所以此處選擇的邊（ 2,3）其權(quán)重為 1。 下面通過(guò)題目的例子（如圖 1）對(duì) kruskal 算法利用并查集實(shí)現(xiàn)過(guò)程中相應(yīng)集合的變化進(jìn)行了詳細(xì)的解析： （ 1）最初的集合有 7個(gè)，這 7個(gè)集合中均只有一個(gè)元素分別為 {1}、{2}、 {3}、 {4}、 {5}、 {6}、 {7}。 在此處實(shí)現(xiàn) Kruskal 算法時(shí)主要使用并查集對(duì)相關(guān)頂點(diǎn)進(jìn)行搜索和合并，從而實(shí)現(xiàn)了使用并查集實(shí)現(xiàn) Kruskal 算法。最初把每一個(gè)對(duì)象看做是一個(gè)單元集合，然后依次按順序讀入一個(gè)等價(jià)對(duì)后，將等價(jià)對(duì)中的兩個(gè)元素所在的集合合并。 （ 5）當(dāng)最小生成樹(shù)生成完畢時(shí)，則調(diào)用 Draw（ E）函數(shù)畫出生成的過(guò)程。 （ 3）判斷找到的邊的數(shù)目是否小于頂點(diǎn)的數(shù)目減一，即 n1，如果是則從沒(méi)有被選中的邊中選取權(quán)值最小的邊，如果放入存儲(chǔ)邊的集合中不構(gòu)成回路則添加進(jìn)去，否則舍去此邊。 kruskal 算法的設(shè)計(jì)與實(shí)現(xiàn)如下所述（具 體的代碼實(shí)現(xiàn)見(jiàn)附錄）： （ 1）對(duì)所畫區(qū)域進(jìn)行刷新。 模塊設(shè)計(jì)與實(shí)現(xiàn) Kruskal 算法的實(shí)現(xiàn)主要包含兩個(gè)部分，即帶權(quán)值的邊的排序和判斷選取的邊的兩個(gè)頂點(diǎn)是否屬于同一個(gè)連通分量。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 1,2）并畫出此邊，其權(quán)重為 5。 （ 4）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,5）并畫出此邊，其權(quán)重為 3。 （ 2）在圖 G的邊的集合 E中按存儲(chǔ)次序選擇權(quán)值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲(chǔ)，所以后選擇邊（ 6,7）并畫出此邊，其權(quán)重為 1。 （ 3）如此反復(fù)下去，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。具體如下： （ 1） 構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn)沒(méi)有邊的非連通圖 T，圖中的每個(gè)頂點(diǎn)為一個(gè)連通分量。每次挑選邊成功了即畫出此邊。 動(dòng)態(tài)演示模塊 Kruskal 算法通常是在已知 V(MST)=V(G)， E(MST)的初態(tài)為空時(shí)對(duì)圖 G 進(jìn)行相關(guān)處理的到最小生成樹(shù)的。 存 第 k 個(gè)頂點(diǎn)的數(shù)據(jù)和相應(yīng)邊的權(quán)值到 MST 中，并將lowCost[k]置為 1，表示第 k 個(gè)頂點(diǎn)從集合 V(G)－ V(MST)加入了集合V(MST)中 當(dāng)?shù)?k 個(gè)頂點(diǎn)加入到集合 V(MST)后，若存在一條邊 (k,j)，其中 k 是集合 V(MST)的頂點(diǎn)， j是集合 V(G)－ V(MST)的頂點(diǎn)，且邊 (k,j)權(quán)值較原先 lowCost[j]的代價(jià)更小，則用這個(gè)權(quán)值修正原先 lowCost[j]中的權(quán)值。 （ 3）循環(huán) n1次 lowCost 中尋找具有最小權(quán)值的邊。 （ 2） MST頂點(diǎn)初始值 ={序號(hào)為 0的頂點(diǎn) }，其邊所在的結(jié)構(gòu)體數(shù)組 E[n1]的值也為空。這里僅給出語(yǔ)言描述的實(shí)現(xiàn)過(guò)程，源代碼的實(shí)現(xiàn)在后面的附錄中將會(huì)給出。 至此圖 G中所有的點(diǎn)均已添加到了 V(MST)，最小生成樹(shù)生成完畢，其 權(quán)值為 16。 （ 5）集合 V(MST)此時(shí)已經(jīng)有五個(gè)頂點(diǎn)了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權(quán)值為 4 的邊添加到 E(MST)中，并將頂點(diǎn) 6 添加到 V(MST)中并畫出此邊。 （ 3）集合 V(MST)此時(shí)已經(jīng)有三個(gè)頂點(diǎn)了，即 3，找到與之相連的符合條件的邊 (v2,v4)將權(quán)值為 2 的邊添加到 E(MST)中，并將頂點(diǎn) 4 添加到 V(MST)中并畫出此邊。 下面主要通過(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)中并畫出此邊。 （ 2） (vi,vj)是關(guān)聯(lián)于 V(MST)中頂點(diǎn)的邊中權(quán)值最小的邊。此時(shí) (vi,vj)一定均未加入 E(MST)。然后，依次選出 n1 條符合以下條件的邊(vi,vj)。 Prime算法的具體過(guò)程如下： 設(shè)最小生成樹(shù)中點(diǎn)的集合 V(MST)和邊的集合 E(MST)的初態(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)。 二．詳細(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)集合中。 對(duì)于算法運(yùn)行時(shí)的動(dòng)態(tài)顯示運(yùn)行過(guò)程這一要求主要通過(guò)將相關(guān)的畫圓、畫線等相關(guān)畫圖的操作扦插到相關(guān)的算法中，在算法的運(yùn)行過(guò)程中再通過(guò)對(duì)相關(guān)條件的判斷從而決定是否執(zhí)行畫圓、畫線等操作。設(shè)計(jì)與實(shí)現(xiàn)中由于所體現(xiàn)的重點(diǎn)不同，因此下面的說(shuō)明主要圍繞著此題的重點(diǎn)，即最小生成樹(shù)的生成過(guò)程。 在深度優(yōu)先搜索算法（ BreadthFirstSearch）中使用 了棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)邊的連通分量的查詢，對(duì)廣度優(yōu)先搜索算法(DepthFirstSearch)的實(shí)現(xiàn)使用了隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)，這里的隊(duì)列和棧都是通過(guò)編程實(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ì)于運(yùn)用圖形學(xué)的知識(shí)實(shí)現(xiàn)算法的動(dòng)態(tài)運(yùn)行效果。 方案選擇通過(guò)對(duì)題目的分析，對(duì)于如何將廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運(yùn)用到對(duì)邊通分量進(jìn)行查詢和合并中有不同的結(jié)合方法。 為了更好、更生動(dòng)的表示這些算法的運(yùn)算過(guò)程，在這里如果使用動(dòng)態(tài)顯示算法的求 解過(guò)程將會(huì)是最好的選擇。通過(guò)這些利用知識(shí)實(shí)現(xiàn)Kruskal 算法和 Prim 算法從而得到圖的最小生成樹(shù)。較高的要求是在邊通分量的查詢與合并的過(guò)程中，采用廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法，并進(jìn)行分析和比較算法時(shí)間復(fù)雜度。 基本的要求是實(shí)現(xiàn)兩種算法：通過(guò)實(shí)現(xiàn) Kruskal 算法和 Prim 算法來(lái)得到圖的最小生成樹(shù)。例如：要在 n 個(gè)城市之間鋪設(shè)光纜，主要目標(biāo)是要使這 n 個(gè)城市的任意兩個(gè)之間都可以通信，但鋪設(shè)光纜的費(fèi)用很高，且各個(gè)城市之 間鋪設(shè)光纜的費(fèi)用不同；另一個(gè)目標(biāo)是要使鋪設(shè)光纜的總費(fè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é)院 專 業(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 基 本 思想?????????