圖論最小生成樹在城市交通建設(shè)中的應(yīng)用

1、最小生成樹在城市交通建設(shè)中的應(yīng)用 最小生成樹在城市交通建設(shè)中的應(yīng)用姓 名 XX 學(xué) 號(hào) S100203029 專 業(yè) 計(jì)算機(jī)應(yīng)用技術(shù) 計(jì)算機(jī)應(yīng)用技術(shù) 2010 年 12 月 4I最小生成樹在城市交通建設(shè)中的應(yīng)用 最小生成樹在城市交通建設(shè)中的應(yīng)用摘 要連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹是最主要的應(yīng)用。比如要在 n 個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是如何保證 n

2、點(diǎn)連通的前提下最節(jié)省經(jīng)費(fèi)，就應(yīng)用到了最小生成樹。求圖的最小生成樹有兩種算法，一種是 Prim（普里姆）算法，另一種是 Kruskal（克魯斯卡爾）算法。本文通過將城市各地點(diǎn)轉(zhuǎn)換成連通圖，再將連通圖轉(zhuǎn)換成鄰接矩陣。在 Microsoft Visual C++上，通過輸入結(jié)點(diǎn)和權(quán)值，用普里姆算法獲得權(quán)值最小邊來得到最小生成樹，從而在保證各個(gè)地點(diǎn)之間能連通的情況下節(jié)省所需費(fèi)用。本文從分析課題的題目背景、題目意義、題目要求等出發(fā)，分別從需求分