基于改進(jìn)的Kruskal算法求解最短路程問(wèn)題

1、提供完整版的畢業(yè)設(shè)計(jì)研究生綜合應(yīng)用報(bào)告課程名稱 高級(jí)計(jì)算機(jī)網(wǎng)絡(luò) 學(xué) 院 計(jì)算機(jī)學(xué)院 年 級(jí) 一 專業(yè)班 學(xué) 生 姓 名 張仲勛 學(xué) 號(hào) 開(kāi) 課 時(shí) 間 2014 至 2015 學(xué)年 第 一 學(xué)期基于流媒體的高清視頻傳輸摘要本文使用適當(dāng)改進(jìn)的Kruskal算法，解決為使總路程最短如何選擇出行路線的問(wèn)題。把要到訪的地點(diǎn)作為頂點(diǎn)，所有頂點(diǎn)兩兩之間的連線和距離（起點(diǎn)和終點(diǎn)無(wú)連線）分別作為邊以及邊的權(quán)值，構(gòu)造加權(quán)無(wú)向圖。問(wèn)題即轉(zhuǎn)化為尋求從起點(diǎn)出發(fā)，遍歷中間各點(diǎn)，最后到達(dá)終點(diǎn)的最短路徑。該路徑是無(wú)向圖的生成樹(shù)，但不一定是最小生成樹(shù)。路徑的起點(diǎn)和終點(diǎn)已經(jīng)固定，他們的度數(shù)必須為1，而中間各頂點(diǎn)的度數(shù)必須為2，

2、原因在問(wèn)題分析里面進(jìn)行說(shuō)明。通過(guò)對(duì)Kruskal算法適當(dāng)改進(jìn)可以得到該路徑。關(guān)鍵詞：最短路徑 生成樹(shù) Kruskal算法一、 問(wèn)題分析對(duì)于該類問(wèn)題，要先得到任意兩個(gè)地點(diǎn)之間的距離，因?yàn)椴荒苤苯訌钠瘘c(diǎn)到達(dá)終點(diǎn)，所以不需要知道起點(diǎn)和終點(diǎn)的直接距離，也即在其加權(quán)圖上這兩點(diǎn)之間沒(méi)有邊?？梢酝ㄟ^(guò)百度地圖1等工具獲取兩個(gè)地點(diǎn)的距離。由于路徑的起點(diǎn)和終點(diǎn)固定，起點(diǎn)只能“出去”，終點(diǎn)只能“進(jìn)來(lái)”，當(dāng)求其最短路徑時(shí)，這兩個(gè)點(diǎn)的度數(shù)要為1。對(duì)于起點(diǎn)和終點(diǎn)之外的其他頂點(diǎn)，其度數(shù)只能為2，原因如下：對(duì)于任意三個(gè)頂點(diǎn)（起點(diǎn)和終點(diǎn)除外）A、B、C，假如A的度數(shù)為3（大于3時(shí)只考慮和A相臨的其中兩點(diǎn)），如圖1所示。圖1：一

3、點(diǎn)的度數(shù)大于2設(shè)A先到B點(diǎn)，要經(jīng)過(guò)C點(diǎn)的話必須回到A，再到C，其路程必然比從B直接到C遠(yuǎn)。這種情形也包含某個(gè)點(diǎn)的度數(shù)為1的情況，所以除起點(diǎn)和終點(diǎn)外其他頂點(diǎn)的必為2。綜上所述，在改進(jìn)Kruskal算法時(shí)，只需加上兩個(gè)限制條件即可，即起點(diǎn)的度數(shù)為1，其余頂點(diǎn)度數(shù)為2。二、 模型建立把每個(gè)地點(diǎn)作為頂點(diǎn)，每?jī)蓚€(gè)頂點(diǎn)相連作為邊，兩個(gè)頂點(diǎn)之間的距離作為邊的權(quán)值，構(gòu)造加權(quán)無(wú)向圖，如圖2所示（單位：千米）。其中a代表重慶，b代表五臺(tái)山，c代表黃鶴樓，d代表泰山，e代表北京，。由于不能從出發(fā)點(diǎn)直接到達(dá)終點(diǎn)，所以a到e沒(méi)有連線。圖2：路線模型圖三、 符號(hào)說(shuō)明：存放生成樹(shù)的邊的集合，初態(tài)為空集；：生成樹(shù)的權(quán)值，初值

4、為零；VS：部分樹(shù)的頂點(diǎn)集的集合，初值為：a，b，c，d，e；：頂點(diǎn)的度數(shù)。四、 Kruskal算法改進(jìn)Kruskal算法步驟2：，0，VSa，b，c，d，e，將邊按權(quán)值小到大排成隊(duì)列Q；若= 1，輸出，停止。否則轉(zhuǎn)入下一步；從Q中取出邊，并從Q中刪除；如果u，v在VS的同一個(gè)元素中，則轉(zhuǎn)，否則分屬兩個(gè)集合，進(jìn)入下一步；，VSVS + ，+，轉(zhuǎn)入。由問(wèn)題分析可知，在對(duì)Kruskal算法進(jìn)行改進(jìn)時(shí)，只需添加兩個(gè)限制條件，起點(diǎn)和終點(diǎn)的度數(shù)為1，其余各點(diǎn)度數(shù)為2。引入來(lái)表示頂點(diǎn)的度數(shù)，初值為0，把Kruskal算法的第步改為如下形式：如果u，v在VS的同一個(gè)元素中，或者 (，u，v不是起點(diǎn)或終點(diǎn))，

5、或者 (，u，v是起點(diǎn)或終點(diǎn))，則轉(zhuǎn)，否則u，v分屬兩個(gè)集合，+ 1，+ 1，進(jìn)入下一步。五、問(wèn)題求解使用改進(jìn)的Kruskal算法求圖2的最小生成樹(shù)，按邊的權(quán)值從小到大排列為：，步驟如下：（1） 選出邊，得到= ，= 359，VS = ，；+ 1 = 1；+ 1 = 1；（2） 選出邊，由于的度只能為1，重新選邊；（3） 選出邊，由于b，d分屬VS的兩個(gè)不同的集合，= 1，= 0，故得到=，VS =，a，c， = 359 + 576=935，+ 1 = 2，+ 1 = 1；（4） 選出邊，由于c，d分屬VS的兩個(gè)不同的集合，= 0，= 1，故得到=，VS = ，a ，= 935+863 = 1798，+ 1 = 1，+ 1 = 2；（5） 選出邊，由于a，c分屬VS的兩個(gè)不同的集合，= 0，= 1故得到=，VS = ，= 1798+896 = 2694，+ 1 = 1，+ 1 = 2；（6） 因=1，輸出=，= 2694，計(jì)算停止。的圖形如圖2所示，即是通過(guò)改進(jìn)的Kruskal算法求得的最小生成樹(shù)。圖2：最短路線圖由圖2可知，當(dāng)如下安排行程：重慶到黃鶴樓，黃鶴樓到泰山，