《数据结构图的存储本讲述》由会员分享，可在线阅读，更多相关《数据结构图的存储本讲述（32页珍藏版）》请在金锄头文库上搜索。
1、第七章 图的存储 本讲内容 1.图的邻接矩阵 2.图的邻接表 3.图的十字链表 4.图的邻接多重表 由于图的结构比较复杂，任意两个顶点之间都有 可能存在联系，因此无法以数据元素在存储区中 的物理位置来表示元素之间的关系。 图没有顺序存储结构，但可以借助于二维数组 来表示元素之间的关系，即邻接矩阵表示法。 另一方面，由于图的任意两个顶点间都可能存 在关系，因此，用链式存储表示图是很自然的 事，图的链式存储有多种，如邻接表、逆邻接 表、十字链表和邻接多重表，应该根据实际需 要的不同选择不同的存储结构。 图的邻接矩阵 矩阵的元素为Aij= 0 或(i,j)VR 1 或(i,j)VR 定义 图的邻接矩
2、阵是表示顶点之间相邻关系的矩 阵。设G(V,VR)是具有n个顶点的图，用邻接 矩阵表示法表示图，除了用二维数组存储图 中各顶点间的关系VR外，还需要用一维数组 存储图中的顶点V。 图的邻接矩阵 举例 B A C D F E 010010 100011 000101 001001 110000 011100 无向图的邻接矩阵一定是对称矩阵，在具 体存放时只需存放上（下）三角阵的元素 。 第i 行（列）非0元素的个数是第i 个顶点 的度。 有向图的邻接矩阵 为非对称矩阵 A BE CD 第i行（列）非0元素 的个数是第i个顶点 的出度（入度）。 邻接矩阵的C描述 const int MAX_VER
3、TEX = 最大顶点个数; typedef char VertexType ; typedef int ArcType ; typedef struct Graph /图的定义 VertexType vexsMAX_VERTEX; /顶点 ArcType arcsMAX_VERTEXMAX_VERTEX; /弧(邻接矩 阵) int vexnum, arcnum; /顶点数，弧数 Graph; 图的邻接矩阵 通过前面给出的图的邻接矩阵的C描述知： 对于图来说，有边（弧）时邻接矩阵arcs中的 元素为1，否则为0。 对于网来说，有边（弧）时邻接矩阵arcs中的 元素为其上的权值，否则为。其中，
4、表示 计算机允许的、大于所有边上权值的数。 邻接矩阵的存储空间个数为n2，与边数无关。 采用邻接矩阵创建无向网 已知一个图的点和边，使用邻接矩阵表示法来创 建此图的方法比较简单。下面以一个无向网为例 来说明创建图的算法。 步骤1：输入总顶点数和总边数。 步骤2：依次输入点的信息存入顶点表中。 步骤3：初始化邻接矩阵，使每个权值初始化为极大值 。 步骤4：构造邻接矩阵。依次输入每条边依附的顶点和 其权值，确定两个顶点在图中的位置后，使相应边赋 予相应的权值，同时使其对称边赋予相同的权值。 void CreateUDN(Graph scanf(G.arcnum); for (i=0;iG.vexn
5、um;i+) /输入顶点的信息 scanf (G.vexsi); for (i=0;iG.vexnum;i+) /初始化邻接矩阵，边上 的权值为极大值MaxInt for (j=0;jG.vexnum;j+) G.arcsij=MaxInt;/ for (k =0 ;kG.arcnum;k+) /构造邻接矩阵 scanf (v1);scanf (v2);scanf (w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij=w; G.arcsji=G.arcsij; 算法分析 算法时间复杂度为O(n2)。 若要建立无向图，只需对上述算法做两处小小 的
6、改动：一是初始化邻接矩阵时，将边的权值 均初始化为0；二是构造邻接矩阵时，将权值w 改为常量1即可。同样，将该算法稍作修改即 可建立一个有向网或有向图。 邻接矩阵表示法的优缺点 优点1.便于判断两个顶点之间是否有边，即根据 Aij来判断。 2.便于计算各个顶点的度。 缺点 1.不便于增加和删除顶点。 2.不便于统计边的数目，时间复杂度为O(n2)。 3.空间复杂度高。如果是有向图，n个顶点需要n2个单元 存储边。如果是有向图，邻接矩阵是对称的，所以规模 较大的邻接矩阵可以采用压缩存储的方法，仅存储下三 角（或上三角）的元素，需要n(n-1)/2个单元即可。无论 以何种方式存储，邻接矩阵的空间复
7、杂度为O(n2) ，对于 稀疏矩阵来说尤其浪费空间。故，适合稠密图。 图的邻接表 定义 图的链式存储结构。在邻接表中，对图中每个顶点vi 建立一个单链表，把与vi相邻接的顶点放在这个链表 中。邻接表中每个单链表的第一个结点存放有关顶点 的信息，把这一结点看成链表的表头，其余结点存放 有关边的信息。 对于图中每条弧均依附于两个结点，因此链表 中的结点就是具有相同弧尾的弧结点。 在实际存储时，图中顶点的邻接点链成链表， 表结点中存储邻接点的存储位置。而在存储图 中顶点时，除了本身的数据信息外，还要存储 指示其第一个邻接点的指针。 0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5
8、4 E 0 1 5 F 1 2 3 B A C D FE 无向图中n个顶点 ，e条边，则邻接 表有n个头结点和 2e个表结点。 举例 1 4 2 3 0 1 2 0 1 2 3 4 A B C D E 有向图的邻接表 A BE CD 可见，在有向图的 邻接表中不易找到 指向该顶点的弧。 A BE CD 有向图的逆邻接表 A B C D E 30 3 4 2 0 0 1 2 3 4 在有向图的逆邻接表中 ，对每个顶点，链接的 是指向该顶点的弧。 邻接表的C描述 adjvex nextarc 弧的结点结构 typedef struct ArcNode int adjvex; / 邻接点的位置 st
9、ruct ArcNode *nextarc; / 下一个邻接点 OtherInfo info ;/和边相关的信息，如权值 ArcNode; info data firstarc顶点的结点结构 typedef struct VexNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一个邻接点 VexNode; 图的结构定义 const intMAX_VERTEX = 最大顶点个数 typedef struct Graph VexNode vexsMAX_VERTEX;/顶点向量 int vexnum, arcnum; /顶点和弧的个数 Gra
10、ph; 采用邻接表创建无向图 基于上述的邻接表表示法，要创建一个图则需要创 建其相应的顶点表和边表。下面以一个无向图为例 来说明采用邻接表表示法创建无向图的算法。 步骤1：输入总顶点数和总边数。 步骤2：依次输入点的信息存入顶点表中，使每个表头 结点的指针域初始化为NULL。 步骤3：创建邻接表。依次输入每条边依附的两个顶点 ，确定这两个顶点的序号i和j后，将此边结点分别插入 vi和vj对应的两个边链表的头部。 void CreateUDG(Graph scanf(G.arcnum); for (i=0;inextarc=G.vexsi.firstarc; G.vexsi.firstarc=p
11、1; /插入到顶点vj的边表头部 p2=(ArcNode *)malloc(sizeof(ArcNode); p2-adjvex=i; p2-nextarc=G.vexsj.firstarc; G.vexsj.firstarc=p2; 算法分析 算法时间复杂度为O(n+e)。 建立有向图的邻接表与此类似，只是更加简单 ，每读入一个顶点对序号，仅需生成一个 邻接点序号为j的边表结点，并将其插入到vi的 边链表头部即可。若要创建网的邻接表，可以 将边的权值存储到info域中。 值得注意的是，一个图的邻接矩阵表示是唯一的，但是其邻接表 表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取 决于建
12、立邻接表的算法，以及边的输入次序。 邻接表表示法的优缺点 优点 1.便于增加和删除顶点。 2.便于统计边的数目，按顶点表顺序扫描所有 边表可得到边的数目，时间复杂度为O(n+e)。 缺点 1.不便于判断顶点之间是否有边，要判定vi和 vj之间是否有边，就需要扫描第i个边表，最坏 情况下要耗费O(n)时间。 2.不便于计算有向图各个顶点的度。 3.空间效率高，空间复杂度为O(n+e)。适合表 示稀疏图。 弧的结点结构 弧尾顶点位置 弧头顶点位置 指向下一个 有相同弧尾 的弧结点 指向下一个 有相同弧头 的弧结点 有向图的十字链表 typedef struct ArcNode /弧结点 int t
13、ailvex, headvex; /弧尾和弧头顶点的位置 struct ArcNode *nexttail, *nexthead; /指向下一 个同弧尾和同弧头的弧结点 ArcNode; 顶点的结点结构 顶点信息 指向该顶点的 第一条入弧 指向该顶点的 第一条出弧 typedef struct VexNode /顶点结点 VertexType data; /顶点信息 ArcNode *firstin, *firstout; /指向第一条 入弧和第一条出弧 VexNode; 有向图的结构定义（十字链表） const intMAX_VERTEX = 最大顶点个数 typedef struct Gr
14、aph VexNode vexsMAX_VERTEX; /顶点向量 int vexnum, arcnum; /有向图的顶点和弧的个数 Graph; 有向图的十字链表相当于邻接表和逆邻接表 的结合。 AB C D E A B C D E / 0 1 2 3 4 / 3 0 / 4 0 / 0 1/ 0 2 / 1 2 / 1 3 / 2 3 / / 4 3 画图技巧：把弧结点按行排整齐， 然后画链表。同弧尾的弧组成链表 ，同弧头的弧组成链表。 无向图的邻接多重表 边的结点结构 边顶点1位置 边顶点2位置 指向下一个 依附顶点1的 边结点 指向下一个依 附顶点2的边 结点 typedef stru
15、ct EdgeNode /边结点 VisitIf mark; /访问标记 int vexi, vexj;/边的两个顶点 struct EdgeNode *nexti, *nextj; /两个顶点所依附 的下一条边 EdgeNode; 顶点的结点结构 顶点信息 指向依附该顶 点的第一条边 typedef struct VexNode / 顶点结点 VertexType data; /顶点信息 EdgeNode *firstedge; /指向依附该顶点的 第一条边 VexNode; 无向图的结构定义（邻接多重表） const intMAX_VERTEX = 最大顶点个数 typedef struct Graph / 图 VexNode
