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

1、实现图的邻接矩阵和邻接表存储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存在操作结果

2、：销毁图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是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数vis

3、it一次且仅一次。一旦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);

4、是正确的，而反过来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）输入顶点

5、数和弧数；（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表示是否相邻； /对带权图则为权值类型i

6、nfotype *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.

7、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;/该弧所指向的顶点在数组中的下标struc

8、t 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;

9、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.vert

10、icesi.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.