国产第页,国产精品视频一区二区三区,国产精品网站夜色,久久艹影院,精品国产第一页,欧美影视一区二区三区,国产在线欧美日韩精品一区二区

軟件綜合實(shí)習(xí)報(bào)告

發(fā)布時(shí)間:2020-11-01 來(lái)源: 思想?yún)R報(bào) 點(diǎn)擊:

 軟件綜合實(shí)習(xí)報(bào)告

  題目:最小生成樹(shù)算法

 院(系):

 計(jì)算機(jī)學(xué)院

  專(zhuān)

 業(yè):

 計(jì)算機(jī)科學(xué)與技術(shù)

 姓

 名:

 班級(jí)學(xué)號(hào):

 2012 年 9 月 12 日

 目錄 一 . 系統(tǒng)需求分析與總體設(shè)計(jì)

 ............................................................................ 1

 1.1 需求分析 ……………………………………………………………………………………………………………… 1

 1.1.1 問(wèn)題描述…………………………………………………………………………………………………………1

 1.1.2 問(wèn)題分析…………………………………………………………………………………………………………1

 1.1.3 方案選擇…………………………………………………………………………………………………………1

  1.1.4 開(kāi)發(fā)平臺(tái)…………………………………………………………………………………………………………2

  1.2 系統(tǒng)總體設(shè)計(jì) ……………………………………………………………………………………………………. 2

 二 . 詳細(xì)設(shè)計(jì)與系統(tǒng)實(shí)現(xiàn)

 ....................................................................................... 2

 2.1 Prime 算法動(dòng)態(tài)演示模 ……. ……………….……………………………………………………………. 2

  2.1.1 基本思想…………………………………………………………………………………………………………2

 2.1.2 設(shè)計(jì)與實(shí)現(xiàn)……………………………………………………………………………………………………..3

  2.2

  Kruskal 算法動(dòng)態(tài)演示模塊 ………………………………………………………………………. 4

  2.2.1 基本思想…………………………………………………………………………………………………………4

 2.2.2 設(shè)計(jì)與實(shí)現(xiàn)………………………………………………………………………………………………………4

  2.3

 并查集實(shí)現(xiàn) kruskal 算法動(dòng)態(tài)演示模塊 ……………………………………………….. 4

  2.3.1 基本思想…………………………………………………………………………………………………………5

 2.3.2 設(shè)計(jì)與實(shí)現(xiàn)………………………………………………………………………………………………………5

  2.4 深 度優(yōu)先搜索實(shí)現(xiàn) Kruskal 算法動(dòng)態(tài) 演示模塊 ………………………………. 6

  2.4.1 基本思想…………………………………………………………………………………………………………6

 2.4.2 設(shè)計(jì)與實(shí)現(xiàn)………………………………………………………………………………………………………7

  2.5

 廣度優(yōu)先搜索實(shí)現(xiàn) Kruskal 算法動(dòng)態(tài)演示模塊 ………………………………. 7

  2.5.1 基本思想…………………………………………………………………………………………………………7

 2.5.2 設(shè)計(jì)與實(shí)現(xiàn)………………………………………………………………………………………………………8

  2.6 畫(huà)圖模塊 ……………………………………………………………………………………………………………….. 8

 三 .系統(tǒng)測(cè)試

 .................................................................................................................. 9

 3.1 測(cè)試數(shù)據(jù) ……………………………………………………………………………… 9

 3.2Primme 的測(cè)試結(jié)果 ………………………………………….…………………… 9

 3.2Kruskal 算法的測(cè)試結(jié)果 ………………………………………….………..…. 10

 3.3 并查集實(shí)現(xiàn)Kruskal 算法的測(cè)試結(jié)果 ……………………………………. 10

 3.4 深度優(yōu)先搜索實(shí)現(xiàn)Kruskal 算法的測(cè)試結(jié)果 …………………………. 11

 3.5 廣度優(yōu)先搜索實(shí)現(xiàn)Kruskal 算法的測(cè)試結(jié)果 …………………………. 11

 3.6 效率分析 ……………………………………………………………………………. 12

 四 . 總結(jié)

 ........................................................................................................................... 12

 參考資料 ……………………………………………………………………………………………………………………. 13

 一. 系統(tǒng)需求分析與總體設(shè)計(jì) 1 1.1 需求分析

 1.1.1 問(wèn)題描述 在一個(gè)具有幾個(gè)頂點(diǎn)的連通圖 G 中,如果存在子圖 G" 包含 G 中所有頂點(diǎn)和一部分邊,且不形成回路,則稱 G" 為圖 G 的生成樹(shù),代價(jià)最小生成樹(shù)則稱為最小生成樹(shù)(Minimal Spanning Tree)。

 許多應(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)行分析和比較。較高的要求是在邊通分量的查詢與合并的過(guò)程中,采用廣度優(yōu)先搜索算法(Breadth First Search)、深度優(yōu)先搜索算法(Depth First Search)和并查集(Union-Find Set)這三種方法,并進(jìn)行分析和比較算法時(shí)間復(fù)雜度。

 測(cè)試數(shù)據(jù)如下:

 圖(1)

 1.1.2 問(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)行查詢和合并,由題可知要對(duì)邊通分量進(jìn)行查詢和合并要使用廣度優(yōu)先搜索算法(Breadth First Search)、深度優(yōu)先搜索算法(Depth First Search)和并查集(Union-Find Set)這三種方法。

 為了更好、更生動(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)算法。

 1.1.3 方案選擇 通過(guò)對(duì)題目的分析,對(duì)于如何將廣度優(yōu)先搜索算法(Breadth First Search)、深度優(yōu)先搜132 5 4 6 5 6 5 2 4 4 7

 3 1 7 1

 索算法(Depth First Search)和并查集(Union-Find Set)這三種方法運(yùn)用到對(duì)邊通分量進(jìn)行查詢和合并中有不同的結(jié)合方法。在這里我選擇了將這三種搜索算法融合到 Kruskal 算法,因?yàn)槲矣X(jué)得在 Kruskal 算法對(duì)邊通分量進(jì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)行效果?梢灾朗褂 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)這一效果。

 1.1.4 開(kāi)發(fā)平臺(tái) 使用的系統(tǒng)是 Windows07 , 開(kāi)發(fā)工具 VC++6.0 2 1.2 系統(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)先搜索算法(Breadth First Search)中使用了棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)邊的連通分量的查詢,對(duì)廣度優(yōu)先搜索算法(Depth First Search)的實(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) e 2.1 Prime 算法動(dòng)態(tài)演示模塊

 2.1.1 基本思想

  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)中。然后,依次選出 n-1條符合以下條件的邊(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)值最小的邊。選出滿足該條件的邊,將

  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)了,即 1、2,找到與之相連的符合條件的邊(v2,v3) 將權(quán)值為 1 的邊添加到 E(MST)中,并將頂點(diǎn) 3 添加到 V(MST)中并畫(huà)出此邊。

 (3)集合 V(MST)此時(shí)已經(jīng)有三個(gè)頂點(diǎn)了,即 1、2、3,找到與之相連的符合條件的邊(v2,v4)將權(quán)值為 2 的邊添加到 E(MST)中,并將頂點(diǎn) 4 添加到 V(MST)中并畫(huà)出此邊。

