最小生成樹算法分析報(bào)告(更新版)
【正文】 一個(gè)連通分量，即把它的兩個(gè)頂點(diǎn)所在集合合并成一個(gè)集合。 當(dāng)然，如果將任意兩臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接，費(fèi)用將是相當(dāng)龐大的。[參考程序]Program wire(Input, Output)；var g : Array [1..100, 1..100] Of Integer；{鄰接矩陣}l : Array [0..100] Of Integer； {l[i]存放頂點(diǎn)i到當(dāng)前已建成的生成樹中任意一頂點(diǎn)j的權(quán)值g[i,j]的最小值}u : Array [0..100] Of Boolean； { u[i]=True，表示頂點(diǎn)i還未加入到生成樹中；u[i]=False，表示頂點(diǎn)I已加入到生成樹中 } n, i, j, k, total : Integer；Begin Assign(Input, 39。)；Reset(Input)；Assign(Output, 39。 現(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，你的任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）。下面給出利用Kruskal算法構(gòu)造圖的最小生成樹的具體算法框架。如何證明Prim算法的正確性呢？提示用反證法。現(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少。對(duì)于不連通的無向圖和不是強(qiáng)連通的有向圖，若有根或者從根外的任意頂點(diǎn)出發(fā)，調(diào)用一次bfs或dfs后一般不能系統(tǒng)地訪問所有頂點(diǎn)，而只能得到以出發(fā)點(diǎn)為根的連通分支（或強(qiáng)連通分支）的生成樹?？梢宰C明：具有n個(gè)頂點(diǎn)的帶權(quán)連通圖，其對(duì)應(yīng)的生成樹有n1條邊。[舉例]下面的圖（A）表示一個(gè)5個(gè)城市的地圖，圖（B）、（C）是對(duì)圖（A）分別進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為20和33，前者比后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為19。將圖G中的邊按權(quán)值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進(jìn)行下去，直到TE中包含n1條邊為止。三、應(yīng)用舉例例最優(yōu)布線問題（，）[問題描述]學(xué)校有n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。第x+1行y列的整數(shù)表示直接連接第x臺(tái)計(jì)算機(jī)和第y臺(tái)計(jì)算
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1