【文章內(nèi)容簡介】 查找得到邊（ 1,2），判斷點(diǎn) 1 和點(diǎn) 2 是否已經(jīng)訪問過了得知點(diǎn) 2 已經(jīng)被 訪問過了，點(diǎn) 1 沒有，因此得到新的集合 { 2,、 7}。同時通過深度優(yōu)先搜索對著兩個結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記，可知點(diǎn) 1 此時被標(biāo)記訪問過了。 至此通過利用深度優(yōu)先搜索進(jìn)行邊通分量查詢的 kruskal 算法運(yùn)行完畢，通過對比可知和使用普通的查 找算法得到的運(yùn)行結(jié)果是一致的。 設(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)的集合中。 深度優(yōu)先搜索的實(shí)現(xiàn)主要利用棧這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。因此主要包含兩個方面，即棧這一數(shù)據(jù)結(jié)構(gòu)中相關(guān)函數(shù)的設(shè)計與實(shí)現(xiàn)，以及如何實(shí)現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設(shè)計與實(shí)現(xiàn)。由于對棧已經(jīng) 比較熟悉，在這里僅作簡要的說明。 （ 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)記為以訪問過，并添加到已經(jīng)訪問過的結(jié)點(diǎn)的集合中，并將相應(yīng)的邊存入 E[]中；如果是要進(jìn)行判斷兩個結(jié)點(diǎn)是不是都已經(jīng)訪問 過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結(jié)點(diǎn)所在的集合中是否有另一個結(jié)點(diǎn)，如果存在則舍棄當(dāng)前所選擇的邊，否則選擇此邊為最小生成樹的一邊。 下面給出 kruakal 算法利用深度優(yōu)先搜索進(jìn)行邊連通分量查詢和合并從而得到最小生成樹的的設(shè)計與實(shí)現(xiàn)步驟： （ 1）對所畫區(qū)域進(jìn)行刷新。 （ 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)。 （ 3）如果都已經(jīng)被訪問過了，則利用深度優(yōu)先搜索判斷這兩個節(jié)點(diǎn)是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進(jìn)行標(biāo)記，并畫出此邊和相對應(yīng)的點(diǎn)。 （ 4）選擇下一條沒有被訪問過的邊重新進(jìn)行（ 1）、（ 2）的判斷，直到所有的頂點(diǎn)均已被訪問過且在同一個集合中，即已經(jīng)添加到了最小生成樹中則最小生成樹生成完畢。 （ 5）當(dāng)最小生成樹生成完畢時，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 廣度優(yōu)先搜索實(shí)現(xiàn) lKruskal算法動態(tài)演示模塊 基本思 想廣度優(yōu)先搜索主要是在圖的遍歷中使用此方法對整個圖進(jìn)行遍歷來訪問整個圖中所有節(jié)點(diǎn)的一種遍歷方法。通常是利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)圖中結(jié)點(diǎn)的遍歷。其基本思想是：對于一個無向連通圖，從某一個起始結(jié)點(diǎn) vi 出發(fā)，依次訪問與它相連的所有未訪問過的結(jié)點(diǎn) vj vj2?? vjn，然后在順序訪問 vj vj2?? vjn的所有還未訪問過的鄰接頂點(diǎn)；再從這些鄰接頂點(diǎn)出發(fā)，再訪問它們的所有未訪問過的鄰接頂點(diǎn)，??，不斷重復(fù)直到圖 G 中所有的頂點(diǎn)都被訪問過為止。 kruskal 算法利用廣度優(yōu)先搜索進(jìn)行邊通分量的查詢和合并的的實(shí)現(xiàn)過程中，邊通分量的查找和合并雖然是廣度優(yōu)先搜索為主，但是總體是以最小生成樹的的生成過程為主，因此 這里所采用的畫圖操做運(yùn)行的情況和使用一般的方法實(shí)現(xiàn)kruskal 算法的運(yùn)行過程是一樣的，在這里不再給予詳細(xì)的說明，如有必要則可以參照 kruskal 的生成最小生成樹的過程。對于廣度優(yōu)先搜索方法的實(shí)現(xiàn)這里使用的方法是通過利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xià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)算過程是一樣的，在這里不再列出。由于本題的重點(diǎn)是最小生成樹的生成，在這里不再給出廣度優(yōu)先搜索具體的搜索過程。 設(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)的集合中。 廣度優(yōu)先搜索的實(shí)現(xiàn)主要利用隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。因此主要包含兩個方面，即隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)中相關(guān)函數(shù)的設(shè)計與實(shí)現(xiàn)，以及如何實(shí)現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設(shè)計與實(shí)現(xiàn)。由于對隊(duì)列已經(jīng)比較熟悉，在這里僅作簡要的說明。 （ 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)記為以訪問過，并添加到已經(jīng)訪問過的結(jié)點(diǎn)的集合中；如果是要進(jìn)行判斷兩個結(jié)點(diǎn)是不是都已經(jīng)訪問過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結(jié)點(diǎn)所在的集合中是否有另一個結(jié)點(diǎn)，如果存在則舍棄當(dāng)前所選擇的邊，否則選擇此邊為最小生成樹的一邊。 下面給出 kruakal 算法利用廣度優(yōu)先搜索進(jìn)行邊連通分量查詢和合并從而得 到最小生成樹的的設(shè)計與實(shí)現(xiàn)步驟： （ 1）對所畫區(qū)域進(jìn)行刷新。 （ 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)。 （ 3）如果都已經(jīng)被訪問過了，則利用廣度優(yōu)先搜索判斷這兩個節(jié)點(diǎn)是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進(jìn)行標(biāo)記，并畫出此邊和相對應(yīng)的點(diǎn)。 （ 4）選擇下一條沒有被訪問過的邊重新進(jìn)行（ 1）、（ 2）的判斷，直到所有的頂點(diǎn)均已被訪問過且在同一個集合中，即已經(jīng)添加到了最小生成樹中則最小生成樹生成完畢。 （ 5）當(dāng)最小生成樹生成完畢時，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 畫圖模塊 這一模塊主要是實(shí)現(xiàn)如何動態(tài)的演示程序運(yùn)行的效果，主要涉及的有三個方面，第一個方面是使用不同的算法實(shí)現(xiàn)最小生成樹的繪制過程，第二個方面是畫圖區(qū)域的刷新，第三個方面是并查集的繪制過程。 對于最小生成樹的繪制過程有一個函數(shù)承擔(dān)，主要是實(shí)現(xiàn)程序在調(diào)用 prime 算法、 kruskal 算法、 深度優(yōu)先搜索實(shí)現(xiàn)的 kruskal 算法和廣度優(yōu)先搜索實(shí)現(xiàn)的 kruskal算法的過程中 相關(guān)運(yùn)行過程的繪制，此處主要通過判斷最小生成樹中所存儲的邊來進(jìn)行繪制。 畫圖區(qū)域的刷新主要是為了實(shí)現(xiàn)同一塊區(qū)域可以畫多次不同的運(yùn)行過程，有兩個函數(shù)承擔(dān)。由于并查集的繪制和最小生成樹的繪制沒有太大的關(guān)聯(lián)，因此在這里采用了單獨(dú)繪制并查集實(shí)現(xiàn) kruskal 算法中并查集的合并過程。 三．系統(tǒng)測試 圖（ 2） 上圖是利用程序直接得到的原圖形，此測試數(shù)據(jù)中有七個頂點(diǎn)，有十條邊。通過這些 可知其生成的最小生成樹只能有七個頂點(diǎn)、六條邊。通過觀察可知這六條邊應(yīng)為（ 2,3）、（ 6,7）、（ 2,4）、（ 4,5）、（ 4,6）、（ 1,2）。 圖（ 3） 通過上面 prime 算法的解析結(jié)果和運(yùn)行結(jié)果發(fā)現(xiàn)其運(yùn)行結(jié)果與分析中應(yīng)該得到的結(jié)果是一致的，由于畫圖和判斷中采用的有延長運(yùn)行時間的函數(shù)，因此這里只通過理論分析得出 prime算法的運(yùn)行效率。 圖 (4) 通過上面 kruskal 算法的解析結(jié)果和運(yùn)行結(jié)果發(fā) 現(xiàn)其運(yùn)行結(jié)果與分析中應(yīng)該得到的結(jié)果是一致的，由于畫圖和判斷中采用的有延長運(yùn)行時間的函數(shù)，因此這里只通過理論分析得出 kruskal 算法的運(yùn)行效率。 并查集實(shí)現(xiàn) Kruskal算法的測試結(jié)果 圖 (5) 此圖中首先給出了最初集合的狀況，緊接著給出了每一次進(jìn)行邊通分量查找合并過程中發(fā)生變化的集合的狀況。通過此圖并結(jié)合上面對并查集的分析可知與其運(yùn)行一致。 深度優(yōu)先搜索實(shí)現(xiàn) Kruskal算法的測試結(jié)果 圖（ 6） 在這里沒有對深度優(yōu)先搜索的過程給予動態(tài)顯示，主要是模擬了深度優(yōu)先搜索實(shí)現(xiàn) kruskal算法的過程，也即最小生成樹的生成過程。通過對比前兩種 kruskal算法的實(shí)現(xiàn)過程可知其運(yùn)行是一致的。 廣度優(yōu)先搜索實(shí)現(xiàn) Kruskal算法的測試結(jié)果 圖（ 7） 通過與其他方法實(shí)現(xiàn) kruska 算法進(jìn)行對比，可知結(jié)果是一致的。由此也說明一個問題，即對于使用不同的方法來實(shí)現(xiàn)這一算法，改變的只是其效率，但是整體的運(yùn)行情況是不會發(fā)生改變的。因此在實(shí)現(xiàn)的過程中應(yīng)該盡量選擇效率比較高的方法來實(shí)現(xiàn)算法。 對于廣度優(yōu)先搜索每個頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接點(diǎn)的過程。因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅在于對頂點(diǎn)訪問的順序不同。對于使用 kruskal 算法和深度優(yōu)先搜索結(jié)合的算法，對邊的遍歷至多是 e 次，故其總代價為 O(n^2*e)。 效率分析 Prime 算法實(shí)現(xiàn)的函數(shù)主要是一個兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點(diǎn)個數(shù) n，所以該算法的時間復(fù)雜度為 O(n^2)。 Kruskal 算法的時間復(fù)雜度與選取的排序函數(shù)有關(guān)，這里采用的是不是對其進(jìn)行排序而是在每一次循環(huán)中找余下的邊中權(quán)值最小的邊，找到最小的邊之后將對其相應(yīng)的點(diǎn)進(jìn)行標(biāo)記，已知點(diǎn)的個數(shù)為 n 邊的個數(shù)為 e，所以它的時間復(fù)雜度為最壞的情況下為 O(e^2)，如果邊已經(jīng)很有序的話，也就是最好的情況下的時間復(fù)雜度為 O(n^2)。 Kruskal 運(yùn)用并查集實(shí)現(xiàn)中使用了路徑壓縮， Find 和 UNION 函數(shù)幾乎是常數(shù)假設(shè)可能對幾乎所有邊都判斷過了，則最壞情況下算法時間代價為 O(eloge)，即堆排序的時間通常情況下只找了接近頂點(diǎn)數(shù)目那么多邊的情況下， MST就已經(jīng)生成，時間代價接近于 O(nloge) 深度優(yōu)先搜索對每一條邊處理一次，每個頂點(diǎn)訪問一次以鄰接矩陣作存儲結(jié)構(gòu)：處理所有的邊需 O(nn^2)的時間，故總代價為 O(n^2)。對于使用 kruskal 算法和深度優(yōu)先搜索結(jié)合的算法，對邊的遍歷至多是 e 此故其總代價為 O(n^2*e)。 四．總結(jié)這個題目的主要要求是通過使用不同的算法求出圖的最小生成樹，并且通過畫圖動態(tài)的顯示出來其不同的算法在求解最小生成樹時的運(yùn)行步驟。在我的程序中已經(jīng)實(shí)現(xiàn)了對給出的這一例子使用Prime 算法、 Kruskal算法求解最小生成樹的運(yùn)算過程的動態(tài)顯示，除此 之外，對于還實(shí)現(xiàn)了在邊通分量的查詢與合并的過程中，采用廣度優(yōu) 先 搜 索 算 法 （ BreadthFirstSearch ）、 深 度 優(yōu) 先 搜 索 算 法(DepthFirstSearch)和并查集（ UnionFindSet）三種方法來實(shí)現(xiàn)對此例中圖的最小生成樹的求解，主要是將這三種搜索方法與 Kruakal 結(jié)合來實(shí)現(xiàn)對最小生成樹的求解。 雖然通過例子實(shí)現(xiàn)了使用題目中要求的算法來求解最小生成樹，但是沒能實(shí)現(xiàn)給用戶一個友好的界面來方便求解各種不同的圖的最小生成樹，只能通過改變程序里面相關(guān)的存儲變量來實(shí)現(xiàn)對不同圖的最小生成樹的求解。同時由于對于作圖這方面不是很熟練，沒能實(shí)現(xiàn)對圖的動態(tài)擴(kuò)充，所以只能是實(shí)現(xiàn)對一定數(shù)目，一定邊數(shù)的圖的求解。為了我的程序更加完美我會繼續(xù)努力，從而實(shí)現(xiàn)圖的動態(tài)擴(kuò)充，同時讓程序更為簡練。 在最初選擇題目的時候，總是覺得自己對使用 MFC 來畫圖這一方面不是很熟悉，擔(dān)心自己做不出來。在實(shí)現(xiàn)在邊通分量的查詢與合并的過 程中，采用廣度優(yōu)先搜索算法（ Breadth FirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）三種方法來實(shí)現(xiàn)對此例中圖的最小生成樹的求解，這一方面最初也是相當(dāng)?shù)募m結(jié)，不知道該從什么方面下手。因?yàn)樵趯W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時只知道廣度優(yōu)先搜索算法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)是用來遍歷圖的，平時沒有在搜索的過程中使用此種算法，不知道該從何下手，通過老師的講解多多少少悟出了點(diǎn)，之后反復(fù) 的思考最終通過使用隊(duì)列實(shí)現(xiàn)了在邊通分量的 查 詢 與 合 并 的 過 程 中 ， 采 用 廣