图的几种存储结构比较分析教材.ppt

图的几种存储结构比较研究班级:软件工程六班姓名:马盛国学号:,(vi,vj)和(vj,vi)表示同一条边,因此,在邻接矩阵中aij=aji。对有向图,弧<vi,vj>和<vj,vi>表示方向不同的两条弧,所以aij≠aji。在图的顶点确定的情况下,其邻接矩阵表示是唯一的。邻接矩阵(AdjacencyMatrix)是表示图中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵An×n:无向图的邻接矩阵是以主对角线对称的,第i行(列)1的个数就是顶点vi的度。即上图中:D(1)=2 D(2)=3 D(3)=2 D(4)=3 D(5)=2有向图的邻接矩阵可能是不对称的。在有向图中:▲第i行中1的个数就是顶点i的出度。▲第j列中1的个数就是顶点j的入度。▲有向图中各顶点的入度之和等于出度之和。ID(vi)=OD(vi)=上图中:D(1)=OD(1)+ID(1)=3D(2)=OD(2)+ID(2)=3 D(3)=OD(3)+ID(3)=3D(4)=OD(4)+ID(4)=3■带权值的邻接矩阵总结:(1)因为不考虑顶点到自身的边或弧,所以邻接矩阵的对角线必为0;(2)无向图的邻接矩阵为对称矩阵,所以可用特殊矩阵压缩方式存储;(3)无向图的顶点的度为邻接矩阵中该顶点对应的行(列)中非零元个数;(5)有向图的邻接矩阵不一定为对称矩阵;(6)有向图中顶点的入度为该顶点对应列中非零元的个数,出度为该顶点对应行中为非零元的个数。邻接矩阵表示法中图的类型定义:#defineMAXSIZE100/*图的顶点个数*/typedefstruc{intno;//顶点编号infotypeinfo;//顶点其它信息}vertextype;//顶点类型typedefstruct//图的定义{vertextypevexs[MAXSIZE];/*顶点信息表*/intedges[MAXSIZE][MAXSIZE];/*邻接矩阵*/intn;/*顶点数*/inte;/*边数*/}mgraph;21435无向图t->n=5t->e=6mgraph*t;BADCE有向图mgraph*t;t->n=5t->e=6