第7章 图 7.2 图的存贮结构《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第7章 图 7.1 图的基本概念 7.2 图的存贮结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.2 图的存贮结构 在前面几章讨论的数据结构中，除了树以外，都可以有两类不同的存储结构（顺序存储和链式存储〕。由于图的结构比较复杂，任意两个顶点之间都可能存在关系，因此无法以数据元素在存储区中的物理位置来表示元素之间关系，即图没有顺序存储结构，这是和前面所有数据结构所不同的。 另一方面，用多重链表表示图是自然的事，它是一种最简单的链式映象结构，即以一个由一个数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针。但是，由于图中各个结点的度数各不相同，最大度数和最小度数可能相差很多，因此，若按度数最大的顶点设计结点结构，则会浪费很多存储单元。 反之，若按每个顶点自己的度数设计不同的结点结构，则会给操作带来不便，在实际应用中不宜采用这种结构。这其实和树的表示是很类似的。 我们一般采用一些改进的方式来存储图，常用的有邻接矩阵、和邻接表等。不管哪一种方式，它除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息）。存储方法的选择，取决于具体的应用。 下面分别讨论之。 7.2.1 邻接矩阵 1． 图的邻接矩阵表示 在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）∈E(G) 或 〈i,j〉∈E(G)，则矩阵中第i行 第j列元素值为1，否则为0 。 图的邻接矩阵定义为： 1 若（i,j）∈E(G) 或〈i,j〉∈E(G) A[i][j]= 0 其它情形 例如, 对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。 3 1 2 ( a) 无向图 G3 (b) 有向图 G4 图 7 - 8 无向图 G3 及有向图 G4 1 2 4 3 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 ( a) G3 的邻接矩阵 (b) G4 的邻接矩 图 7 - 9 邻接矩阵表示 Question: （1）矩阵对称吗？ （2）如何判断顶点i 和顶点j之间是否有边相连？ （3）如何计算顶点i 的（出/入）度？ （4）如何计算图中边的数目？ Question: （1）矩阵对称吗？ （2）如何判断顶点i 和顶点j之间是否有边相连？ （3）如何计算顶点i 的度？ （4）如何计算图中边的数目？ 2． 从无向图的邻接矩阵可以得出如下结论 （1）矩阵是对称的，可压缩存储（上（下）三角）; （2）第i行或第i 列中1的个数为顶点i 的度; （3）矩阵中1的个数的一半为图中边的数目; （4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。 3． 从有向图的邻接矩阵可以得出如下结论 （1） 矩阵不一定是对称的; （2）第i 行中1的个数为顶点i 的出度;第i列中1的个数为顶点 i的入度; （3） 矩阵中1的个数为图中边的数目; （4） 矩阵中1的个数为图中弧的数目; （5） 很容易判断顶点i 和顶点j 是否有弧相连. 4． 网的邻接矩阵表示 类似地可以定义网的邻接矩阵为 wij 若（i,j）∈E(G) 或〈i,j〉∈E(G) A[i][j]= ∞ 其它情形 网及网的邻接矩阵见图7-10。 ( a) 网 G5 (b) 网 G5 的邻接矩阵示意图 图 7 - 10 网及邻接矩阵示意图 5 3 1 2 4 3 6 1 2 4 8 9 7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 7 4 9 3 7 2 8 4 2 1 9 8 6 3 1 6 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O