intMin">

最小生成樹_prim算法實現(xiàn)c++

ID:9863659

大?。?00.50 KB

頁數(shù):17頁

時間:2018-05-12

最小生成樹_prim算法實現(xiàn)c++_第1頁
最小生成樹_prim算法實現(xiàn)c++_第2頁
最小生成樹_prim算法實現(xiàn)c++_第3頁
最小生成樹_prim算法實現(xiàn)c++_第4頁
最小生成樹_prim算法實現(xiàn)c++_第5頁
資源描述:

《最小生成樹_prim算法實現(xiàn)c++》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫

1、最小生成樹Prim算法實現(xiàn)的c++語言,使用鄰接矩陣存儲邊信息。共三個文件。第一個#ifndef__PRIM_H__#define__PRIM_H__templateintMinVertex(constAdjMatrixUndirNetwork&net,int*adjVex)//操作結(jié)果:返回w,使得邊為連接V-U到U的具有最小權(quán)值的邊{intw=-1;//初始化最小頂點intv;//臨時頂點for(v=0;v<

2、net.GetVexNum();v++){//查找第一個滿足條件的V-U中頂點vif(net.GetTag(v)==UNVISITED//表示v為V-U中的頂點&&net.GetWeight(v,adjVex[v])>0)//存在從v到U的邊(v,adjVex[v]){w=v;break;}}for(v++;vif(net.GetTag(v)==UNVISITED&&net.GetWeight(v,adjVex[v])>0&&net.

3、GetWeight(v,adjVex[v])voidMiniSpanTreePrim(constAdjMatrixUndirNetwork&net,intu0)//初始條件:存在網(wǎng)net,u0為g的一個頂點//操作結(jié)果:用Prim算法從u0出發(fā)構(gòu)造網(wǎng)g的最小代價生成樹{if(u0<0

4、

5、u0>=net.GetVexNum())throwErr

6、or("u0不合法1!");//拋出異常int*adjVex;//如果v∈V-U,net.GetWeight(v,adjVex[v])>0//表示(v,adjVex[v])是v到U具有最小權(quán)值邊的鄰接點intu,v,w;//表示頂點的臨時變量adjVex=newint[net.GetVexNum()];//分配存儲空間for(v=0;v

7、ITED);}else{//對于v∈Unet.SetTag(v,VISITED);adjVex[v]=u0;}}for(u=1;u為連接V-U到U的具有最小權(quán)值的邊if(w==-1){//表示U與V-U已無邊相連return;}cout<<"edge:("<

8、adjVex[w])<=0;v=net.NextAdjVex(w,v)){//新頂點并入U后重新選擇最小邊if(net.GetTag(v)==UNVISITED&&//v∈V-U(net.GetWeight(v,w)

9、

10、//邊的權(quán)值更小net.GetWeight(v,adjVex[v])==0))//不存在邊

11、{//為新的最小邊adjVex[v]=w;}}}delete[]adjVex;//釋放存儲空間}#endif第二個#ifndef__ADJ_MATRIX_UNDIR_GRAPH_H__#define__ADJ_MATRIX_UNDIR_GRAPH_H__#include"utility.h"http://實用程序軟件包//無向網(wǎng)的鄰接矩陣類模板templateclassAdjMatrixUndirNetwork{protected://鄰接矩陣的數(shù)據(jù)成員:intvexNum,ed

12、geNum;//頂點個數(shù)和邊數(shù)WeightType**Matrix;//鄰接矩陣ElemType*elems;//頂點數(shù)據(jù)mutableStatusCode*tag;//指向標(biāo)志

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