。4)集合 V(MST)此時(shí)已經(jīng)有四個(gè)頂點(diǎn)了,即 1、2、3、4,找到與之相連的符合條件的邊(v4,v5)將權(quán)值為 3 的邊添加到 E(MST)中,并將頂點(diǎn) 5 添加到 V(MST)中并畫(huà)出此邊。

。5)集合 V(MST)此時(shí)已經(jīng)有五個(gè)頂點(diǎn)了,即 1、2、3、4、5,找到與之相連的符合條件的邊(v4,v6)將權(quán)值為 4 的邊添加到 E(MST)中,并將頂點(diǎn) 6 添加到 V(MST)中并畫(huà)出此邊。

 (6)集合 V(MST)此時(shí)已經(jīng)有六個(gè)頂點(diǎn)了,即 1、2、3、4、5、6,找到與之相連的符合條件的邊(v6,v7)將權(quán)值為1的邊添加到E(MST)中,并將頂點(diǎn)7添加到V(MST)中并畫(huà)出此邊。

 至此圖 G 中所有的點(diǎn)均已添加到了 V(MST),最小生成樹(shù)生成完畢,其權(quán)值為 16。

 2.1.2 設(shè)計(jì)與實(shí)現(xiàn) 對(duì)于 prime 算法的動(dòng)態(tài)演示,主要是關(guān)乎兩個(gè)函數(shù)的實(shí)現(xiàn)一個(gè)是畫(huà)圖函數(shù)的實(shí)現(xiàn),另 外一個(gè)就是如何判斷何時(shí)進(jìn)行畫(huà)圖操作并進(jìn)行相關(guān)操作的畫(huà)圖函數(shù),在這里主要通過(guò)兩個(gè)函數(shù)實(shí)現(xiàn)一個(gè)是與 Kruskal 算法動(dòng)態(tài)實(shí)現(xiàn)的公用的畫(huà)圖操作函數(shù),另外一個(gè)就是 prime 算法尋找最小生成樹(shù)的實(shí)現(xiàn)。這里僅給出語(yǔ)言描述的實(shí)現(xiàn)過(guò)程,源代碼的實(shí)現(xiàn)在后面的附錄中將會(huì)給出。

 Prime 算法的設(shè)計(jì)與實(shí)現(xiàn) 如下所述:

。1)對(duì)所畫(huà)區(qū)域刷新。

。2)

 MST 頂點(diǎn)初始值={序號(hào)為 0 的頂點(diǎn)},其邊所在的結(jié)構(gòu)體數(shù)組 E[n-1]的值也為空。lowCost的初始值為鄰接矩陣中第0行的值,這樣初始時(shí)lowCost中就存放了從集合V(MST)中頂點(diǎn) 0 到集合 V(G)-V(MST)中各個(gè)頂點(diǎn)的權(quán)值 。

。3)循環(huán) n-1 次 2.1 從 lowCost 中尋找具有最小權(quán)值的邊。根據(jù) lowCost 的定義,這樣的邊其一個(gè)頂點(diǎn)必然為集合 V(MST)中的頂點(diǎn),其另一個(gè)頂點(diǎn)(設(shè)第 k 個(gè)頂點(diǎn))必然為集合 V(G)-V(MST)中的頂點(diǎn) ,將相應(yīng)的邊添加到 E[n-1]中。

 2.2 存第 k 個(gè)頂點(diǎn)的數(shù)據(jù)和相應(yīng)邊的權(quán)值到 MST 中,并將 lowCost[k]置為-1,表示第k 個(gè)頂點(diǎn)從集合 V(G)-V(MST)加入了集合 V(MST)中

 2.3 當(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)值。

 2.4 當(dāng)最小生成樹(shù)生成完畢時(shí),則調(diào)用 Draw(E)函數(shù)畫(huà)出生成的過(guò)程。

 l 2.2 Kruskal 算法動(dòng)態(tài)演示模塊

 2.2.1 基本思想 Kruskal 算法通常是在已知 V(MST)=V(G),E(MST)的初態(tài)為空時(shí)對(duì)圖 G 進(jìn)行相關(guān)處理的到最小生成樹(shù)的。首先將圖中所有邊按權(quán)值遞增順序排列,依次選定取權(quán)值較小的邊,但要求后面選取的邊不能與前面選取的邊構(gòu)成回路,若構(gòu)成回路,則放棄該條邊,再去選后面權(quán)值較大的邊。每次挑選邊成功了即畫(huà)出此邊。在 n 個(gè)頂點(diǎn)的圖中,選夠 n-1 條邊即可。具體如下:

 (1)

 構(gòu)造一個(gè)只有 n 個(gè)頂點(diǎn)沒(méi)有邊的非連通圖 T,圖中的每個(gè)頂點(diǎn)為一個(gè)連通分量。

