最小生成樹算法分析報告-在線瀏覽
2024-09-01 22:19本頁面
【正文】 n1行，每行為兩個城市的序號，表明這兩個城市間建一條高速公路?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計可使得工程的總造價最少。求圖的最小生成樹具有很高的實際應(yīng)用價值，比如下面的這個例題。二、求圖的最小生成樹算法嚴格來說，如果圖G=（V，E）是一個連通的無向圖，則把它的全部頂點V和一部分邊E’構(gòu)成一個子圖G’，即G’=（V， E’），且邊集E’能將圖中所有頂點連通又不形成回路，則稱子圖G’是圖G的一棵生成樹。由此可以看出，一個圖的生成樹是不唯一的，不同的搜索方法可以得到不同的生成樹，即使是同一種搜索方法，出發(fā)點不同亦可導(dǎo)致不同的生成樹。對于不連通的無向圖和不是強連通的有向圖，若有根或者從根外的任意頂點出發(fā)，調(diào)用一次bfs或dfs后一般不能系統(tǒng)地訪問所有頂點，而只能得到以出發(fā)點為根的連通分支（或強連通分支）的生成樹。最小生成樹算法分析一、生成樹的概念若圖是連通的無向圖或強連通的有向圖，則從其中任一個頂點出發(fā)調(diào)用一次bfs或dfs后便可以系統(tǒng)地訪問圖中所有頂點；若圖是有根的有向圖，則從根出發(fā)通過調(diào)用一次dfs或bfs亦可系統(tǒng)地訪問所有頂點。在這種情況下，圖中所有頂點加上遍歷過程中經(jīng)過的邊所構(gòu)成的子圖稱為原圖的生成樹。要訪問其它頂點需要從沒有訪問過的頂點中找一個頂點作為起始點，再次調(diào)用bfs或dfs，這樣得到的是生成森林?？梢宰C明：具有n個頂點的帶權(quán)連通圖，其對應(yīng)的生成樹有n1條邊。對于加權(quán)連通圖，生成樹的權(quán)即為生成樹中所有邊上的權(quán)值總和，權(quán)值最小的生成樹稱為圖的最小生成樹。例城市公交網(wǎng)[問題描述]有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關(guān)系，邊上的權(quán)為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的。[輸入] n（城市數(shù)，1=n=100） e（邊數(shù)） 以下e行，每行3個數(shù)i,j,wij，表示在城市i,j之間修建高速公路的造價。[舉例]下面的圖（A）表示一個5個城市的地圖，圖（B）、（C）是對圖（A）分別進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為20和33，前者比后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為19。那么選哪n1條邊呢？設(shè)圖G的度為n，G=（V
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1