【正文】 （ 2）繼續(xù)向下查找得到邊（ 6,7），判斷點(diǎn) 6 和點(diǎn) 7 是否已經(jīng)訪問過了，由于數(shù)組 check 中相應(yīng)的值為 0，因此合并這兩個結(jié)點(diǎn)，得到新的集合 { 7}。在每一次的合并過程結(jié)束時，將會畫出合并之后的集合。 （ 2）初始化過程：為了方便并查集的描述與實(shí)現(xiàn)，通常把先后加入到一個集合中的元素表示成一個樹形結(jié)構(gòu)，并用根節(jié)點(diǎn)來代表這個集合。 （ 7）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 1,2）并畫出此邊，其權(quán)重為 5。此時集合變?yōu)?{1}、 { 4}、 {5}、 { 7}。畫出初始狀態(tài)。 （ 4）如果不符合（ 2）中的判斷則不斷的重復(fù)直到選取的邊等于n1。 （ 5）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫出此邊，其權(quán)重為 4。在 n 個頂點(diǎn)的圖中，選夠 n1條邊即可。 lowCost 的初始值為鄰接矩陣中第 0 行的值，這樣初始時lowCost 中就存放了從集合 V(MST)中頂點(diǎn) 0 到集合 V(G)－ V(MST)中各個頂點(diǎn)的權(quán)值。 （ 4）集合 V(MST)此時已經(jīng)有四個頂點(diǎn)了，即 4，找到與之相連的符合條件的邊 (v4,v5)將權(quán)值為 3的邊添加到 E(MST)中 ，并將頂點(diǎn) 5 添加到 V(MST)中并畫出此邊。 （ 1） (vi,vj) E(G)， v是 V(MST)的頂點(diǎn)，而 vj是還未加入 V(MST)的頂點(diǎn)。在這些算法運(yùn)行過程中實(shí)現(xiàn)的畫圖操作主要通過調(diào)用一個公用的函數(shù)進(jìn)行畫圖的相關(guān)操作?？梢灾朗褂肕FC 通過單文檔畫圖來實(shí)現(xiàn)算法動態(tài)顯示運(yùn)行效果或者使用對話框來實(shí)現(xiàn)算 法動態(tài)顯示運(yùn)行效果，為了方便起見，我選擇的是通過 MFC 建立單文檔來實(shí)現(xiàn)這一效果。 測試數(shù)據(jù)如下： 圖（ 1） 問題分析通過問題的描述，可知這一道題目主要涉及，面向?qū)ο蟮姆治雠c設(shè)計，數(shù)據(jù)結(jié)構(gòu)和算法。所以通過 這次的實(shí)習(xí)，讓我認(rèn)識到只要去嘗試，去努力沒有什么是不可以做的。同時由于對于作圖這方面不是很熟練，沒能實(shí)現(xiàn)對圖的動態(tài)擴(kuò)充，所以只能是實(shí)現(xiàn)對一定數(shù)目，一定邊數(shù)的圖的求解。對于使用 kruskal 算法和深度優(yōu)先搜索結(jié)合的算法，對邊的遍歷至多是 e 次，故其總代價為 O(n^2*e)。 深度優(yōu)先搜索實(shí)現(xiàn) Kruskal算法的測試結(jié)果 圖（ 6） 在這里沒有對深度優(yōu)先搜索的過程給予動態(tài)顯示，主要是模擬了深度優(yōu)先搜索實(shí)現(xiàn) kruskal算法的過程，也即最小生成樹的生成過程。由于并查集的繪制和最小生成樹的繪制沒有太大的關(guān)聯(lián)，因此在這里采用了單獨(dú)繪制并查集實(shí)現(xiàn) kruskal 算法中并查集的合并過程。 下面給出 kruakal 算法利用廣度優(yōu)先搜索進(jìn)行邊連通分量查詢和合并從而得 到最小生成樹的的設(shè)計與實(shí)現(xiàn)步驟： （ 1）對所畫區(qū)域進(jìn)行刷新。 這里采用的廣度優(yōu)先搜索主要是用來檢索邊的鄰接頂點(diǎn)是不是在同一個集合中，由于使 用 kruskal 算法時最初已經(jīng)對邊進(jìn)行了一個排序，所以每一次所選用的邊和通過廣度優(yōu)先搜索對鄰接頂點(diǎn)進(jìn)行判斷的結(jié)果是一樣的，在這里不再給予詳細(xì)的說明， kruskal 算法結(jié)合廣度優(yōu)先搜索具體的運(yùn)算過程和 kruskal 算法結(jié)合深度優(yōu)先搜索的運(yùn)算過程是一樣的，在這里不再列出。 （ 3）如果都已經(jīng)被訪問過了，則利用深度優(yōu)先搜索判斷這兩個節(jié)點(diǎn)是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進(jìn)行標(biāo)記，并畫出此邊和相對應(yīng)的點(diǎn)。 設(shè)計與實(shí)現(xiàn)在這里采用 Kruskal 算法得到最小生成樹的過程中，在對邊連通分量的查詢時使用了深度優(yōu)先搜索的方法來查詢當(dāng)前得到的具有最下權(quán)值的邊的兩個頂點(diǎn)是不是已經(jīng)存在于被訪問過的結(jié)點(diǎn)的集合中，如果是的則進(jìn)行下一次查詢，否則的話則將沒有訪問過的結(jié)點(diǎn)加入已經(jīng)訪問過的結(jié)點(diǎn)的集合中。 （ 4）繼續(xù)向下查找得到邊（ 4,5），判斷點(diǎn) 4 和點(diǎn) 5 是否已經(jīng)訪問過了得知點(diǎn) 4 已經(jīng)被訪問過了，點(diǎn) 5沒有，因此得到新的集合 {2,、 5}。 在這個算法的實(shí)現(xiàn)過程中，邊通分量的查找雖然是深度優(yōu)先搜索為主，但是是以最小生成樹的的生成過 程為主，因此這里所采用的畫圖操做運(yùn)行的情況和使用一般的方法實(shí)現(xiàn) kruskal 算法的運(yùn)行過程是一樣的，在這里不再給予詳細(xì)的說明，如有必要則可以參照 kruskal的生成最小生成樹的過程。這里通過壓縮路 徑的方法來加快后續(xù)的查找速度，主要是通過增加一個 while 循環(huán)，每次都把從結(jié)點(diǎn) i 到集合根節(jié)點(diǎn)的路徑上經(jīng)過的結(jié)點(diǎn)直接設(shè)置為根結(jié)點(diǎn)的子結(jié)點(diǎn)。 設(shè)計與實(shí)現(xiàn) Kruskal 算法利用并查集實(shí)現(xiàn)查找、合并的設(shè)計與實(shí)現(xiàn)也是首先選擇權(quán)值最小的邊，其次是利用并查集來對所要選擇的那些頂點(diǎn)進(jìn)行查找、合并。通過判斷畫出發(fā)生改變的集合 { 5}。 （ 3）在圖 G的邊的集合 E中按存儲次序選擇權(quán)值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7），其權(quán)重為 1。在此過程中不斷的重復(fù)使用一個搜索運(yùn)算，從而確定此元素在哪一個集合中，當(dāng)讀入一個等價對 A≡ B 時，首先檢測 A 和 B是不是屬于同一個集合，如果是，則不用合并；如果不是，則使用一個合并運(yùn)算把 A 和 B 合并到同一個集合中，使得這兩個集合中的任意兩個元素都是等價的（依據(jù)等價的傳遞性）。因此首先將圖 G 的頂點(diǎn)集合 V 分為 n 個等價類，每個等價類包括一個頂點(diǎn)；然后以權(quán)值的大小為順序處理各條邊，如果某條邊連接兩個不同等價類的頂點(diǎn)，則這條邊被添加到 MST（選取的邊不與前面選取的邊構(gòu)成回路），兩個等價類被合并為一個；反復(fù)執(zhí)行此過程，直到只剩下一個等價類。 下面主要通過題目中給出的例子（如圖 1）對 kruskal 算法進(jìn)行詳細(xì)的解析： （ 1）在圖 G的邊的集合 E中按存儲次序選擇權(quán)值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）并畫出此邊，其權(quán)重為 1。 當(dāng)最小生成樹生成完畢時，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 設(shè)計與實(shí)現(xiàn)對于 prime 算法的動態(tài)演示，主要是關(guān)乎兩個函數(shù)的實(shí)現(xiàn)一個是畫圖函數(shù)的實(shí)現(xiàn)，另外一個就是如何判斷何時進(jìn)行畫圖操作并進(jìn)行 相關(guān)操作的畫圖函數(shù)，在這里主要通過兩個函數(shù)實(shí)現(xiàn)一個是與 Kruskal 算法動態(tài)實(shí)現(xiàn)的公用的畫圖操作函數(shù)，另外一個就是 prime 算法尋找最小生成樹的實(shí)現(xiàn)。選出滿足該條件的邊，將 vj 加入 V(MST)， (vi,vj)加入 E(MST)，之后畫出相應(yīng)的邊和新添加進(jìn)去的頂點(diǎn)。對于已經(jīng)選擇的頂點(diǎn)之間的邊存儲在最小生成樹的邊的集合中 E(MST)。 這里主要分為六個模塊，即 prime 算法模塊、 kruskal 算法模塊、用并查集實(shí)現(xiàn) kruskal算法的模塊、 kruskal算法和深度優(yōu)先搜索算法結(jié)合的模塊、 kruskal 算法和廣度優(yōu)先搜索算法結(jié)合的模塊以及畫圖操作的相關(guān)模塊。對于不同的算法其求解最小生成樹時運(yùn)算的效率是不同的，因此還需要對各種算法時間復(fù)雜度進(jìn)行分析和比較， 從而更加深入的理解算法，從而方便我們在不同的場合采用不同的實(shí)現(xiàn)算法。這就需要找到帶權(quán)的最小生成樹。 基本的要求是實(shí)現(xiàn)兩種算 法：通過實(shí)現(xiàn) Kruskal 算法和 Prim 算法來得到圖的最小生成樹。 方案選擇通過對題目的分析，對于如何將廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運(yùn)用到對邊通分量進(jìn)行查詢和合并中有不同的結(jié)合方法。設(shè)計與實(shí)現(xiàn)中由于所體現(xiàn)的重點(diǎn)不同，因此下面的說明主要圍繞著此題的重點(diǎn)，即最小生成樹的生成過程。 Prime算法的具體過程如下： 設(shè)最小生成樹中點(diǎn)的集合 V(MST)和邊的集合 E(MST)的初態(tài)均為空。 下面主要通過題目中給出的例子（如圖 1）對 prime 算法進(jìn)行詳細(xì)的解析： （ 1）將 1 作為起始頂點(diǎn)添加到 V(MST)，找到與之相連的符合條件的邊 (v1,v2)，將權(quán)值為 5 的邊添加到 E(MST)中，并將頂點(diǎn) 2 添加到V(MST)中并畫出此邊。這里僅給出語言描述的實(shí)現(xiàn)過程，源代碼的實(shí)現(xiàn)在后面的附錄中將會給出。 Kruskal 算法通常是在已知 V(MST)=V(G)， E(MST)的初態(tài)為空時對圖 G 進(jìn)行相關(guān)處理的到最小生成樹的。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權(quán)值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7）并畫出此邊，其權(quán)重為 1。 kruskal 算法的設(shè)計與實(shí)現(xiàn)如下所述（具體的代碼實(shí)現(xiàn)見附錄）： （ 1）對所畫區(qū)域進(jìn)行刷新。 在此處實(shí)現(xiàn) Kruskal 算法時主 要使用并查集對相關(guān)頂點(diǎn)進(jìn)行搜索和合并，從而實(shí)現(xiàn)了使用并查集實(shí)現(xiàn) Kruskal 算法。此時集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 { 7}。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫出此邊，其權(quán)重為 4。在 Kruskal 使用并查集時首先對其進(jìn)行邊 集合的排序，接著利用并查集對圖 G 中的頂點(diǎn)進(jìn)行初始化，每一個頂點(diǎn)當(dāng)做一個集合，同時給其一個相關(guān)的變量標(biāo)志其集合中頂點(diǎn)的數(shù)目；然后利用并查集判斷此時的頂點(diǎn)所在集合是不是相同，如果不相同則合并這兩個頂點(diǎn)所在的集合。 （ 4）合并：兩個集合合并時，任何一方均可作為另一方的子孫。對于深度優(yōu)先搜索方法的實(shí)現(xiàn)這里使用的方法是通過利用棧這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的。同時通過深度優(yōu)先搜索對著兩個結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記，可知點(diǎn) 5 此時被標(biāo)記訪問過了。 深度優(yōu)先搜索的實(shí)現(xiàn)主要利用棧這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。 （ 4）選擇下一條沒有被訪問過的邊重新進(jìn)行（ 1）、（ 2）的判斷，直到所有的頂點(diǎn)均已被訪問過且在同一個集合中，即已經(jīng)添加到了最小生成樹中則最小生成樹生成完畢。由于本題的重點(diǎn)是最小生成樹的生成，在這里不再給出廣度優(yōu)先搜索具體的搜索過程。 （ 2）對已經(jīng)排好序的邊進(jìn)行選擇，對沒有訪問過的最小權(quán)值的邊的兩個結(jié)點(diǎn)進(jìn)行判斷，檢查是否已經(jīng)被訪問過了，如果有一個沒有被訪問過，則將和此邊相應(yīng)的頂點(diǎn)進(jìn)行廣度優(yōu)先搜索的判斷之后進(jìn)行標(biāo)記，同時畫出所選擇的這個邊和相應(yīng)的頂點(diǎn)。 三．系統(tǒng)測試 圖（ 2） 上圖是利用程序直接得到的原圖形，此測試數(shù)據(jù)中有七個頂點(diǎn)，有十條邊。通過對比前兩種 kruskal算法的實(shí)現(xiàn)過程可知其運(yùn)行是一致的。 效率分析 Prime 算法實(shí)現(xiàn)的函數(shù)主要是一個兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點(diǎn)個數(shù) n，所以該算法的時間復(fù)雜度為 O(n^2)。為了我的程序更加完美我會繼續(xù)努力，從而實(shí)現(xiàn)圖的動態(tài)擴(kuò)充，同時讓程序更為簡練。 參考文獻(xiàn)： [1]朱戰(zhàn)立，數(shù)據(jù)結(jié)構(gòu) — 使用 c 語言（第四版），電子工業(yè)出版社2021年 11 月 [2]王桂平、王衍、任嘉辰，圖論算法理論、實(shí)現(xiàn)及應(yīng)用，北京大學(xué)出版社， 2021 年 1月 [3]孫鑫、余安萍， VC++深入詳解，電子工業(yè)出版社 2021年 5月 第二篇：軟件綜合實(shí)習(xí)報告 軟件綜合實(shí)習(xí)報告 題目：最小生成樹算法 院（系）： 計算機(jī)學(xué)院 專 業(yè)： 計算機(jī)科學(xué)與技術(shù) 姓 名： 班級學(xué)號： 2021年 9月 12 日 目錄一．系統(tǒng)需求分析與總體設(shè)計 ............................................................................1 需 求 分析?????????????????????????????????????????? 1 問 題 描述???????????????????????????????????????? 1 問題 分析???????????????????????????????????????? 1 方 案 選擇???????????????????????????????????????? 1 開 發(fā) 平臺???????????????????????????????????????? 2 系 統(tǒng) 總 體 設(shè)計?????????????????????????????????????? .2 二．詳細(xì)設(shè)計與系統(tǒng)實(shí)現(xiàn) .......................................................................................2 算 法 動 態(tài) 演 示模?? .?????? .????????