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