资源描述:
《数据结构算法——Visual C++ 6.0程序集 第6章》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构算法VisualC++6.0程序集侯识忠等编著中国水利水电出版社第六章图6、0图的类定义和实现//图的相关数据类型的定义graph.h//最多顶点数constintMaxV=10;//最大权值constintMaxValue=99;//定义邻接表中的边结点类型structedgenode{intadjvex;//邻接点域intweight;//权值域edgenode*next;//指向下一个边结点的链域};//定义邻接表类型typedefedgenode**adjlist;//邻接矩阵类定义classAdjMatrix{private:
2、charg[MaxV];//顶点信息数组intsize;//当前顶点数intGA[MaxV][MaxV];//定义邻接矩阵GAintnumE;//当前边数public://构造函数,初始化图的邻接矩阵AdjMatrix(intn,intk2);//判断图空否boolGraphEmpty(){returnsize==0;}//取当前顶点数intNumV(){returnsize;}//取当前边数intNumEdges(){returnnumE;}//取顶点i的值charGetValue(constinti);//取弧的权intGet
3、Weight(constintv1,constintv2);//在位置pos处插入顶点VvoidInsertV(constchar&V,intpos);//插入弧,权为weightvoidInsertEdge(constintv1,constintv2,intweight);//删除顶点i与顶点i相关的所有边charDeleteVE(constinti);//删除弧voidDeleteEdge(constintv1,constintv2);//建立图的邻接矩阵voidCreateMatrix(intn,intk1,i
4、ntk2);//k1为0则无向否则为有向,k2为0则无权否则为有权//从初始点vi出发深度优先搜索由邻接矩阵表示的图voiddfsMatrix(bool*&visited,inti,intn,intk2);//从初始点vi出发广度优先搜索由邻接矩阵表示的图voidbfsMatrix(bool*&visited,inti,intn,intk2);//由图的邻接矩阵得到图的邻接表voidgraphChange(adjlist&GL,intn,intk2);//检查输入的边序号是否越界,若越界则重输voidCheck(intn,int&i,int&j
5、);//由图的邻接矩阵建立图voidCreatgraph(intn,intk2);//对非连通图进行深度优先搜索voiddfsMatrix(intn,intk2);//对非连通图进行广度优先搜索voidbfsMatrix(intn,intk2);};//图的相关运算的实现graph.cpp#include"graph.h"//构造函数,初始化图的邻接矩阵AdjMatrix::AdjMatrix(intn,intk2){inti,j;if(k2==0){//初始化无(有)向无权图for(i=0;i6、[i][j]=0;}else{//初始化无(有)向有权图for(i=0;i>e;if(k1==0&&k2==0){//建立无向无权图cout<<"输入"<7、<"条无向无权边的起点和终点序号!"<>i>>j;Check(n,i,j);GA[i][j]=GA[j][i]=1;}}elseif(k1==0&&k2!=0){//建立无向有权图cout<<"输入"<>i>>j>>w;Check(n,i,j);GA[i][j]=GA[j][i]=w;}}elseif(k1!=0&&k2==0){//建立有向无权图cout<<"输入"<8、无权边的起点和终点序号!"<>i>>j;Check(n,i,j);GA[i][j]=1;}}e