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