最小生成樹算法分析報告-閱讀頁
2025-08-06 22:19本頁面
【正文】 ，E），我們介紹兩種基于貪心的算法，Prim算法和Kruskal算法。其中圖（E）中的4條粗線將5個頂點連通成了一棵最小生成樹。因為操作是沿著邊進(jìn)行的，所以數(shù)據(jù)結(jié)構(gòu)采用邊集數(shù)組表示法，下面給出Prim算法構(gòu)造圖的最小生成樹的具體算法框架。將圖G中的邊按權(quán)值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進(jìn)行下去，直到TE中包含n1條邊為止。如何證明呢？下圖是按照Kruskal算法給出了例題中圖（A）最小生成樹的生成過程：Kruskal算法在實現(xiàn)過程中的關(guān)鍵和難點在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？我們可以將頂點劃分到不同的集合中，每個集合中的頂點表示一個無回路的連通分量，很明顯算法開始時，把所有n個頂點劃分到n個集合中，每個集合只有一個頂點，表明頂點之間互不相通。如果選取的一條邊的兩個頂點屬于同一個集合，則此邊應(yīng)該舍棄，因為同一個集合中的頂點是連通無回路的，若再加入一條邊則必然產(chǎn)生回路。① 將圖的存儲結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權(quán)值從小到大排好序；② 設(shè)數(shù)組C[1..n1]用來存儲最小生成樹的所有邊，C[i]是第i次選取的可行邊在排好序的elist中的下標(biāo)；③ 設(shè)一個數(shù)組S[1..n]，S[i]都是集合，初始時S[i]= [ i ]。三、應(yīng)用舉例例最優(yōu)布線問題（，）[問題描述]學(xué)校有n臺計算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。由于計算機(jī)所處的位置不同，因此不同的兩臺計算機(jī)的連接費用往往是不同的。為了節(jié)省費用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺計算機(jī)可以間接的通過若干臺計算機(jī)（作為中轉(zhuǎn)）來實現(xiàn)與另一臺計算機(jī)的連接。[輸入格式] ，第一行為整數(shù)n（2=n=100），表示計算機(jī)的數(shù)目。第x+1行y列的整數(shù)表示直接連接第x臺計算機(jī)和第y臺計算機(jī)的費用。[樣例輸入]30 1 21 0 12 1 0[樣例輸出]2（注：表示連接1和2，2和3，費用為2）[問題分析]本題是典型的求圖的最小生成樹問題，我們可以利用Prim算法或者Kruskal算法求出，下面的程序在數(shù)據(jù)結(jié)構(gòu)上對Kruskal算法做了一點修改，具體細(xì)節(jié)請看程序及注解。3
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1