实现图的邻接矩阵和邻接表存储

实现图的邻接矩阵和邻接表存储1需求分析对于下图所示的有向图G，编写一个程序完成如下功能：1 建立G的邻接矩阵并输出之2 由G的邻接矩阵产生邻接表并输出之3 再由2的邻接表产生对应的邻接矩阵并输出之2系统设计1图的抽象数据类型定义：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集数据关系R： R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作P：CreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁图GInsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点vInsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧，若G是无向的则还增添对称弧DFSTraverse(G,Visit()初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败BFSTraverse(G,Visit()初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败ADT Graph2主程序的流程：调用CreateMG函数创建邻接矩阵M；调用PrintMatrix函数输出邻接矩阵M调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G调用PrintDN函数输出邻接表G调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N调用PrintMatrix函数输出邻接矩阵N3函数关系调用图：3调试分析（1）在MGraph的定义中有枚举类型typedef enumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的，要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enumDG,DN,UDG,UDN会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型（2）算法的时间复杂度分析：CreateMG、CreateMGtoDN、CreateDNtoMG、PrintMatrix、PrintDN的时间复杂度均为O(n2)n为图的顶点数，所以main：T(n)= O(n2)4测试结果用需求分析中的测试数据输入：输出：5、用户手册（1）输入顶点数和弧数；（2）输入顶点内容；（3）按行序输入邻接矩阵，输入各弧相应权值（4）回车输出邻接矩阵M、邻接表G和邻接矩阵N6、附录源程序：#include #include #define MAX_VERTEX_NUM 20typedef int VRType;typedef int InfoType;typedef int VertexType;typedef enumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCellVRType adj;/VRType是顶点关系类型，对无权图用1或0表示是否相邻； /对带权图则为权值类型InfoType *info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind;/图的种类标志MGraph;void CreateMG(MGraph &M)int i,j;M.kind=DN;printf(输入顶点数:);scanf(%d,&M.vexnum);printf(输入弧数:);scanf(%d,&M.arcnum);printf(输入顶点:n);for(i=0;iM.vexnum;i+)scanf(%d,&M.vexsi);printf(建立邻接矩阵:n);for(i=0;iM.vexnum;i+)for(j=0;jM.vexnum;j+)scanf(%d,&M.arcsij.adj);printf(输入相应权值:n);for(i=0;iM.vexnum;i+)for(j=0;jM.vexnum;j+)if(M.arcsij.adj)scanf(%d,&M.);typedef struct ArcNodeint adjvex;/该弧所指向的顶点在数组中的下标struct ArcNode *nextarc;InfoType *info;/该弧相关信息的指针ArcNode;typedef struct VNodeVertexType data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志ALGraph;void PrintDN(ALGraph G)int i;ArcNode *p;printf(顶点:n);for(i=0;iG.vexnum;+i)printf(%2d,G.verticesi.data);printf(n弧:n);for(i=0;iadjvex,p-info);p=p-nextarc;printf(n); /forvoid CreateMGtoDN(ALGraph &G,MGraph M)/采用邻接表存储表示,构造有向图G(G.kind=DN)int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;iG.vexnum;+i)/构造表头向量G.verticesi.data=M.vexsi;G.verticesi.firstarc=NULL;/初始化指针for(i=0;iG.vexnum;+i)for(j=0;jadjvex=j;p-nextarc=G.verticesi.firstarc;p-info=M.;G.verticesi.firstarc=p;void CreateDNtoMG(MGraph &M,ALGraph G)int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;iM.vexnum;+i)M.vexsi=G.verticesi.data;for(i=0;iadjvex.adj=1;p=p-nextarc;/whilefor(j=0;jM.vexnum;+j)if(M.arcsij.adj!=1)M.arcsij.adj=0;/forvoid PrintMatrix(MGraph M)int i,j;for(i=0;iM.vexnum;+i)for(j=0;jM.vexn