。2)

 在原圖 G 中的邊中選擇具有最小權(quán)值的邊,若該邊的兩個(gè)頂點(diǎn)落在不同的連 通分量上,則將此邊加入到 T 中;否則,則將此邊舍去(此后永不選入此邊),重新選擇一條權(quán)值最小的邊并進(jìn)行畫(huà)圖的操作處理。

 (3)如此反復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。

 下面主要通過(guò)題目中給出的例子(如圖 1)對(duì) kruskal 算法進(jìn)行詳細(xì)的解析:

。1)在圖 G 的邊的集合 E 中按存儲(chǔ)次序選擇權(quán)值最小的邊,即(2,3)由于邊(2,3)在(6,7)前面存儲(chǔ),所以此處選擇的邊(2,3)并畫(huà)出此邊,其權(quán)重為 1。

 (2)在圖 G 的邊的集合 E 中按存儲(chǔ)次序選擇權(quán)值最小的邊,即(6,7)由于邊(6,7)在(2,3)后面存儲(chǔ),所以后選擇邊(6,7)并畫(huà)出此邊,其權(quán)重為 1。

。3)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(2,4)并畫(huà)出此邊,其權(quán)重為 2。

 (4)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(4,5)并畫(huà)出此邊,其權(quán)重為 3。

。5)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(4,6)并畫(huà)出此邊,其權(quán)重為 4。

。6)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(1,2)并畫(huà)出此邊,其權(quán)重為 5。

 至此通過(guò) kruskal 算法得到最小生成樹(shù)及生成過(guò)程,其最小生成樹(shù)的權(quán)值為 16。

 2.2.1 模塊設(shè)計(jì)與實(shí)現(xiàn) Kruskal 算法的實(shí)現(xiàn)主要包含兩個(gè)部分,即帶權(quán)值的邊的排序和判斷選取的邊的兩個(gè)頂點(diǎn)是否屬于同一個(gè)連通分量。因此首先將圖 G 的頂點(diǎn)集合 V 分為 n 個(gè)等價(jià)類(lèi),每個(gè)等價(jià)類(lèi)包括一個(gè)頂點(diǎn);然后以權(quán)值的大小為順序處理各條邊,如果某條邊連接兩個(gè)不同等價(jià)類(lèi)的頂點(diǎn),則這條邊被添加到 MST(選取的邊不與前面選取的邊構(gòu)成回路),兩個(gè)等價(jià)類(lèi)被合并為一個(gè);反復(fù)執(zhí)行此過(guò)程,直到只剩下一個(gè)等價(jià)類(lèi)。

 kruskal 算法的設(shè)計(jì)與實(shí)現(xiàn)如下所述(具體的代碼實(shí)現(xiàn)見(jiàn)附錄):

。1)對(duì)所畫(huà)區(qū)域進(jìn)行刷新。

。2)設(shè)置查找到的頂點(diǎn)集合 find[n]所有的值為-1,存儲(chǔ)邊的集合 E[n-1]為空集。

。3)判斷找到的邊的數(shù)目是否小于頂點(diǎn)的數(shù)目減一,即 n-1,如果是則從沒(méi)有被選中的邊中選取權(quán)值最小的邊,如果放入存儲(chǔ)邊的集合中不構(gòu)成回路則添加進(jìn)去,否則舍去此邊。

。4)如果不符合(2)中的判斷則不斷的重復(fù)直到選取的邊等于 n-1。

 (5)當(dāng)最小生成樹(shù)生成完畢時(shí),則調(diào)用 Draw(E)函數(shù)畫(huà)出生成的過(guò)程。

 3 2.3 并查集實(shí)現(xiàn) l kruskal 算法動(dòng)態(tài)演示模塊

 2.3.1 基本思想 并查集處理問(wèn)題的主要思想是在處理時(shí)使用搜索與合并運(yùn)算對(duì)相關(guān)集合進(jìn)行處理。最初 把每一個(gè)對(duì)象看做是一個(gè)單元集合,然后依次按順序讀入一個(gè)等價(jià)對(duì)后,將等價(jià)對(duì)中的兩個(gè)元素所在的集合合并。在此過(guò)程中不斷的重復(fù)使用一個(gè)搜索運(yùn)算,從而確定此元素在哪一個(gè)集合中,當(dāng)讀入一個(gè)等價(jià)對(duì) A≡B 時(shí),首先檢測(cè) A 和 B 是不是屬于同一個(gè)集合,如果是,則不用合并;如果不是,則使用一個(gè)合并運(yùn)算把 A 和 B 合并到同一個(gè)集合中,使得這兩個(gè)集合中的任意兩個(gè)元素都是等價(jià)的(依據(jù)等價(jià)的傳遞性)。

 在此處實(shí)現(xiàn) Kruskal 算法時(shí)主要使用并查集對(duì)相關(guān)頂點(diǎn)進(jìn)行搜索和合并,從而實(shí)現(xiàn)了使用并查集實(shí)現(xiàn) Kruskal 算法。在程序中也實(shí)現(xiàn)了并查集的動(dòng)態(tài)演示,通過(guò) Kruskal 算法調(diào)用并查集的函數(shù),在函數(shù)中 對(duì)相關(guān)的頂點(diǎn)信息進(jìn)行判斷從而實(shí)施相應(yīng)的畫(huà)圖操作。

 下面通過(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}。畫(huà)出初始狀態(tài)。

