圖論最小生成樹在城市交通建設(shè)中的應(yīng)用-資料下載頁
2025-06-23 15:06本頁面
【正文】 //temp=1時(shí)將權(quán)重賦值最大值88 [i][j]=maxvalue。 } else //ij由于權(quán)重是對(duì)稱的即呈上三角或下三角分布故只需將i,j對(duì)換即可 [i][j]=[j][i]。 } printf(\n)。 } return x。 //返回圖x}void print(mgraph g,int n) //打印函數(shù){ int i,j。 //定義整型i,j printf( )。 //打印美觀需要 for(i=1。i=n。i++) printf(%2d ,i)。 printf(\n)。 for(i=1。i=n。i++) //雙層循環(huán)按矩陣方式打印輸出各節(jié)點(diǎn)間權(quán)值 { printf(%d ,i)。 for(j=1。j=n。j++) printf(%2d ,[i][j])。 printf(\n)。 } }void prim(mgraph g,int k,int n) //核心算法Prim算法實(shí)現(xiàn)函數(shù){ int i,j,min,p。 //定義整型變量i,j用于循環(huán) min和p分別用于臨時(shí)存放最小權(quán)值及其下標(biāo) struct //定義型類型數(shù)據(jù)closedge[]用于臨時(shí)存放下標(biāo)和最小邊 { int adjvex。 int lowcost。 }closedge[maxnum]。 for(i=1。i=n。i++) //初始化輔助數(shù)組 if(i!=k) { closedge[i].adjvex=k。 closedge[i].lowcost=[k][i]。 } closedge[k].lowcost=0。 //將節(jié)點(diǎn)加入生成樹中 for(i=1。in。i++) //循環(huán)比較最小權(quán)值且將最小權(quán)值的點(diǎ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é)點(diǎn)不在已生成樹中且權(quán)值最下 { min=closedge[j].lowcost。 //替換最小權(quán)值為當(dāng)前節(jié)點(diǎn)的權(quán)值 p=j。 //記錄該節(jié)點(diǎn)下標(biāo) } printf(%d_ _%d\n,closedge[p].adjvex,p,min)。 //打印最小的權(quán)值的下標(biāo)和最小邊 closedge[p].lowcost=0。 //將該節(jié)點(diǎn)加入生成樹中 for(j=1。j=n。j++) //刷新臨時(shí)存放空間 if(([p][j]) (closedge[j].lowcost)) { closedge[j].lowcost=[p][j]。 //賦值最小邊 closedge[j].adjvex=p。 //賦值最小邊對(duì)應(yīng)下標(biāo) } }}int main() //主函數(shù){ int n,start。 //定義整型n,start表示節(jié)點(diǎn)數(shù)和開始節(jié)點(diǎn) printf(請輸入節(jié)點(diǎn)數(shù)(不大于10):)。 scanf(%d,amp。n)。 mgraph red。 //定義圖red red=input(n)。 //調(diào)用輸入函數(shù)用戶輸入數(shù)據(jù) print(red,n)。 //調(diào)用輸出函數(shù)打印輸出所輸入的數(shù)據(jù) printf(請輸入開始節(jié)點(diǎn):)。 scanf(%d,amp。start)。 prim(red,start,n)。 //調(diào)用prim函數(shù)實(shí)現(xiàn)prim算法求最小生成樹 return 0。}
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1