圖論最小生成樹在城市交通建設(shè)中的應(yīng)用(編輯修改稿)
2025-07-20 15:06 本頁面
【文章內(nèi)容簡介】 =maxint。j:=i。for k:=2 to size do {用選擇法尋找頂點分別在VU與U中權(quán)最小的邊}if (not used[k])and(lowcost[k] beginmin:=lowcost[k]。j:=k。end。writeln(fout,39。(39。,closeset[j],39。,39。,j,39。)39。)。 {輸出找到的最小生成樹的一條邊，此處可根據(jù)情況修改}used[j]:=true。 {將j填加到U}for k:=2 to size do {調(diào)整lowcost和closeset}if (not used[k])and(G[j,k] beginlowcost[k]:=G[j,k]。closeset[k]:=j。end。end。end。4 系統(tǒng)設(shè)計及其應(yīng)用一、系統(tǒng)設(shè)計數(shù)據(jù)信息以結(jié)構(gòu)體【3】【4】和數(shù)組形式儲存，結(jié)點的信息結(jié)構(gòu)體定義如下：struct graph{ char tnode。 char hnode。 double quanzhi。}gr[100]。char node[50]= 。圖的存儲結(jié)構(gòu)為：define INFINITY INT_MAX //最大值define MAX_VERTEX_NUM 20 //最多的頂點個數(shù)typedef enum{DG,DN,UDG,UDN} GraphKind。 //{有向圖、有向網(wǎng)、無向圖、無向網(wǎng)}typedef struct ArcCell{ VRType adj。 //頂點關(guān)系類型：圖：0、1 網(wǎng)：權(quán)值 InfoType *info。//該弧相關(guān)信息指針}ArcCell,AdjMaTrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]。typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。//頂點向量 AdjMaxtrix arcs。 //鄰接矩陣 int vexnum,arum。 //頂點數(shù)和弧或邊數(shù) GraphKind kind。 //圖的種類標(biāo)志 }Mgraph。Prim算法： void prim(mgraph g,int k,int n) //核心算法Prim算法實現(xiàn)函數(shù){ int i,j,min,p。 //定義整型變量i,j用于循環(huán) min和p分別用于臨時存放最小權(quán)值及其下標(biāo) struct //定義型類型數(shù)據(jù)closedge[]用于臨時存放下標(biāo)和最小邊 { int adjvex。 int lowcost。 }closedge[100]。 for(i=1。i=n。i++) //初始化輔助數(shù)組 if(i!=k) { closedge[i].adjvex=k。 closedge[i].lowcost=[k][i]。 } closedge[k].lowcost=0。 //將節(jié)點加入生成樹中 for(i=1。in。i++) //循環(huán)比較最小權(quán)值且將最小權(quán)值的點加入生成樹中并打印輸出 { p=1。 //初始化p min=maxvalue。 //初始化最小權(quán)值 for(j=1。j=n。j++) //循環(huán)n次比較最小權(quán)值 if(closedge[j].lowcost!=0amp。amp。closedge[j].lowcostmin) //當(dāng)前節(jié)點不在已生成樹中且權(quán)值最下 { min=closedge[j].lowcost。 //替換最小權(quán)值為當(dāng)前節(jié)點的權(quán)值 p=j。 //記錄該節(jié)點下標(biāo) } printf(%d_ _%
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1