。2)在圖 G 的邊的集合 E 中按存儲(chǔ)次序選擇權(quán)值最小的邊,即(2,3)由于邊(2,3)在(6,7)前面存儲(chǔ),所以此處選擇的邊(2,3)其權(quán)重為 1。此時(shí)集合變?yōu)閧1}、{2、3}、{4}、 {5}、{6}、{7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合{2、3}。

 (3)在圖 G 的邊的集合 E 中按存儲(chǔ)次序選擇權(quán)值最小的邊,即(6,7)由于邊(6,7)在(2,3)后面存儲(chǔ),所以后選擇邊(6,7),其權(quán)重為 1。此時(shí)集合變?yōu)閧1}、{2、3}、{4}、 {5}、{6、7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合{6、7}。

。4)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(2,4)并畫(huà)出此邊,其權(quán)重為 2。此時(shí)集合變?yōu)閧1}、{2、3、4}、{5}、{6、7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合{2、3、4}。

 (5)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(4,5)并畫(huà)出此邊,其權(quán)重為 3。此時(shí)集合變?yōu)閧1}、{2、3、4、5}、{6、7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合{2、3、4、5}。

。6)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(4,6)并畫(huà)出此邊,其權(quán)重為 4。此時(shí)集合變?yōu)閧1}、{2、3、4、5、6、7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合{2、3、4、5、6、7}。

。7)在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊(1,2)并畫(huà)出此邊,其權(quán)重為 5。此時(shí)集合變?yōu)閧1、2、3、4、5、6、7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合{1、2、3、4、5、6、7}。

 至此 kruskal 算法利用并查集查找、合并的過(guò)程結(jié)束,通過(guò) kruskal 算法得到最小生成樹(shù)及生成過(guò)程,其最小生成樹(shù)的權(quán)值為 16。

 2.3.2 設(shè)計(jì)與實(shí)現(xiàn) Kruskal 算法利用并查集實(shí)現(xiàn)查找、合并的設(shè)計(jì)與實(shí)現(xiàn)也是首先選擇權(quán)值最小的邊,其次是利用并查集來(lái)對(duì)所要選擇的那些頂點(diǎn)進(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)所在的集合。

 并查集的實(shí)現(xiàn)主要包含三個(gè)方面,即并查集的初始化、查找和集合的合并,下面主要介紹并查集這三個(gè)過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)。

。1)對(duì)所畫(huà)區(qū)域進(jìn)行刷新。

。2)初始化過(guò)程:為了方便并查集的描述與實(shí)現(xiàn),通常把先后加入到一個(gè)集合中的元素表示成一個(gè)樹(shù)形結(jié)構(gòu),并用根節(jié)點(diǎn)來(lái)代表這個(gè)集合。這里定義一個(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è)元素。

。3)查找:主要是查找并返回結(jié)點(diǎn) i 所屬集合的根節(jié)點(diǎn)。在此函數(shù)中如果只靠一個(gè)循環(huán)來(lái)得到結(jié)果,則對(duì)于合并中得到的層次比較深的集合,查找會(huì)很費(fèi)時(shí)。這里通過(guò)壓縮路徑的方法來(lái)加快后續(xù)的查找速度,主要是通過(guò)增加一個(gè) while 循環(huán),每次都把從結(jié)點(diǎn) i 到集合根節(jié)點(diǎn)的路徑上經(jīng)過(guò)的結(jié)點(diǎn)直接設(shè)置為根結(jié)點(diǎn)的子結(jié)點(diǎn)。

 (4)合并:兩個(gè)集合合并時(shí),任何一方均可作為另一方的子孫。在這里采用的是加權(quán)合并,即把兩個(gè)集合中元素個(gè)數(shù)少的根結(jié)點(diǎn)作為元素個(gè)數(shù)多的根節(jié)點(diǎn)的子結(jié)點(diǎn)。這樣處理可以減少樹(shù)中深層次元素的個(gè)數(shù),減少后續(xù)查找時(shí)間。在每一次的合并過(guò)程結(jié)束時(shí),將會(huì)畫(huà)出合并之后的集合。

 2.4 深度優(yōu)先搜索實(shí)現(xiàn) l Kruskal 算法動(dòng)態(tài)演示模塊

 2.4.1 基本思想 深度優(yōu)先搜索主要是在圖的遍歷中使用此方法對(duì)整個(gè)圖進(jìn)行遍歷來(lái)訪問(wèn)整個(gè)圖中所有節(jié)點(diǎn)的一種遍歷方法。通常是利用遞歸來(lái)實(shí)現(xiàn)圖中結(jié)點(diǎ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)為止。

 在這個(gè)算法的實(shí)現(xiàn)過(guò)程中,邊通分量的查找雖然是深度優(yōu)先搜索為主,但是是以最小生成樹(shù)的的生成過(guò)程為主,因此這里所采用的畫(huà)圖操做運(yùn)行的情況和使用一般的方法實(shí)現(xiàn)kruskal 算法的運(yùn)行過(guò)程是一樣的,在這里不再給予詳細(xì)的說(shuō)明,如有必要?jiǎng)t可以參照 kruskal的生成最小生成樹(shù)的過(guò)程。對(duì)于深度優(yōu)先搜索方法的實(shí)現(xiàn)這里使用的方法是通過(guò)利用棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。下面僅給出在邊已經(jīng)通過(guò)權(quán)值大小進(jìn)行排序之后,邊通分量的查找的過(guò)程和查找之后集合的合并情況 (1)得到圖 G 中最小權(quán)值的邊(2,3),因?yàn)椋?,3)排在(6,7)的前面,所以先判斷它的兩個(gè)結(jié)點(diǎn),判斷點(diǎn) 2 和點(diǎn) 3 是否已經(jīng)訪問(wèn)過(guò)了,由于數(shù)組 check 中相應(yīng)的值為 0,說(shuō)明沒(méi)有被訪問(wèn)過(guò),因此合并這兩個(gè)結(jié)點(diǎn)為一個(gè)集合{2、3}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)這兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷及標(biāo)記已經(jīng)訪問(wèn)過(guò)了。

 (2)繼續(xù)向下查找得到邊(6,7),判斷點(diǎn) 6 和點(diǎn) 7 是否已經(jīng)訪問(wèn)過(guò)了,由于數(shù)組 check中相應(yīng)的值為 0,因此合并這兩個(gè)結(jié)點(diǎn),得到新的集合{6、7}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)這兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷及標(biāo)記已經(jīng)訪問(wèn)過(guò)了。

  (3)繼續(xù)向下查找得到邊(2,4),判斷點(diǎn) 2 和點(diǎn) 4 是否已經(jīng)訪問(wèn)過(guò)了得知點(diǎn) 2 已經(jīng)被訪問(wèn)過(guò)了,點(diǎn) 4 沒(méi)有,因此得到新的集合{2,、3、4}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)著兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記,可知點(diǎn) 4 此時(shí)被標(biāo)記訪問(wèn)過(guò)了。

  (4)繼續(xù)向下查找得到邊(4,5),判斷點(diǎn) 4 和點(diǎn) 5 是否已經(jīng)訪問(wèn)過(guò)了得知點(diǎn) 4 已經(jīng)被訪問(wèn)過(guò)了,點(diǎn) 5 沒(méi)有,因此得到新的集合{2,、3、4、5}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)著兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記,可知點(diǎn) 5 此時(shí)被標(biāo)記訪問(wèn)過(guò)了。

 (5)繼續(xù)向下查找得到邊(4,6),判斷點(diǎn) 4 和點(diǎn) 6 是否已經(jīng)訪問(wèn)過(guò)了得知點(diǎn) 4 已經(jīng)被訪問(wèn)過(guò)了,點(diǎn) 6 沒(méi)有,因此得到新的集合{2,、3、4、5、6、7}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)著兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記則知均不需要。

