最小生成树_prim算法实现c++

《最小生成树_prim算法实现c++》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最小生成树Prim算法实现的c++语言，使用邻接矩阵存储边信息。共三个文件。第一个#ifndef__PRIM_H__#define__PRIM_H__templateintMinVertex(constAdjMatrixUndirNetwork&net,int*adjVex)//操作结果：返回w，使得边为连接V-U到U的具有最小权值的边{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)//初始条件：存在网net,u0为g的一个顶点//操作结果：用Prim算法从u0出发构造网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具有最小权值边的邻接点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的具有最小权值的边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、//边的权值更小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"//实用程序软件包//无向网的邻接矩阵类模板templateclassAdjMatrixUndirNetwork{protected://邻接矩阵的数据成员:intvexNum,ed

12、geNum;//顶点个数和边数WeightType**Matrix;//邻接矩阵ElemType*elems;//顶点数据mutableStatusCode*tag;//指向标志