最小生成树Prim算法实现C++.docx
- 文档编号:5135280
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:27
- 大小:124.62KB
最小生成树Prim算法实现C++.docx
《最小生成树Prim算法实现C++.docx》由会员分享,可在线阅读,更多相关《最小生成树Prim算法实现C++.docx(27页珍藏版)》请在冰点文库上搜索。
最小生成树Prim算法实现C++
最小生成树Prim算法实现的c++语言,使用邻接矩阵存储边信息。
共三个文件。
第一个
#ifndef__PRIM_H_#define__PRIM_Htemplate
返回w,使得边<w,adjVex[w]>为连接V-U到U的具有最小权值的边{
intw=-1;//初始化最小顶点
intv;//临时顶点
for(v=0;v {//查找第一个满足条件的V-U中顶点v //表示v为V-U中的顶点 //存在从v到U的边(v,adjVex[v]) V-U到U的具有最小权值的边<w, if(net.GetTag(v)==UNVISITED &&net.GetWeight(v,adjVex[v])>0) { w=v; break; } } for(v++;v adjVex[w]> if(net.GetTag(v)==UNVISITED&&net.GetWeight(v,adjVex[v])>0&&net.GetWeight(v,adjVex[v]) w=v;returnw; } template voidMiniSpanTreePrim(constAdjMatrixUndirNetwork //初始条件: 存在网net,u0为g的一个顶点 //操作结果: 用Prim算法从uO出发构造网g的最小代价生成树 { if(uO ");//抛出异常 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=O;v {//初始化辅助数组adjVex,并对顶点作标志,此时U={v0} if(v! =uO) {//对于v€V-U adjVex[v]=u0; net.SetTag(v,UNVISITED); } else {//对于v€U net.SetTag(v,VISITED); adjVex[v]=u0; } } for(u=1;u {//选择生成树的其余net.GetVexNum()-1个顶点 w=MinVertex(net,adjVex); //选择使得边 if(w==-1) {//表示U与V-U已无边相连 return; } cout<<"edge: ("< " < if(net.GetTag(v)==UNVISITED&&//v€V-U (net.GetWeight(v,w) net.GetWeight(v,adjVex[v])==0))//不存在边 {// adjVex[v]=w; } } } delete[]adjVex;//释放存储空间 } #endif 第二个 #ifndef__ADJ_MATRIX_UNDIR_GRAPH_H_#define__ADJ_MATRIX_UNDIR_GRAPH_H #include"utility.h" //实用程序软件包 //无向网的邻接矩阵类模板 template { protected: //顶点个数和边数 //邻接矩阵 //顶点数据 //指向标志数组的指针 //无穷大 //销毁无向网,释放无向网占用的空间 //邻接矩阵的数据成员: intvexNum,edgeNum;WeightType**Matrix;ElemType*elems;mutableStatusCode*tag;WeightTypeinfinity; //辅助函数模板: voidDestroyHelp(); public: //抽象数据类型方法声明及重载编译系统默认方法声明: AdjMatrixUndirNetwork(ElemTypees[],intvertexNum=DEFAULT_SIZE,WeightTypeinfinit=(WeightType)DEFAULT_INFINITY); vertexNum,infinit表示无穷大,边数为0的无向 //构造顶点数据为es[],顶点个数为网 AdjMatrixUndirNetwork(intvertexNum=DEFAULT_SIZE,WeightTypeinfinit=(WeightType)DEFAULT_INFINITY); //构造顶点个数为vertexNum,infinit表示无穷大,边数为0的无向网 //析构函数模板 求顶点的元素设置顶点的元素值//返回无穷大//返回顶点个数//返回边数个数返回顶点v的第一个邻接点返回顶点v1的相对于v2的下一个邻接点 ~AdjMatrixUndirNetwork(); StatusCodeGetElem(intv,ElemType&e)const;//StatusCodeSetElem(intv,constElemType&e);//WeightTypeGetInfinity()const;intGetVexNum()const;intGetEdgeNum()const; //插入顶点为v1和v2,权为w的边 intFirstAdjVex(intv)const;//intNextAdjVex(intv1,intv2)const;// voidInsertEdge(intv1,intv2,WeightTypew); voidDeleteEdge(intv1,intv2);//删除顶点为v1和v2的边 WeightTypeGetWeight(intv1,intv2)const;//返回顶点为v1和v2的边的权值voidSetWeight(intv1,intv2,WeightTypew);//设置顶点为v1和v2的边的权值StatusCodeGetTag(intv)const;//返回顶点v的标志 voidSetTag(intv,StatusCodeval)const;//设置顶点v的标志为valAdjMatrixUndirNetwork(constAdjMatrixUndirNetwork AdjMatrixUndirNetwork AdjMatrixUndirNetwork }; template voidDisplay(constAdjMatrixUndirNetwork //无向网的邻接矩阵类的实现部分template : AdjMatrixUndirNetwork(ElemTypees[],intvertexNum,WeightTypeinfinit) //操作结果: 构造顶点数据为es[],顶点个数为vertexNum,infinit表示无穷大,边数为0的无 向网 { if(vertexNum<0)throwError("顶点个数不能为负! ");//抛出异常 for(iPos=0;iPos { for(intjPos=0;jPos Matrix[iPos][jPos]=infinity; 生成邻接矩阵 Matrix=(WeightType**)newWeightType*[vexNum];//for(iPos=0;iPos {//生成邻接矩阵的行 Matrix[iPos]=newWeightType[vexNum]; } for(iPos=0;iPos { for(intjPos=0;jPos } } } template voidAdjMatrixUndirNetwork : DestroyHelp() //操作结果: 销毁无向网,释放无向网占用的空间 { delete[]elems; delete[]tag; //释放顶点数据 //释放标志 for(intiPos=0;iPos {//释放邻接矩阵的行 delete[]Matrix[iPos]; } delete[]Matrix;//释放邻接矩阵 } template AdjMatrixUndirNetwork : ~AdjMatrixUndirNetwork() //操作结果: 释放对象所占用空间 { DestroyHelp(); } template StatusCodeAdjMatrixUndirNetwork : GetElem(intv,ElemType&e)const //操作结果: 求顶点v的元素,v的取值范围为0wvvvexNum,v合法时返回 //SUCCESS否则返回RANGE_ERROR { if(v<0||v>=vexNum) {//v范围错 returnNOT_PRESENT;//元素不存在 } else {//v合法 e=elems[v];//将顶点v的元素值赋给e returnENTRY_FOUND;//元素存在 } } template StatusCodeAdjMatrixUndirNetwork : SetElem(intv,constElemType&e) //操作结果: 设置顶点的元素值v的取值范围为0wvvvexNum,v合法时返回 //SUCCESS否则返回RANGE_ERROR { if(v<0||v>=vexNum) {//v范围错 returnRANGE_ERROR;//位置错 } else {//v合法 elems[v]=e;//顶点元素 returnSUCCESS;//成功 template WeightTypeAdjMatrixUndirNetwork : GetInfinity()const //操作结果: 返回无穷大 { returninfinity; } template intAdjMatrixUndirNetwork : GetVexNum()const //操作结果: 返回顶点个数 { returnvexNum; } template intAdjMatrixUndirNetwork : GetEdgeNum()const //操作结果: 返回边数个数 { returnedgeNum; } template intAdjMatrixUndirNetwork : FirstAdjVex(intv)const //操作结果: 返回顶点v的第1个邻接点 { if(v<0||v>=vexNum)throwError("v不合法! ");//抛出异常 for(intcur=0;cur {//查找邻接点 if(Matrix[v][cur]! =infinity)returncur; } return-1;//返回-1表示无邻接点 } template intAdjMatrixUndirNetwork : NextAdjVex(intv1,intv2)const //操作结果: 返回顶点v1的相对于v2的下1个邻接点 { if(v1<0||v1>=vexNum)throwError("v1不合法! ");//抛出异常 if(v2<0||v2>=vexNum)throwError("v2不合法! ");//抛出异常 if(v1==v2)throwError("v1不能等于v2! "); for(intcur=v2+1;cur {//查找邻接点 if(Matrix[v1][cur]! =infinity)returncur;} return-1;} //抛出异常 //返回-1表示无邻接点 template voidAdjMatrixUndirNetwork : InsertEdge(intv1,intv2,WeightTypew) //操作结果: 插入顶点为v1和v2,权为w的边 { if(v1<0||v1>=vexNum)throwError("v1不合法! ");//抛出异常 if(v2<0||v2>=vexNum)throwError("v2不合法! ");//抛出异常 if(v1==v2)throwError("v1不能等于v2! ");//抛出异常 if(w==infinity)throwError("w不能为无空大! ");//抛出异常 if(Matrix[v1][v2]==infinity&&Matrix[v2][v1]==infinity) {//原无向网无边(v1,v2),插入后边数自增1edgeNum++; template voidAdjMatrixUndirNetwork : DeleteEdge(intv1,intv2) II操作结果: 删除顶点为v1和v2的边 { if(v1<0||v1>=vexNum)throwError("v1不合法! ");II抛出异常 if(v2<0||v2>=vexNum)throwError("v2不合法! ");II抛出异常 if(v1==v2)throwError("v1不能等于v2! ");II抛出异常 if(Matrix[v1][v2]! =infinity&&Matrix[v2][v1]! =infinity) {II原无向网存在边(v1,v2),删除后边数自减1edgeNum--; } Matrix[v1][v2]=infinity;II修改 Matrix[v2][v1]=infinity;II修改 } template WeightTypeAdjMatrixUndirNetwork : GetWeight(intv1,intv2)const//操作结果: 返回顶点为v1和v2的边的权值 { if(v1<0||v1>=vexNum)throwError("v1不合法! ");//抛出异常 if(v2<0||v2>=vexNum)throwError("v2不合法! ");//抛出异常 returnMatrix[v1][v2]; } template voidAdjMatrixUndirNetwork : SetWeight(intv1,intv2,WeightTypew)//操作结果: 设置顶点为v1和v2的边的权值 { if(v1<0||v1>=vexNum)throwError("v1不合法! ");//抛出异常 if(v2<0||v2>=vexNum)throwError("v2不合法! ");//抛出异常 if(v1==v2)throwError("v1不能等于v2! ");//抛出异常 if(w==infinity)throwError("w不能为无空大! ");//抛出异常 template StatusCodeAdjMatrixUndirNetwork : GetTag(intv)constII操作结果: 返回顶点v的标志 { if(v<0||v>=vexNum)throwError("v不合法! ");II抛出异常 returntag[v]; } template voidAdjMatrixUndirNetwork : SetTag(intv,StatusCodeval)constII操作结果: 设置顶点v的标志为val { if(v<0||v>=vexNum)throwError("v不合法! ");II抛出异常 tag[v]=val; } template AdjMatrixUndirNetwork : AdjMatrixUndirNetwork(constAdjMatrixUndirNetwork II操作结果: 由无向网的邻接矩阵copy构造新无向网的邻接矩阵copy——复制构造函数模 intiPos,jPos; infinity=copy.infinity;vexNum=copy.vexNum;edgeNum=copy.edgeNum; //临时变量 //复制无穷大 //复制顶点数 //复制边数 elems=newElemType[vexNum];for(iPos=0;iPos elems[iPos]=copy.elems[iPos];} //生成顶点数据数组 tag=newStatusCode[vexNum];for(iPos=0;iPos
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 生成 Prim 算法 实现 C+