圖論最小生成樹在城市交通建設(shè)中的應(yīng)用-wenkub
2023-07-08 15:06:47 本頁面
【正文】 姓 名 XX 學(xué) 號 S100203029 專 業(yè) 計算機應(yīng)用技術(shù) 2010年12月414 / 17目錄摘 要 I緒論 12 有關(guān)最小生成樹的概念 23 prim算法介紹 34 系統(tǒng)設(shè)計及其應(yīng)用 5一、系統(tǒng)設(shè)計 5二、最小生成樹應(yīng)用 65 總結(jié) 9參考文獻 10附件： 11最小生成樹在城市交通建設(shè)中的應(yīng)用摘 要連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹是最主要的應(yīng)用。在Microsoft Visual C++上，通過輸入結(jié)點和權(quán)值，用普里姆算法獲得權(quán)值最小邊來得到最小生成樹，從而在保證各個地點之間能連通的情況下節(jié)省所需費用。其結(jié)果是，資源浪費，效率低下，使用不便利。從而能節(jié)省更多的錢來投資其他地方建設(shè)，如農(nóng)村交通建設(shè)。普里姆算法通過尋找無向圖中權(quán)值最小的邊，并且將其組合成最小生成樹，同時將最小生成樹以點集的形式輸出，便于觀察。(3) 要能夠形象地演示PRIM算法求最小生成樹的過程。2 有關(guān)最小生成樹的概念最小生成樹：連通加權(quán)圖里權(quán)和最小的生成樹稱為最小生成樹。定義一（圖）：圖是有一個非空的頂點集合和一個描述頂點之間的關(guān)系即邊的集合組成。當(dāng)n=0時表示為空樹。即除根結(jié)點無父結(jié)點，其余各結(jié)點都有一個父結(jié)點和n（n=0）個子結(jié)點。設(shè)G=(V,E)是一個圖，其中V={v1,v2,…,vn}。也表示i結(jié)點是否與j結(jié)點連通。Prim算法的基本思想：首先，選擇帶最小的邊，把它放進生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n1條邊為止。輸出選中的這條邊，它是最小生成樹中的一條邊。知道最后所有的權(quán)值最小的邊全部輸出。while UV dobegin(u,v):= u∈U且v∈VU的最小權(quán)邊。end。注意：假設(shè)輸入的圖是連通圖}varlowcost:array [1..maxsize] of integer。beginfor i:=2 to size do {初始化，此時U只含有頂點1}beginlowcost[i]:= G[1,i]。used[1]:=true。j:=k。,closeset[j],39。)。end。 char hnode。圖的存儲結(jié)構(gòu)為：define INFINITY INT_MAX //最大值define MAX_VERTEX_NUM 20 //最多的頂點個數(shù)typedef enum{DG,DN,UDG,UDN} GraphKind。typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。 //圖的種類標(biāo)志 }Mgraph。 }closedge[100]。 closedge[i].lowcost=[k][i]。i++) //循環(huán)比較最小權(quán)值且將最小權(quán)值的點加入生成樹中并打印輸出 { p=1。j++) //循環(huán)n次比較最小權(quán)值 if(closedge[j].lowcost!=0amp。 //記錄該節(jié)點下標(biāo) } printf(%d_ _%d\n,closedge[p].adjvex,p,min)。j++) //刷新臨時存放空間 if(([p][j]) (closedge[j].lowcost)) { closedge[j].lowcost=[p][j]。這個程序還有待開發(fā)，將其運用到交通建設(shè)上，能起到節(jié)約資源和時間的作用，并且也是交通建設(shè)發(fā)展必要的工具。【4】《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴(yán)蔚敏 吳偉民，清華大學(xué)出版社。 //該數(shù)據(jù)類型用標(biāo)識符mgraph表示mgraph input(int n) //數(shù)據(jù)輸入函數(shù)用于輸入各節(jié)點間邊的權(quán)值{ mgraph x。 } for(in
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1