最小生成樹(shù)算法分析報(bào)告(編輯修改稿)
2025-08-18 22:19 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 list[i].endv； w:=g[j,s]； If welist[i].weight Then Begin elist[i].weight:=w；elist[i].fromv:=j；End； End； End；④ 輸出；用Kruskal算法求最小生成樹(shù)的思想如下： 設(shè)最小生成樹(shù)為T=（V，TE），設(shè)置邊的集合TE的初始狀態(tài)為空集。將圖G中的邊按權(quán)值從小到大排好序，然后從小的開(kāi)始依次選取，若選取的邊使生成樹(shù)T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹(shù)形成回路，則將其舍棄；如此進(jìn)行下去，直到TE中包含n1條邊為止。最后的T即為最小生成樹(shù)。如何證明呢？下圖是按照Kruskal算法給出了例題中圖（A）最小生成樹(shù)的生成過(guò)程：Kruskal算法在實(shí)現(xiàn)過(guò)程中的關(guān)鍵和難點(diǎn)在于：如何判斷欲加入的一條邊是否與生成樹(shù)中已保留的邊形成回路？我們可以將頂點(diǎn)劃分到不同的集合中，每個(gè)集合中的頂點(diǎn)表示一個(gè)無(wú)回路的連通分量，很明顯算法開(kāi)始時(shí)，把所有n個(gè)頂點(diǎn)劃分到n個(gè)集合中，每個(gè)集合只有一個(gè)頂點(diǎn)，表明頂點(diǎn)之間互不相通。當(dāng)選取一條邊時(shí)，若它的兩個(gè)頂點(diǎn)分屬于不同的集合，則表明此邊連通了兩個(gè)不同的連通分量，因每個(gè)連通分量無(wú)回路，所以連通后得到的連通分量仍不會(huì)產(chǎn)生回路，因此這條邊應(yīng)該保留，且把它們作為一個(gè)連通分量，即把它的兩個(gè)頂點(diǎn)所在集合合并成一個(gè)集合。如果選取的一條邊的兩個(gè)頂點(diǎn)屬于同一個(gè)集合，則此邊應(yīng)該舍棄，因?yàn)橥粋€(gè)集合中的頂點(diǎn)是連通無(wú)回路的，若再加入一條邊則必然產(chǎn)生回路。下面給出利用Kruskal算法構(gòu)造圖的最小生成樹(shù)的具體算法框架。① 將圖的存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權(quán)值從小到大排好序；② 設(shè)數(shù)組C[1..n1]用來(lái)存儲(chǔ)最小生成樹(shù)的所有邊，C[i]是第i次選取的可行邊在排好序的elist中的下標(biāo)；③ 設(shè)一個(gè)數(shù)組S[1..n]，S[i]都是集合，初始時(shí)S[i]= [ i ]。i:=1；{獲取的第i條最小生成樹(shù)的邊}j:=1；{邊集數(shù)組的下標(biāo)}While i=n1 Do Begin For k:=1 To n Do Begin {取出第j條邊，記下兩個(gè)頂點(diǎn)分屬的集合序號(hào)} If elist[j].fromv in
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1