。6)繼續(xù)向下查找得到邊(5,6),判斷點(diǎn) 5 和點(diǎn) 6 是否已經(jīng)訪問(wèn)過(guò)了得知已經(jīng)被訪問(wèn)過(guò)了,因此得到不進(jìn)行集合的合并,繼續(xù)向下查找相應(yīng)的邊。

。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)有,因此得到新的集合{1、2,、3、4、5、6、7}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)著兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記,可知點(diǎn) 1 此時(shí)被標(biāo)記訪問(wèn)過(guò)了。

 至此通過(guò)利用深度優(yōu)先搜索進(jìn)行邊通分量查詢的 kruskal 算法運(yùn)行完畢,通過(guò)對(duì)比可知和使用普通的查找算法得到的運(yùn)行結(jié)果是一致的。

 2.4.2 設(shè)計(jì)與實(shí)現(xiàn) 在這里采用 Kruskal 算法得到最小生成樹(shù)的過(guò)程中,在對(duì)邊連通分量的查詢時(shí)使用了深度優(yōu)先搜索的方法來(lái)查詢當(dāng)前得到的具有最下權(quán)值的邊的兩個(gè)頂點(diǎn)是不是已經(jīng)存在于被訪問(wèn)過(guò)的結(jié)點(diǎn)的集合中,如果是的則進(jìn)行下一次查詢,否則的話則將沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)加入已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)的集合中。

 深度優(yōu)先搜索的實(shí)現(xiàn)主要利用棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。因此主要包含兩個(gè)方面,即棧這一數(shù)據(jù)結(jié)構(gòu)中相關(guān)函數(shù)的設(shè)計(jì)與實(shí)現(xiàn),以及如何實(shí)現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設(shè)計(jì)與實(shí)現(xiàn)。由于對(duì)棧已經(jīng)比較熟悉,在這里僅作簡(jiǎn)要的說(shuō)明。

。1)棧:

 這里使用到的與棧相關(guān)的操作主要有棧中數(shù)據(jù)的初始化 StackInitiate、將數(shù)據(jù)壓入棧的操作 StackPush、將數(shù)據(jù)彈出棧的操作 StackPop、判斷棧是否為空的操作StackNotEmpty 和得到棧頂元素的操作 StackTop。

。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ù)的一邊。

 下面給出 kruakal 算法利用深度優(yōu)先搜索進(jìn)行邊連通分量查詢和合并從而得到最小生成樹(shù)的的設(shè)計(jì)與實(shí)現(xiàn)步驟:

 (1)對(duì)所畫(huà)區(qū)域進(jìn)行刷新。

 (2)對(duì)已經(jīng)排好序的邊進(jìn)行選擇,對(duì)沒(méi)有訪問(wèn)過(guò)的最小權(quán)值的邊的兩個(gè)結(jié)點(diǎn)進(jìn)行判斷,檢查是否已經(jīng)被訪問(wèn)過(guò)了,如果有一個(gè)沒(méi)有被訪問(wèn)過(guò),則將和此邊相應(yīng)的頂點(diǎn)進(jìn)行深度優(yōu)先搜索的判斷之后進(jìn)行標(biāo)記,同時(shí)存儲(chǔ)所選擇的這個(gè)邊和相應(yīng)的頂點(diǎn)。

。3)如果都已經(jīng)被訪問(wèn)過(guò)了,則利用深度優(yōu)先搜索判斷這兩個(gè)節(jié)點(diǎn)是否屬于同一個(gè)集合,如果是的話則拋棄此邊,如果不是的話則對(duì)其進(jìn)行標(biāo)記,并畫(huà)出此邊和相對(duì)應(yīng)的點(diǎn)。

。4)選擇下一條沒(méi)有被訪問(wèn)過(guò)的邊重新進(jìn)行(1)、(2)的判斷,直到所有的頂點(diǎn)均已被訪問(wèn)過(guò)且在同一個(gè)集合中,即已經(jīng)添加到了最小生成樹(shù)中則最小生成樹(shù)生成完畢。

