资源描述:
《实现图的邻接矩阵和邻接表存储.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、实现图的邻接矩阵和邻接表存储1.需求分析对于下图所示的有向图G,编写一个程序完成如下功能:1.建立G的邻接矩阵并输出之2.由G的邻接矩阵产生邻接表并输出之3.再由2的邻接表产生对应的邻接矩阵并输出之2.系统设计1.图的抽象数据类型定义:ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集数据关系R:R={VR}VR={
2、v,w∈V且P(v,w),表示从v到w的弧,谓词P(v,w)定义了弧的意义或信息}基本操作P:CreatGraph(&G,V,VR)初始条件:V是图的顶点集,V
3、R是图中弧的集合操作结果:按V和VR的定义构造图GDestroyGraph(&G)初始条件:图G存在操作结果:销毁图GInsertVex(&G,v)初始条件:图G存在,v和图中顶点有相同特征操作结果:在图G中增添新顶点v……InsertArc(&G,v,w)初始条件:图G存在,v和w是G中两个顶点操作结果:在G中增添弧,若G是无向的则还增添对称弧……DFSTraverse(G,Visit())初始条件:图G存在,Visit是顶点的应用函数操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit
4、一次且仅一次。一旦Visit()失败,则操作失败BFSTraverse(G,Visit())初始条件:图G存在,Visit是顶点的应用函数操作结果:对图进行广度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败}ADTGraph2.主程序的流程:调用CreateMG函数创建邻接矩阵M;调用PrintMatrix函数输出邻接矩阵M调用CreateMGtoDN函数,由邻接矩阵M创建邻接表G调用PrintDN函数输出邻接表G调用CreateDNtoMG函数,由邻接表M创建邻接矩阵N调用P
5、rintMatrix函数输出邻接矩阵N3.函数关系调用图:3.调试分析(1)在MGraph的定义中有枚举类型typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}赋值语句G.kind(int)=M.kind(GraphKind);是正确的,而反过来M.kind=G.kind则是错误的,要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN}会自动赋值DG=0;DN=1,UDG=2,UDN=3;可以自动从GraphKi
6、nd类型转换到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#incl
7、ude#defineMAX_VERTEX_NUM20typedefintVRType;typedefintInfoType;typedefintVertexType;typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型,对无权图用1或0表示是否相邻;//对带权图则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[M
8、AX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;voidCreateMG(MGraph&M){inti,j;M.kind=DN;printf("输入顶点数:");scanf("%d",&M.vexnum);printf("输入弧数:");scanf("%d",
9、&M.arcnum);printf("输入顶点:");for(i=0;i