最小生成樹算法分析報(bào)告-免費(fèi)閱讀
【正文】 39。為了節(jié)省費(fèi)用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺計(jì)算機(jī)可以間接的通過若干臺計(jì)算機(jī)（作為中轉(zhuǎn)）來實(shí)現(xiàn)與另一臺計(jì)算機(jī)的連接。如果選取的一條邊的兩個頂點(diǎn)屬于同一個集合，則此邊應(yīng)該舍棄，因?yàn)橥粋€集合中的頂點(diǎn)是連通無回路的，若再加入一條邊則必然產(chǎn)生回路。其中圖（E）中的4條粗線將5個頂點(diǎn)連通成了一棵最小生成樹。例城市公交網(wǎng)[問題描述]有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個城市間的連通關(guān)系，邊上的權(quán)為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點(diǎn)，即任一對城市都是連通的。在這種情況下，圖中所有頂點(diǎn)加上遍歷過程中經(jīng)過的邊所構(gòu)成的子圖稱為原圖的生成樹。二、求圖的最小生成樹算法嚴(yán)格來說，如果圖G=（V，E）是一個連通的無向圖，則把它的全部頂點(diǎn)V和一部分邊E’構(gòu)成一個子圖G’，即G’=（V， E’），且邊集E’能將圖中所有頂點(diǎn)連通又不形成回路，則稱子圖G’是圖G的一棵生成樹。[問題分析] 出發(fā)點(diǎn)：具有n個頂點(diǎn)的帶權(quán)連通圖，其對應(yīng)的生成樹有n1條邊。最后的T即為最小生成樹。兩臺計(jì)算機(jī)被連接是指它們時間有數(shù)據(jù)線連接。[輸出格式] ，一個整數(shù)，表示最小的連接費(fèi)用。)；Rewrite(Output)； Readln(n)； For i := 1 To n Do Begin For j := 1 To n Do Read(g[i，j])； Readln；End； Fillchar(l, sizeof(l), $7F)； {初始化為maxint}l[1] := 0； {開始時生成樹中只有第1個頂點(diǎn)} Fillchar(u, sizeof(u), 1)； {初始化為True，表示所有頂點(diǎn)均未加入} For i := 1 To n Do Begin k := 0； For j := 1 To n Do {找一個未加入到生成樹中的頂點(diǎn)，記為k，要求k到當(dāng)前生成樹中所有頂點(diǎn)的代價最小} If u[j] And (l[j] l[k]) Then k := j； u[k] := False； {頂點(diǎn)k加入生成樹} For j :=
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1