。5)當(dāng)最小生成樹(shù)生成完畢時(shí),則調(diào)用 Draw(E)函數(shù)畫(huà)出生成的過(guò)程。

 2.5 廣度優(yōu)先搜索實(shí)現(xiàn) l Kruskal 算法動(dòng)態(tài)演示模塊

 2.5.1 基本思想 廣度優(yōu)先搜索主要是在圖的遍歷中使用此方法對(duì)整個(gè)圖進(jìn)行遍歷來(lái)訪問(wèn)整個(gè)圖中所有節(jié)點(diǎn)的一種遍歷方法。通常是利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)圖中結(jié)點(diǎn)的遍歷。其基本思想是:對(duì)于一個(gè)無(wú)向連通圖,從某一個(gè)起始結(jié)點(diǎn) vi 出發(fā),依次訪問(wèn)與它相連的所有未訪問(wèn)過(guò)的結(jié)點(diǎn) vj1、vj2……vjn,然后在順序訪問(wèn) vj1、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ò)為止。

 kruskal 算法利用廣度優(yōu)先搜索進(jìn)行邊通分量的查詢和合并的的實(shí)現(xiàn)過(guò)程中,邊通分量的查找和合并雖然是廣度優(yōu)先搜索為主,但是總體是以最小生成樹(shù)的的生成過(guò)程為主,因此

 這里所采用的畫(huà)圖操做運(yùn)行的情況和使用一般的方法實(shí)現(xiàn) kruskal 算法的運(yùn)行過(guò)程是一樣的,在這里不再給予詳細(xì)的說(shuō)明,如有必要?jiǎng)t可以參照 kruskal 的生成最小生成樹(shù)的過(guò)程。對(duì)于廣度優(yōu)先搜索方法的實(shí)現(xiàn)這里使用的方法是通過(guò)利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。

 這里采用的廣度優(yōu)先搜索主要是用來(lái)檢索邊的鄰接頂點(diǎn)是不是在同一個(gè)集合中,由于使用 kruskal 算法時(shí)最初已經(jīng)對(duì)邊進(jìn)行了一個(gè)排序,所以每一次所選用的邊和通過(guò)廣度優(yōu)先搜索對(duì)鄰接頂點(diǎn)進(jìn)行判斷的結(jié)果是一樣的,在這里不再給予詳細(xì)的說(shuō)明,kruskal 算法結(jié)合廣度優(yōu)先搜索具體的運(yùn)算過(guò)程和 kruskal 算法結(jié)合深度優(yōu)先搜索的運(yùn)算過(guò)程是一樣的,在這里不再列出。由于本題的重點(diǎn)是最小生成樹(shù)的生成,在這里不再給出廣度優(yōu)先搜索具體的搜索過(guò)程。

 2.5.2 設(shè)計(jì)與實(shí)現(xiàn) 在這里采用 Kruskal 算法得到最小生成樹(shù)的過(guò)程中,在對(duì)邊連通分量的查詢時(shí)使用了廣度優(yōu)先搜索的方法來(lái)查詢當(dāng)前得到的具有最下權(quán)值的邊的兩個(gè)頂點(diǎn)是不是已經(jīng)存在于被訪問(wèn)過(guò)的結(jié)點(diǎn)的集合中,如果是的則進(jìn)行下一次查詢,否則的話則將沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)加入已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)的集合中。

 廣度優(yōu)先搜索的實(shí)現(xiàn)主要利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。因此主要包含兩個(gè)方面,即隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)中相關(guān)函數(shù)的設(shè)計(jì)與實(shí)現(xiàn),以及如何實(shí)現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設(shè)計(jì)與實(shí)現(xiàn)。由于對(duì)隊(duì)列已經(jīng)比較熟悉,在這里僅作簡(jiǎn)要的說(shuō)明。

。1)隊(duì)列:

 這里使用到的與隊(duì)列相關(guān)的操作主要有棧中數(shù)據(jù)的初始化 QueueInitiate、將數(shù)據(jù)存入隊(duì)列的操作 QueueAppend、將數(shù)據(jù)從隊(duì)列中刪除的操作 QueueDelete、判斷隊(duì)列是否為空的操作 QueueNotEmpty。

 (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)的集合中;如果是要進(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ù)的一邊。

 下面給出 kruakal 算法利用廣度優(yōu)先搜索進(jìn)行邊連通分量查詢和合并從而得到最小生成樹(shù)的的設(shè)計(jì)與實(shí)現(xiàn)步驟:

。1)對(duì)所畫(huà)區(qū)域進(jìn)行刷新。

。2)對(duì)已經(jīng)排好序的邊進(jìn)行選擇,對(duì)沒(méi)有訪問(wèn)過(guò)的最小權(quán)值的邊的兩個(gè)結(jié)點(diǎn)進(jìn)行判斷,檢查是否已經(jīng)被訪問(wèn)過(guò)了,如果有一個(gè)沒(méi)有被訪問(wèn)過(guò),則將和此邊相應(yīng)的頂點(diǎn)進(jìn)行廣度優(yōu)先搜索的判斷之后進(jìn)行標(biāo)記,同時(shí)畫(huà)出所選擇的這個(gè)邊和相應(yīng)的頂點(diǎn)。

。3)如果都已經(jīng)被訪問(wèn)過(guò)了,則利用廣度優(yōu)先搜索判斷這兩個(gè)節(jié)點(diǎn)是否屬于同一個(gè)集合,如果是的話則拋棄此邊,如果不是的話則對(duì)其進(jìn)行標(biāo)記,并畫(huà)出此邊和相對(duì)應(yīng)的點(diǎn)。

