【正文】 中相關變量和數(shù)據(jù)的存儲也主要通過數(shù)組、結構體來實現(xiàn)了。 這里主要分為六個模塊，即 prime 算法模塊、 kruskal 算法模塊、用并查集實現(xiàn) kruskal算法的模塊、 kruskal算法和深度優(yōu)先搜索算法結合的模塊、 kruskal 算法和廣度優(yōu)先搜索算法結合的模塊以及畫圖操作的相關模塊。 對于最小生成樹生成過程中邊相關變量的存儲均是通過定義一個邊（ edge）的結構體變量進行存儲的，而關于點的存儲則是通過定義數(shù)組進行相應的存儲，由于不同的實現(xiàn)方法采用的初始值不一樣，因此使用的數(shù)組會有所不同。在這些算法運行過程中實現(xiàn)的畫圖操作主要通過調用一個公用的函數(shù)進行畫圖的相關操作。通過這樣的一個遍歷過程與畫圖的相 關操作結合來實現(xiàn)最小生成樹生成過程的動態(tài)演示。對于已經(jīng)選擇的頂點之間的邊存儲在最小生成樹的邊的集合中 E(MST)。首先從圖 G 的頂點集 V(G)中任選一個頂點，把它加到最小生成樹MST 的頂點集 V(MST)中。 （ 1） (vi,vj) E(G)， v是 V(MST)的頂點，而 vj是還未加入 V(MST)的頂點。通過判斷先找出所有這樣的邊。選出滿足該條件的邊，將 vj 加入 V(MST)， (vi,vj)加入 E(MST)，之后畫出相應的邊和新添加進去的頂點。 （ 2）集合 V(MST)此時已經(jīng)有兩個頂點了，即 2，找到與之相連的符合條件的邊 (v2,v3)將權值為 1的邊添加到 E(MST)中，并將頂點3 添加到 V(MST)中并畫出此邊。 （ 4）集合 V(MST)此時已經(jīng)有四個頂點了，即 4，找到與之相連的符合條件的邊 (v4,v5)將權值為 3的邊添加到 E(MST)中，并將頂點 5 添加到 V(MST)中并畫出此邊。 （ 6）集合 V(MST)此時已經(jīng)有六個頂點了，即 6，找到與之相連的符合條件的邊 (v6,v7)將權值為 1 的邊添加到 E(MST)中，并將頂點 7 添加到 V(MST)中并畫出此邊。 設計與實現(xiàn)對于 prime 算法的動態(tài)演示，主要是關乎兩個函數(shù)的實現(xiàn)一個是畫圖函數(shù)的實現(xiàn)，另外一個就是如何判斷何時進行畫圖操作并進行 相關操作的畫圖函數(shù)，在這里主要通過兩個函數(shù)實現(xiàn)一個是與 Kruskal 算法動態(tài)實現(xiàn)的公用的畫圖操作函數(shù)，另外一個就是 prime 算法尋找最小生成樹的實現(xiàn)。 Prime算法的設計與實現(xiàn)如下所述： （ 1）對所畫區(qū)域刷新。 lowCost 的初始值為鄰接矩陣中第 0 行的值，這樣初始時lowCost 中就存放了從集合 V(MST)中頂點 0 到集 合 V(G)－ V(MST)中各個頂點的權值。根據(jù)lowCost 的定義，這樣的邊其一個頂點必然為集合 V(MST)中的頂點，其另一個頂點（設第 k 個頂點）必然為集合 V(G)－ V(MST)中的頂點，將相應的邊添加到 E[n1]中。 當最小生成樹生成完畢時，則調用 Draw（ E）函數(shù)畫出生成的過程。首先將圖中所有邊按權值遞增順序排列，依次選定取 權值較小的邊，但要求后面選取的邊不能與前面選取的邊構成回路，若構成回路，則放棄該條邊，再去選后面權值較大的邊。在 n 個頂點的圖中，選夠 n1條邊即可。 （ 2） 在原圖 G 中的邊中選擇具有最小權值的邊，若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到 T 中；否則，則將此邊舍去（此后永不選入此邊），重新選擇一條權值最小的邊并進行畫圖的操作處理。 下面主要通過題目中給出的例子（如圖 1）對 kruskal 算法進行詳細的解析： （ 1）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）并畫出此邊，其權重為 1。 （ 3）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 2,4）并畫出此邊，其權重為 2。 （ 5）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,6）并畫出此邊，其權重為 4。 至此通過 kruskal 算法得到最小生成樹及生成過程，其最小生成樹的權值為 16。因此首先將圖 G 的頂點集合 V 分為 n 個等價類，每個等價類包括一個頂點；然后以權值的大小為順序處理各條邊，如果某條邊連接兩個不同等價類的頂點，則這條邊被添加到 MST（選取的邊不與前面選取的邊構成回路），兩個等價類被合并為一個；反復執(zhí)行此過程，直到只剩下一個等價類。 （ 2）設置查找到的頂點集合 find[n]所有的值為 1，存儲邊的集合 E[n1]為空集。 （ 4）如果不符合（ 2）中的判斷則不斷的重復直到選取的邊等于n1。 lkruskal算法動態(tài)演示模塊 基本思想并查集處理問題的主要思想是在處理時使用搜索與合并運算對相關集合進行處理。在此過程中不斷的重復使用一個搜索運算，從而確定此元素在哪一個集合中，當讀入一個等價對 A≡ B 時，首先檢測 A 和 B是不是屬于同一個集合，如果是，則不用合并；如果不是，則使用一個合并運算把 A 和 B 合并到同一個集合中，使得這兩個集合中的任意兩個元素都是等價的（依據(jù)等價的傳遞性）。在程序中也實現(xiàn)了并查集的動態(tài)演示，通過 Kruskal 算法調用并查集的函數(shù)，在函數(shù)中對相關的頂點信息進行判斷從而實施相應的畫圖操作。畫出初始狀態(tài)。此時集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 {6}、 {7}。 （ 3）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7），其權重為 1。通過判斷畫出發(fā)生改變的集合 { 7}。此時集合變?yōu)?{1}、 { 4}、 {5}、 { 7}。 （ 5）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,5）并畫出此邊，其權重為 3。通過判斷畫出發(fā)生改變的集合 { 5}。此時集合變?yōu)?{1}、 { 7}。 （ 7）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 1,2）并畫出此邊，其權重為 5。通過判斷畫出發(fā)生改變的集合 { 7}。 設計與實現(xiàn) Kruskal 算法利用并查集實現(xiàn)查找、合并的設計與實現(xiàn)也是首先選擇權值最小的邊，其次是利用并查集來對所要選擇的那些頂點進行查找、合并。 并查集的實現(xiàn)主要包含三個方面，即并查集的初始化、查找和集合的合并，下面主要介紹并查集這三個過程的設計與實現(xiàn)。 （ 2）初始化過程：為了方便并查集的描述與實現(xiàn)，通常把先后加入到一個集合中的元素表示成一個樹形結構，并用根節(jié)點來代表這個集合。 （ 3）查找：主要是查找并返回結點 i 所屬集合的根節(jié)點。這里通過壓縮路 徑的方法來加快后續(xù)的查找速度，主要是通過增加一個 while 循環(huán)，每次都把從結點 i 到集合根節(jié)點的路徑上經(jīng)過的結點直接設置為根結點的子結點。在這里采用的是加權合并，即把兩個集合中元素個數(shù)少的根結點作為元素個數(shù)多的根節(jié)點的子結點。在每一次的合并過程結束時，將會畫出合并之后的集合。通常是利用遞歸來實現(xiàn)圖中結點的遍歷。 在這個算法的實現(xiàn)過程中，邊通分量的查找雖然是深度優(yōu)先搜索為主，但是是以最小生成樹的的生成過 程為主，因此這里所采用的畫圖操做運行的情況和使用一般的方法實現(xiàn) kruskal 算法的運行過程是一樣的，在這里不再給予詳細的說明，如有必要則可以參照 kruskal的生成最小生成樹的過程。下面僅給出在邊已經(jīng)通過權值大小進行排序之后，邊通分量的查找的過程和查找之后集合的合并情況（ 1）得到圖 G 中最小權值的邊（ 2,3），因為（ 2,3）排在（ 6,7）的前面，所以先判斷它的兩個結點，判斷點 2 和點 3 是否已經(jīng)訪問過了，由于數(shù)組 check 中相應的值為 0，說 明沒有被訪問過，因此合并這兩個結點為一個集合 { 3}。 （ 2）繼續(xù)向下查找得到邊（ 6,7），判斷點 6 和點 7 是否已經(jīng)訪問過了，由于數(shù)組 check 中相應的值為 0，因此合并這兩個結點，得到新的集合 { 7}。 （ 3）繼續(xù)向下查找得到邊（ 2,4），判斷點 2 和點 4 是否已經(jīng)訪問過了得知點 2 已經(jīng)被訪問過了，點 4沒有，因此得到新的集合 {2,、 4}。 （ 4）繼續(xù)向下查找得到邊（ 4,5），判斷點 4 和點 5 是否已經(jīng)訪問過了得知點 4 已經(jīng)被訪問過了，點 5沒有，因此得到新的集合 {2,、 5}。 （ 5）繼續(xù)向下查找得到邊（ 4,6），判斷點 4 和點 6 是否已經(jīng)訪問過了得知點 4 已經(jīng)被訪問過了，點 6沒有，因此得到新的集合 {2,、 7}。 （ 6）繼續(xù)向下查找得到邊（ 5,6），判斷點 5 和點 6 是否已經(jīng)訪問過了得知已經(jīng)被訪問過了，因此得到不進行集合的合并，繼續(xù)向下查找相應的邊。同時通過深度優(yōu)先搜索對著兩個結點分別進行判斷是否需要標記，可知點 1 此時被標記訪問過了。 設計與實現(xiàn)在這里采用 Kruskal 算法得到最小生成樹的過程中，在對邊連通分量的查詢時使用了深度優(yōu)先搜索的方法來查詢當前得到的具有最下權值的邊的兩個頂點是不是已經(jīng)存在于被訪問過的結點的集合中，如果是的則進行下一次查詢，否則的話則將沒有訪問過的結點加入已經(jīng)訪問過的結點的集合中。因此主要包含兩個方面，即棧這一數(shù)據(jù)結構中相關函數(shù)的設計與實現(xiàn)，以及如何實現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設計與實現(xiàn)。 （ 1）棧： 這里使用到的與棧相關的操作主要有棧中數(shù)據(jù)的初始化StackInitiate、將數(shù)據(jù)壓入棧的操作 StackPush、將數(shù)據(jù)彈出棧的操作 StackPop、判斷棧是否為空的操作 StackNotEmpty 和得到棧頂元素的操作 StackTop。 下面給出 kruakal 算法利用深度優(yōu)先搜索進行邊連通分量查詢和合并從而得到最小生成樹的的設計與實現(xiàn)步驟： （ 1）對所畫區(qū)域進行刷新。 （ 3）如果都已經(jīng)被訪問過了，則利用深度優(yōu)先搜索判斷這兩個節(jié)點是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進行標記，并畫出此邊和相對應的點。 （ 5）當最小生成樹生成完畢時，則調用 Draw（ E）函數(shù)畫出生成的過程。通常是利用隊列這一數(shù)據(jù)結構來實現(xiàn)圖中結點的遍歷。 kruskal 算法利用廣度優(yōu)先搜索進行邊通分量的查詢和合并的的實現(xiàn)過程中，邊通分量的查找和合并雖然是廣度優(yōu)先搜索為主，但是總體是以最小生成樹的的生成過程為主，因此 這里所采用的畫圖操做運行的情況和使用一般的方法實現(xiàn)kruskal 算法的運行過程是一樣的，在這里不再給予詳細的說明，如有必要則可以參照 kruskal 的生成最小生成樹的過程。 這里采用的廣度優(yōu)先搜索主要是用來檢索邊的鄰接頂點是不是在同一個集合中，由于使 用 kruskal 算法時最初已經(jīng)對邊進行了一個排序，所以每一次所選用的邊和通過廣度優(yōu)先搜索對鄰接頂點進行判斷的結果是一樣的，在這里不再給予詳細的說明， kruskal 算法結合廣度優(yōu)先搜索具體的運算過程和 kruskal 算法結合深度優(yōu)先搜索的運算過程是一樣的，在這里不再列出。 設計與實現(xiàn)在這里采用 Kruskal 算法得到最小生成樹的過程中，在對邊連通分量的查詢時使用了廣度優(yōu)先搜索的方法來查詢當前得到的具有最下權值的邊的兩個頂 點是不是已經(jīng)存在于被訪問過的結點的集合中，如果是的則進行下一次查詢，否則的話則將沒有訪問過的結點加入已經(jīng)訪問過的結點的集合中。因此主要包含兩個方面，即隊列這一數(shù)據(jù)結構中相關函數(shù)的設計與實現(xiàn)，以及如何實現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設計與實現(xiàn)。 （ 1）隊列： 這里使用到的與隊列相關的操作主要有棧中數(shù)據(jù)的初始化QueueInitiate、將數(shù)據(jù)存入隊列的操作 QueueAppend、將數(shù)據(jù) 從隊列中刪除的操作 QueueDelete、判斷隊列是否為空的操作 QueueNotEmpty。 下面給出 kruakal 算法利用廣度優(yōu)先搜索進行邊連通分量查詢和合并從而得 到最小生成樹的的設計與實現(xiàn)步驟： （ 1）對所畫區(qū)域進行刷新。 （ 3）如果都已經(jīng)被訪問過了，則利用廣度優(yōu)先搜索判斷這兩個節(jié)點是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進行標記，并畫出此邊和相對應的點。 （ 5）當最小生成樹生成完畢時，則調用 Draw（ E）函數(shù)畫出生成的過程。 對于最小生成樹的繪制過程有一個函數(shù)承擔，主要是實現(xiàn)程序在調用 prime 算法、 kruskal 算法、 深度優(yōu)先搜索實現(xiàn)的 kruskal 算法和廣度優(yōu)先搜索實現(xiàn)的 kruskal算法的過程中 相關運行過程的繪制，此處主要通過判斷最小生成樹中所存儲的邊來進行繪制。由于并查集的繪制和最小生成樹的繪制沒有太大的關聯(lián)，因此在這里采用了單獨繪制并查集實現(xiàn) kruskal 算法中并查集的合并過程。通過這些 可知其生成的最小生成樹只能有七個頂點、六條邊。