【正文】 。 （ 3）集合 V(MST)此時(shí)已經(jīng)有三個(gè)頂點(diǎn)了，即 3，找到與之相連的符合條件的邊 (v2,v4)將權(quán)值為 2 的邊添加到 E(MST)中，并將頂點(diǎn) 4 添加到 V(MST)中并畫(huà)出此邊。 （ 4）集合 V(MST)此時(shí)已經(jīng)有四個(gè)頂點(diǎn)了，即 4，找到與之相連的符合條件的邊 (v4,v5)將權(quán)值為 3的邊添加到 E(MST)中 ，并將頂點(diǎn) 5 添加到 V(MST)中并畫(huà)出此邊。 （ 5）集合 V(MST)此時(shí)已經(jīng)有五個(gè)頂點(diǎn)了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權(quán)值為 4 的邊添加到 E(MST)中，并將頂點(diǎn) 6 添加到 V(MST)中并畫(huà)出此邊。 （ 6）集合 V(MST)此時(shí)已經(jīng)有六個(gè)頂點(diǎn)了，即 6，找到與之相連的符合條件的邊 (v6,v7)將權(quán)值為 1 的邊添加到 E(MST)中，并將頂點(diǎn) 7 添加到 V(MST)中并畫(huà)出此邊。 至此圖 G中所有的點(diǎn)均已添加到了 V(MST)，最小生成樹(shù)生成完畢，其 權(quán)值為 16。 設(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[n1]的值也為空。 lowCost 的初始值為鄰接矩陣中第 0 行的值，這樣初始時(shí)lowCost 中就存放了從集合 V(MST)中頂點(diǎn) 0 到集合 V(G)－ V(MST)中各個(gè)頂點(diǎn)的權(quán)值。 （ 3）循環(huán) n1次 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[n1]中。 存 第 k 個(gè)頂點(diǎn)的數(shù)據(jù)和相應(yīng)邊的權(quán)值到 MST 中，并將lowCost[k]置為 1，表示第 k 個(gè)頂點(diǎn)從集合 V(G)－ V(MST)加入了集合V(MST)中 當(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)值。 當(dāng)最小生成樹(shù)生成完畢時(shí)，則調(diào)用 Draw（ E）函數(shù)畫(huà)出生成的過(guò)程。 動(dòng)態(tài)演示模塊 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)的圖中，選夠 n1條邊即可。具體如下： （ 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。 模塊設(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[n1]為空集。 （ 3）判斷找到的邊的數(shù)目是否小于頂點(diǎn)的數(shù)目減一，即 n1，如果是則從沒(méi)有被選中的邊中選取權(quán)值最小的邊，如果放入存儲(chǔ)邊的集合中不構(gòu)成回路則添加進(jìn)去，否則舍去此邊。 （ 4）如果不符合（ 2）中的判斷則不斷的重復(fù)直到選取的邊等于n1。 （ 5）當(dāng)最小生成樹(shù)生成完畢時(shí)，則調(diào)用 Draw（ E）函數(shù)畫(huà)出生成的過(guò)程。 lkruskal算法動(dòng)態(tài)演示模塊 基本思想并查集處理問(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}、 { 3}、 {4}、 {5}、 {6}、 {7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 3}。 （ 3）在圖 G的邊的集合 E中按存儲(chǔ)次序選擇權(quán)值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲(chǔ)，所以后選擇 邊（ 6,7），其權(quán)重為 1。此時(shí)集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 { 7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 7}。 （ 4）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 2,4）并畫(huà)出此邊，其權(quán)重為 2。此時(shí)集合變?yōu)?{1}、 { 4}、 {5}、 { 7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 4}。 （ 5）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,5）并畫(huà)出此邊，其權(quán)重為 3。此時(shí)集合變?yōu)?{1}、 { 5}、 { 7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 5}。 （ 6）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,6）并畫(huà)出此邊，其權(quán)重為 4。此時(shí)集合變?yōu)?{1}、 { 7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 7}。 （ 7）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 1,2）并畫(huà)出此邊，其權(quán)重為 5。此時(shí)集合變?yōu)?{ 7}。通過(guò)判斷畫(huà)出發(fā)生改變的集合 { 7}。 至此 kruskal 算法利用并查集查找、合并的過(guò)程結(jié)束，通過(guò)kruskal算法得到最小生成樹(shù)及生成過(guò)程，其最小生成樹(shù)的權(quán)值為 16。 設(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à)出合并之后的集合。 深度優(yōu)先搜索實(shí)現(xiàn) lKruskal算法動(dòng)態(tài)演示模塊 基本思想深度優(yōu)先搜索主要是在圖的遍歷中使用此方法對(duì)整個(gè)圖進(jìn)行遍歷來(lái)訪(fǎng)問(wèn)整個(gè)圖中所有節(jié)點(diǎn)的一種遍歷方法。通常是利用遞歸來(lái)實(shí)現(xiàn)圖中結(jié)點(diǎn)的遍歷。其基本思想是：對(duì)于一個(gè)無(wú)向連通圖，從某一個(gè)起始結(jié)點(diǎn) vi 出發(fā)，訪(fǎng)問(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ù)直到找到訪(fǎng)問(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)椋?2,3）排在（ 6,7）的前面，所以先判斷它的兩個(gè)結(jié)點(diǎn)，判斷點(diǎn) 2 和點(diǎn) 3 是否已經(jīng)訪(fǎng)問(wèn)過(guò)了，由于數(shù)組 check 中相應(yīng)的值為 0，說(shuō)明沒(méi)有被訪(fǎng)問(wèn)過(guò)，因此合并這兩個(gè)結(jié)點(diǎn)為一個(gè)集合 { 3}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)這兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷及標(biāo)記已經(jīng)訪(fǎng)問(wèn)過(guò)了。 （ 2）繼續(xù)向下查找得到邊（ 6,7），判斷點(diǎn) 6 和點(diǎn) 7 是否已經(jīng)訪(fǎng)問(wèn)過(guò)了，由于數(shù)組 check 中相應(yīng)的值為 0，因此合并這兩個(gè)結(jié)點(diǎn)，得到新的集合 { 7}。同時(shí)通過(guò)深度優(yōu)先搜索對(duì)這兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷及標(biāo)記已經(jīng)訪(fǎng)問(wèn)過(guò)了。 （ 3）繼續(xù)向下查找得到邊（ 2,4），判斷點(diǎn) 2 和點(diǎn) 4 是否已經(jīng)訪(fǎng)問(wèn)過(guò)了得知點(diǎn) 2 已經(jīng)被訪(fǎng)問(wèn)過(guò)了，點(diǎn) 4沒(méi)有，因此得到新的集合 {2,、 4}。同時(shí)通