。4)選擇下一條沒(méi)有被訪問(wèn)過(guò)的邊重新進(jìn)行(1)、(2)的判斷,直到所有的頂點(diǎn)均已被訪問(wèn)過(guò)且在同一個(gè)集合中,即已經(jīng)添加到了最小生成樹(shù)中則最小生成樹(shù)生成完畢。

 (5)當(dāng)最小生成樹(shù)生成完畢時(shí),則調(diào)用 Draw(E)函數(shù)畫(huà)出生成的過(guò)程。

 2.6 畫(huà)圖模塊

 這一模塊主要是實(shí)現(xiàn)如何動(dòng)態(tài)的演示程序運(yùn)行的效果,主要涉及的有三個(gè)方面,第一個(gè)方面是使用不同的算法實(shí)現(xiàn)最小生成樹(shù)的繪制過(guò)程,第二個(gè)方面是畫(huà)圖區(qū)域的刷新,第三個(gè)方面是并查集的繪制過(guò)程。

 對(duì)于最小生成樹(shù)的繪制過(guò)程有一個(gè)函數(shù)承擔(dān),主要是實(shí)現(xiàn)程序在調(diào)用 prime 算法、kruskal 算法、深度優(yōu)先搜索實(shí)現(xiàn)的 kruskal 算法和廣度優(yōu)先搜索實(shí)現(xiàn)的 kruskal 算法的過(guò)程中

 相關(guān)運(yùn)行過(guò)程的繪制,此處主要通過(guò)判斷最小生成樹(shù)中所存儲(chǔ)的邊來(lái)進(jìn)行繪制。

 畫(huà)圖區(qū)域的刷新主要是為了實(shí)現(xiàn)同一塊區(qū)域可以畫(huà)多次不同的運(yùn)行過(guò)程,有兩個(gè)函數(shù)承擔(dān)。由于并查集的繪制和最小生成樹(shù)的繪制沒(méi)有太大的關(guān)聯(lián),因此在這里采用了單獨(dú)繪制并查集實(shí)現(xiàn) kruskal 算法中并查集的合并過(guò)程。

 三. 系統(tǒng)測(cè)試 3.1 測(cè)試數(shù)據(jù)

  圖(2)

 上圖是利用程序直接得到的原圖形,此測(cè)試數(shù)據(jù)中有七個(gè)頂點(diǎn),有十條邊。通過(guò)這些可知其生成的最小生成樹(shù)只能有七個(gè)頂點(diǎn)、六條邊。通過(guò)觀察可知這六條邊應(yīng)為(2,3)、(6,7)、(2,4)、(4,5)、(4,6)、(1,2)。

 3.2Primme 的測(cè)試結(jié)果

  圖(3)

 通過(guò)上面 prime 算法的解析結(jié)果和運(yùn)行結(jié)果發(fā)現(xiàn)其運(yùn)行結(jié)果與分析中應(yīng)該得到的結(jié)果是一致的,由于畫(huà)圖和判斷中采用的有延長(zhǎng)運(yùn)行時(shí)間的函數(shù),因此這里只通過(guò)理論分析得出prime 算法的運(yùn)行效率。

  3.2Kruskal 算法的測(cè)試結(jié)果

  圖(4)

  通過(guò)上面 kruskal 算法的解析結(jié)果和運(yùn)行結(jié)果發(fā)現(xiàn)其運(yùn)行結(jié)果與分析中應(yīng)該得到的結(jié)果是一致的,由于畫(huà)圖和判斷中采用的有延長(zhǎng)運(yùn)行時(shí)間的函數(shù),因此這里只通過(guò)理論分析得出kruskal 算法的運(yùn)行效率。

 3.3 并查集實(shí)現(xiàn) Kruskal 算法的測(cè)試結(jié)果

 圖(5)

  此圖中首先給出了最初集合的狀況,緊接著給出了每一次進(jìn)行邊通分量查找合并過(guò)程中發(fā)生變化的集合的狀況。通過(guò)此圖并結(jié)合上面對(duì)并查集的分析可知與其運(yùn)行一致。

 3.4 深度優(yōu)先搜索實(shí)現(xiàn) Kruskal 算法的測(cè)試結(jié)果

 圖(6)

 在這里沒(méi)有對(duì)深度優(yōu)先搜索的過(guò)程給予動(dòng)態(tài)顯示,主要是模擬了深度優(yōu)先搜索實(shí)現(xiàn)kruskal 算法的過(guò)程,也即最小生成樹(shù)的生成過(guò)程。通過(guò)對(duì)比前兩種 kruskal 算法的實(shí)現(xiàn)過(guò)程可知其運(yùn)行是一致的。

 3.5 廣度優(yōu)先搜索實(shí)現(xiàn) Kruskal 算法的測(cè)試結(jié)果

 圖(7)

  通過(guò)與其他方法實(shí)現(xiàn) kruska 算法進(jìn)行對(duì)比,可知結(jié)果是一致的。由此也說(shuō)明一個(gè)問(wèn)題,即對(duì)于使用不同的方法來(lái)實(shí)現(xiàn)這一算法,改變的只是其效率,但是整體的運(yùn)行情況是不會(huì)發(fā)生改變的。因此在實(shí)現(xiàn)的過(guò)程中應(yīng)該盡量選擇效率比較高的方法來(lái)實(shí)現(xiàn)算法。

 對(duì)于廣度優(yōu)先搜索每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧找鄰接 點(diǎn)的過(guò)程。因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同,兩者不同之處僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。對(duì)于使用 kruskal 算法和深度優(yōu)先搜索結(jié)合的算法,對(duì)邊的遍歷至多是 e 次,故其總代價(jià)為 O(n^2*e)。

 3.6 效率分析 Prime 算法實(shí)現(xiàn)的函數(shù)主要是一個(gè)兩重循環(huán),其中每一重循環(huán)的次數(shù)均為頂點(diǎn)個(gè)數(shù) n,所以該算法的時(shí)間復(fù)雜度為 O(n^2)。

 Kruskal 算法的時(shí)間復(fù)雜度與選取的排序函數(shù)有關(guān),這里采用的是不是對(duì)其進(jìn)行排序 而是在每一次循環(huán)中找余下的邊中權(quán)值最小的邊,找到最小的邊之后將對(duì)其相應(yīng)的點(diǎn)進(jìn)行標(biāo)記,已知點(diǎn)的個(gè)數(shù)為 n 邊的個(gè)數(shù)為 e,所以它的時(shí)間復(fù)雜度為最壞的情況下為 O(e^2),如果邊已經(jīng)很有序的話,也就是最好的情況下的時(shí)間復(fù)雜度為 O(n^2)。

 Kruskal 運(yùn)用并查集實(shí)現(xiàn)中使用了路徑壓縮,F(xiàn)ind 和 UNION 函數(shù)幾乎是常數(shù)假設(shè)可能對(duì)幾乎所有邊都判斷過(guò)了,則最壞情況下算法時(shí)間代價(jià)為 O(eloge),即堆排序的時(shí)間通常情況下只找了接近頂點(diǎn)數(shù)目那么多邊的情況下,MST 就已經(jīng)生成,時(shí)間代價(jià)接近于 O(nloge)

  深度優(yōu)先搜索對(duì)每一條邊處理一次,每個(gè)頂點(diǎn)訪問(wèn)一次以鄰接矩陣作存儲(chǔ)結(jié)構(gòu):處理所 有的邊需 O(n n^2)的時(shí)間 ,故總代價(jià)為 O(n^2)。對(duì)于使用 kruskal 算法和深度優(yōu)先搜索結(jié)合的算法,對(duì)邊的遍歷至多是 e 此故其總代價(jià)為 O(n^2*e)。

 四. 總結(jié) 這個(gè)題目的主要要求是通過(guò)使用不同的算法求出圖的最小生成樹(shù),并且通過(guò)畫(huà)圖動(dòng)態(tài)的顯示出來(lái)其不同的算法在求解最小生成樹(shù)時(shí)的運(yùn)行步驟。在我的程序中已經(jīng)實(shí)現(xiàn)了對(duì)給出的這一例子使用 Prime 算法、Kruskal 算法求解最小生成樹(shù)的運(yùn)算過(guò)程的動(dòng)態(tài)顯示,除此之外,對(duì)于還實(shí)現(xiàn)了在邊通分量的查詢與合并的過(guò)程中,采用廣度優(yōu)先搜索算法(Breadth First Search)、深度優(yōu)先搜索算法(Depth First Search)和并查集(Union-Find Set)三種方法來(lái)實(shí)現(xiàn)對(duì)此例中圖的最小生成樹(shù)的求解,主要是將這三種搜索方法與 Kruakal 結(jié)合來(lái)實(shí)現(xiàn)對(duì)最小生成樹(shù)的求解。

  雖然通過(guò)例子實(shí)現(xiàn)了使用題目中要求的算法來(lái)求解最小生成樹(shù),但是沒(méi)能實(shí)現(xiàn)給用戶一個(gè)友好的界面來(lái)方便求解各種不同的圖的最小生成樹(shù),只能通過(guò)改變程序里面相關(guān)的存儲(chǔ)變量來(lái)實(shí)現(xiàn)對(duì)不同圖的最小生成樹(shù)的求解。同時(shí)由于對(duì)于作圖這方面不是很熟練,沒(méi)能實(shí)現(xiàn)對(duì)圖的動(dòng)態(tài)擴(kuò)充,所以只能是實(shí)現(xiàn)對(duì)一定數(shù)目,一定邊數(shù)的圖的求解。為了我的程序更加完美我會(huì)繼續(xù)努力,從而實(shí)現(xiàn)圖的動(dòng)態(tài)擴(kuò)充,同時(shí)讓程序更為簡(jiǎn)練。

  在最初選擇題目的時(shí)候,總是覺(jué)得自己對(duì)使用 MFC 來(lái)畫(huà)圖這一方面不是很熟悉,擔(dān)心自己做不出來(lái)。在實(shí)現(xiàn)在邊通分量的查詢與合并的過(guò)程中,采用廣度優(yōu)先搜索算法(Breadth

 First Search)、深度優(yōu)先搜索算法(Depth First Search)和并查集(Union-Find Set)三種方法來(lái)實(shí)現(xiàn)對(duì)此例中圖的最小生成樹(shù)的求解,這一方面最初也是相當(dāng)?shù)募m結(jié),不知道該從什么方面下手。因?yàn)樵趯W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)只知道廣度優(yōu)先搜索算法(Breadth First Search)、深度優(yōu)先搜索算法(Depth First Search)是用來(lái)遍歷圖的,平時(shí)沒(méi)有在搜索的過(guò)程中使用此種算法,不知道該從何下手,通過(guò)老師的講解多多少少悟出了點(diǎn),之后反復(fù)的思考最終通過(guò)使用隊(duì)列實(shí)現(xiàn)了在邊通分量的查詢與合并的過(guò)程中,采用廣度優(yōu)先搜索算法(Breadth First Search),通過(guò)使用棧實(shí)現(xiàn)了在邊通分量的查詢與合并的過(guò)程中,深度優(yōu)先搜索算法(Depth First Search)。

 這讓我意識(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è)出版社 2010 年 11 月 [2]王桂平、王衍、任嘉辰,圖論算法理論、實(shí)現(xiàn)及應(yīng)用,北京大學(xué)出版社,2011 年 1 月 [3]孫鑫、余安萍,VC++深入詳解,電子工業(yè)出版社 2011 年 5 月

相關(guān)熱詞搜索:實(shí)習(xí)報(bào)告 綜合 軟件

版權(quán)所有 蒲公英文摘 www.huhawan.com