【正文】 ??????????????????????????????? 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)和一部分邊，且不形成回路，則稱 G為圖 G 的生成樹(shù)，代價(jià)最小生成樹(shù)則稱為最小生成樹(shù)（ MinimalSpanningTree）。雖然最后做的和自己最初設(shè)想的有所差異，但是題目中的要求我都完成了，還是小有成就感的。 這讓我意識(shí)到學(xué)習(xí)到的知識(shí)一定要活用才能創(chuàng)造出更好的方法，只是使用它通常的用途是遠(yuǎn)遠(yuǎn)不夠的。在實(shí)現(xiàn)在邊通分量的查詢與合并的過(guò) 程中，采用廣度優(yōu)先搜索算法（ Breadth FirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）三種方法來(lái)實(shí)現(xiàn)對(duì)此例中圖的最小生成樹(shù)的求解，這一方面最初也是相當(dāng)?shù)募m結(jié)，不知道該從什么方面下手。為了我的程序更加完美我會(huì)繼續(xù)努力，從而實(shí)現(xiàn)圖的動(dòng)態(tài)擴(kuò)充，同時(shí)讓程序更為簡(jiǎn)練。 雖然通過(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ù)的求解。 四．總結(jié)這個(gè)題目的主要要求是通過(guò)使用不同的算法求出圖的最小生成樹(shù)，并且通過(guò)畫(huà)圖動(dòng)態(tài)的顯示出來(lái)其不同的算法在求解最小生成樹(shù)時(shí)的運(yùn)行步驟。 Kruskal 運(yùn)用并查集實(shí)現(xiàn)中使用了路徑壓縮， Find 和 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(nn^2)的時(shí)間，故總代價(jià)為 O(n^2)。 效率分析 Prime 算法實(shí)現(xiàn)的函數(shù)主要是一個(gè)兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點(diǎn)個(gè)數(shù) n，所以該算法的時(shí)間復(fù)雜度為 O(n^2)。因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。 對(duì)于廣度優(yōu)先搜索每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。由此也說(shuō)明一個(gè)問(wèn)題，即對(duì)于使用不同的方法來(lái)實(shí)現(xiàn)這一算法，改變的只是其效率，但是整體的運(yùn)行情況是不會(huì)發(fā)生改變的。通過(guò)對(duì)比前兩種 kruskal算法的實(shí)現(xiàn)過(guò)程可知其運(yùn)行是一致的。通過(guò)此圖并結(jié)合上面對(duì)并查集的分析可知與其運(yùn)行一致。 圖 (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)行效率。通過(guò)觀察可知這六條邊應(yīng)為（ 2,3）、（ 6,7）、（ 2,4）、（ 4,5）、（ 4,6）、（ 1,2）。 三．系統(tǒng)測(cè)試 圖（ 2） 上圖是利用程序直接得到的原圖形，此測(cè)試數(shù)據(jù)中有七個(gè)頂點(diǎn)，有十條邊。 畫(huà)圖區(qū)域的刷新主要是為了實(shí)現(xiàn)同一塊區(qū)域可以畫(huà)多次不同的運(yùn)行過(guò)程，有兩個(gè)函數(shù)承擔(dān)。 畫(huà)圖模塊 這一模塊主要是實(shí)現(xiàn)如何動(dòng)態(tài)的演示程序運(yùn)行的效果，主要涉及的有三個(gè)方面，第一個(gè)方面是使用不同的算法實(shí)現(xiàn)最小生成樹(shù)的繪制過(guò)程，第二個(gè)方面是畫(huà)圖區(qū)域的刷新，第三個(gè)方面是并查集的繪制過(guò)程。 （ 4）選擇下一條沒(méi)有被訪問(wèn)過(guò)的邊重新進(jìn)行（ 1）、（ 2）的判斷，直到所有的頂點(diǎn)均已被訪問(wèn)過(guò)且在同一個(gè)集合中，即已經(jīng)添加到了最小生成樹(shù)中則最小生成樹(shù)生成完畢。 （ 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)。 （ 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ù)的一邊。由于對(duì)隊(duì)列已經(jīng)比較熟悉，在這里僅作簡(jiǎn)要的說(shuō)明。 廣度優(yōu)先搜索的實(shí)現(xiàn)主要利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。由于本題的重點(diǎn)是最小生成樹(shù)的生成，在這里不再給出廣度優(yōu)先搜索具體的搜索過(guò)程。對(duì)于廣度優(yōu)先搜索方法的實(shí)現(xiàn)這里使用的方法是通過(guò)利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。其基本思想是：對(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ò)為止。 廣度優(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）選擇下一條沒(méi)有被訪問(wèn)過(guò)的邊重新進(jìn)行（ 1）、（ 2）的判斷，直到所有的頂點(diǎn)均已被訪問(wèn)過(guò)且在同一個(gè)集合中，即已經(jīng)添加到了最小生成樹(shù)中則最小生成樹(shù)生成完畢。 （ 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)。 （ 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ù)的一邊。由于對(duì)棧已經(jīng) 比較熟悉，在這里僅作簡(jiǎn)要的說(shuō)明。 深度優(yōu)先搜索的實(shí)現(xiàn)主要利用棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。 至此通過(guò)利用深度優(yōu)先搜索進(jìn)行邊通分量查詢的 kruskal 算法運(yùn)行完畢，通過(guò)對(duì)比可知和使用普通的查 找算法得到的運(yùn)行結(jié)果是一致的。 （ 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)記則知均不 需要。同時(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)記，可知點(diǎn) 4 此時(shí)被標(biāo)記訪問(wèn)過(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ì)所畫(huà)區(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ò)判斷畫(huà)出發(fā)生改變的集合 { 7}。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫(huà)出此邊，其權(quán)重為 4。此時(shí)集合變?yōu)?{1}、 { 5}、 { 7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 4}。 （ 4）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 2,4）并 畫(huà)出此邊，其權(quán)重為 2。此時(shí)集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 { 7}。通過(guò)判斷畫(huà)出發(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ù)畫(huà)出生成的過(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ì)所畫(huà)區(qū)域進(jìn)行刷新。 模塊設(shè)計(jì)與實(shí)現(xiàn) Kruskal 算法的實(shí)現(xiàn)主要包含兩個(gè)部分，即帶權(quán) 值的邊的排序和判斷選