資源描述:
《最小生成樹_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)志