【数据结构（邓俊辉）学习笔记】图01——图的表示与实现_邓俊辉数据结构

1. 概述

1.1 邻接 + 关联

相对于此前的线性以及半线性结构，图结构对其中元素的限定更少，因此反过来，它描述应用问题的能力也就更强。

如上图所示，就数学意义而言的图，包含两个要素，首先是顶点集V——也就是任意一组元素，这里只考虑有限集，所以不妨将这个集合的规模记作n，在这n个顶点之间可能存在某种两两关系，如果的确存在这样的关系，我们就在对应的顶点之间以连边表示，存在对应关系就连边，存在对应关系就连边…，所有这些连边构成图的第二个要素，形象称为边集，同样地通常用e来表示边的总数。

彼此之间存在这种关系并且因此也存在连边的任何两个点都称作是彼此邻接的，这样的关系，也称作邻接关系。而参与定义这种邻接关系的每个顶点与这个邻接关系之间的关系也称作关联关系。

邻接关系和关联关系两者之间区别？形象地说，所谓的邻接关系就是顶点与顶点之间的关系——v ~ v。关联关系是描述顶点以及与它相关的某条边之间的关系——v ~ e。

可以看到图的这种邻接关系的定义是可以任意的，此前所学的几种数据结构因此也都可以视作是它的特例。
  ~  
比如在此前的向量和列表等线性序列中，只有互为前驱与后继的元素之间才能够定义邻接关系。因此整体而言，序列结构应该是图的一种特例。
  ~  
树结构也只能在父节点与子节点之间才能够定义邻接关系，因此就整体而言，树结构也可以视作图的一种特例。
  ~  
也就是说图更为一般化，其中的任何两个节点之间，都允许存在这样的一个邻接关系。
  ~  
需要排除的特例，也就是是否允许同一个节点与自身构成一个邻接关系？在图论中，的确有时需要讨论这类图，为了简化起见，不妨将此类称作自环的边忽略掉。

1.2 无向 + 有向

根据所允许的边不同，我们还可以对图进行进一步的类型划分——有向 + 无向。

注意力主要集中在有向图上，原因很简单，因为通过有向图完全可以表示并且实现无向图以及混合图。这里的技巧是可以将任何一条无向边转化为彼此对称的一对有向边。因此接下来图的实现以及图的算法都是围绕有向图来展开。

1.3 路径 + 环路

二叉树中所学过的路径以及环路等概念，也自然可以推广至一般性的图。

所谓的路径也就是由一系列的顶点按照依次邻接的关系构成的一个序列。

不含重复节点的路径称作简单路径，否则化则为一般性路径。

起点与终点重合的路径称作环路。同样环路也有简单与不简单之分，具体来说就是路径中是否包含重复的节点。

如果在一个有向图中不包含任何环路，称为有向无环图。

在所有的环路中，有一种环路是非常有名，而且也非常有意思的，也就是它覆盖了图中所有的边，各边恰好出现一次的环路，称作欧拉环路。 还有一种环路，它经过每一个顶点一次，且各顶点恰好出现一次的环路，称作哈密尔顿环路。

2. 邻接矩阵

2.1 接口

从数学角度给出了图的定义以及相关的一些重要术语，尽管图论中设计的概念和术语还远远不止于此，但就目前学习的内容看大致足够。因此接下来讨论的是如何在计算机中以数据结构的形式表示并且实现图。

首先不妨从抽象数据类型的角度对图这种数据结构的接口以及操作规范进行一个统一的定义。利用C++语言模板类机制图结构标准接口可以大致定义如下：

通过模板参数可以任意指定顶点以及边的基本类型，而对外的操作接口无非三类，也就是针对于顶点、边以及针对相关的算法，因为这些接口数量较多，在此暂且不予列出，在后面会陆续地介绍它。

然而无论如何具体实现，这些接口在形式以及语义上都必须做到统一，后面会针对这种形式以及语义的统一性逐一校对。

以内部公用的reset（）接口为例，尽管现在还不清楚Graph模板类的具体实现方法，但是其中已经允许对顶点以及边做一些已经封装好的操作，比如取顶点的状态信息status（）、父节点信息parent（）、以及优先级数priority（）。还有顶点的时间标签dTime（），再如判断两点之间是否存在一条连边exists（），以及设置或查询边的状态status（）。

那么所有这些图结构的标准接口应当如何实现呢？首先要解决的问题是如何表示一个图。

2.2 邻接矩阵 + 关联矩阵

实际上图论已经提供了现成的图表示方法，其中最典型的就是邻接矩阵以及关联矩阵。

首先看下邻接矩阵，所谓邻接矩阵就是用以描述顶点之间相互邻接关系的一种形式。如下图

具体来说，这是一个方阵，如果图中包含n个顶点，这个矩阵就是n*n。于是矩阵中的任何一个单元，比如对应于第i行第j列的那个单元，都表示顶点i与顶点j之间是否存在一条边，也就是说它们是否关联，如果是可以简明地将这个元素取作1，反过来如果是否取作0。
  ~  
不难看出，如果是无向图，那么它对应的邻接矩阵就应该是对称的，也就是说第i行第j列的元素必然与第j行第i列的元素雷同。
  ~  
特别地，在该矩阵对角线上的元素都对应于此前所说的自环。之前做过交代，不考虑此类的边。
  ~  
当然，如果考察的是所谓带权图，其中的每一条边都拥有某一个称为权重的指标，那么只需对这样的形式的矩阵略加扩充。具体来说，如果在顶点i与j之间存在一条边，而且该边的权重是w，就不妨将这个权重存入矩阵中对应的单元。可以看到，如果说无权图可以简单地用01的比特矩阵来表示，对于带权图，只需将每个单元的类型从单个的比特扩展为对应的一个整数或者浮点数即可。

再看所谓的关联矩阵，如下图

如果当前的图有n个节点，那么这个矩阵就有n行，如果图中总共包含e条边，那么这个矩阵就对应的有e列，n行e列。相应地矩阵中的任何一个单元表示的也就是对应的顶点与对应的边之间的关系。
  ~  
类似地，如果存在关联关系，这个单元就记作1，否则就记作0。不难看出对于这个矩阵中的任何一列而言，应该恰好只有两个单元的数组为1，而其余的都是0。

这里主要介绍邻接矩阵，尽管在有些算法中，关联矩阵也同样可以大显身手。

2.3 实例

看下邻接矩阵的几个实例，如下图：

首先看下无向图（a）

这里采用个习惯，将矩阵中没有明确标出，所谓的默认值，都记在这个矩阵的左上角，这里的默认值为0。这样可以使我们更加清晰准确地把握邻接矩阵。
可以看到无向图的邻接矩阵的确是对称阵，因此就存储效率而言，存在一定的冗余性redundancy。每一条边都被重复保持两份。

图（b）和图（c）见上图。

2.4 顶点和边

• 下面给出图顶点类的一种实现方式，如下图
  
  为了简明起见，这里没有对Vertex类没有做严格的封装——struct。

首先需要data域记录顶点的自身信息，其次当前顶点与其他的多少个顶点相互关联可以用它的入度inDegree以及出度outDegree分别指示。
  ~  
status、dTime、fTime、parent、priority信息都是服务之后的图遍历算法。

1. 在整个遍历过程中，图中每个节点在任何时候都处于特定的状态，这种状态总共可以枚举的三种UNDISCOVERED、DISCOVERED、VISITED。可以看到，在被创建时，每一个顶点都初始地被置成所谓的UNDISCOVERED状态。
2. 此外，我们还需要两个时间标签，分别记录顶点被发现以及访问完毕的时刻。
3. 而在遍历所生成的遍历树中，当前节点的父节点是谁，则是由parent记录。
4. 而在基于优先级的遍历算法中，还需要为每个顶点维护一个优先级数。

这些信息的具体含义，我们在接下来的遍历算法中将会详细介绍。

因此当一个顶点被创建时，自然地也需要对以上各项进行设置，也就是把数据域设置成对应的指定与域，而入度以及出度都被初始化为0，其余各项也是如此。

• 再给出边类型的一种实现方式，如下图
  
  同样地出于简捷的考虑，这里对于Edge类也省去了严格的封装——struct。

1. 首先需要有一个域来记录自己所携带的信息，
2. 其次，对于带权网络还需记录边的权重。
3. 与顶点类似地在经过遍历之后，所有的边都会被归入某一种类型，可以看到上述一共枚举五种类型，它们的具体含义将在后面介绍遍历算法时逐一介绍。

如此为了创建一条边，也是需相应地对其中的各项进行初始化设置即可。

2.5 邻接矩阵

基于邻接矩阵实现图结构的一种可行方式。

作为一个类GraphMatrix也是派生于此前所定义的Graph结构。

首先需要将顶点集以及边集首先兑现为具体的数据结构，此前所学过的向量vector。所谓的顶点集无非就是由一组顶点所构成的向量，可以称作a vector of vertex。如上图最左侧V[]，它的长度恰好等于顶点的规模，也就是通常记作的n。
  ~  
所谓的边集在这里定义成是由一组边所构成的向量，进而由这一组向量所构成的向量，也就是a vector of vectors of
edges，可以通过上图理解这种实现方式。具体来说就是将一系列边构成若干个向量，同样，每个顶点最多可能与n个顶点相关联，所以每一个向量的长度也是n，而总共会有n个向量。所有这些向量再和在一起，构成一个向量E[]，所以可以认为是二维向量。这个恰好就是之前所构思的邻接矩阵。

需要强调的是得益于此前对向量重载的方括号操作符[]，在这只需用E[i][j]即可便捷指代在顶点 i 与 j 之间 潜在的那样一条边，既可以读出这条边信息，也可以反过来修改其中的某条信息。

2.6 顶点静态操作

按照这种实现方式，可以简明实现顶点操作中的大部分基本操作。如下图

直接返回顶点所对应的数据、入度、出度、状态、时间标签、父节点、优先级数。

当然并非所有的顶点操作都能如此直截了当地一蹴而就地实现。例如在图的遍历过程中需要反复地使用这样一个接口

也就是说站在当前顶点 i 的位置，需要逐一地罗列也就是枚举出与之邻接地所有顶点，我们称这些顶点是当前顶点的邻居。
为此首先需要实现一个名为nextNbr的接口，它的功能语义是如果我们已经枚举到顶点i的编号为 j 的这个邻居，那么它将返回接下来的下一个邻居。

与顶点 i 潜在的可以相邻的点无非就是它在邻接矩阵中所对应的那一行，这个行向量的取值或0或1，而所有那些数值为1的单元才各自对应于与 i 邻接的一个顶点。如下图

• 如果现在已经枚举到编号为 j 的这个邻居，如何找到下一个有效的邻居？

不难理解这个算法为什么要从 j 开始不断地通过减减逆向地向前进行搜索。每抵达下一个潜在的邻居，都要通过exists接口判断对应的这条边是否存在。只要不存在就继续通过 j 减减指向下一个潜在邻居，直到最终发现一个有效的邻居，至此只需将新发现的这个邻居返回即可。
  ~  
接下来，如果再次调用nextNbr接口自然也就返回下一个邻居，以及再下一个有效邻居等。当试图越过这个向量的左边界0，也就是试图抵达-1的时候，将终止这样一个搜索的过程。这也是为什么在这个短路求值的逻辑表达式中首先需要检查 j 是否已经越界。

• 那么第一个有效邻居又该如何确定呢？
  

其实 firstNbr() 也是调用了nextNbr()而已，不同在于，它将顶点n作为上一个有效邻居，尽管编号为n的顶点压根不存在，依然不妨将它视作假想的哨兵，而且等效认为它会和包括 i 在内的任何顶点都相邻。从而简明而有效地启动整个搜索和枚举过程。

• 整个这样从第一个有效的邻居一直枚举到最终的一个的过程，累计需要花费多少时间呢？

尽管各自nextNbr所对应while循环的长度不仅相同，但累计而言其长度不过是整个行向量的长度，这个长度恰好就是n。因此整个算法所需要的运行时间累计不过是线性。当然若对这个效率不怎么满意，可以借助稍后介绍的邻接表结构进行改进。如此改进后，整个过程累计所需要的时间将线性正比于当前顶点的出度O（1 + outDegree（i））。

2.7 边操作

同样的利用邻接矩阵，可以便捷地实现很多边地操作。

可以非常便捷地判定在两个顶点之间是否的确连有一条边

既然在邻接矩阵中每一对顶点之间潜在的那条边都在矩阵中对应于一个单元，因此只需判断这个单元是否有效即可。具体来说，只要所给的顶点 i 以及 j 是合法的，那么只需取出邻接矩阵中对应的项进行一次比对，即可做出正确的判断。
  ~  
一旦判断出某条边的确存在，只需取出这个单元数据域即可返回这条边所对应的信息。类似的，它对应的其他信息也可以直接返回。

• 那么如何在一幅图中插入一条边呢？

依然需要围绕邻接矩阵进行操作，假设需要在顶点 i 与顶点 j 之间连接一条有向边，假设这条边尚不存在，于是只需要将待插入那条边信息，比如它的权重等等，封装为一个具体的边记录，然后将这个新的边记录地址，存入于邻接矩阵中对应的那个单元。于是反过来也可以说，这个单元将指向这个新的边记录。具体代码如下

1. 首先需要经过一次检验，以确定这条边还不存在。
2. 于是可以创建这样一个边的记录，并且将这个新记录的地址转交给邻接矩阵中对应的单元，这样就完成这条边的物理引入。
3. 那么从逻辑上这幅图还要做相关信息的更新，包括整体边数加 1 ，此外，作为这条边的尾部节点 i 的出度需要递增，而作为这条边的头部节点 j 的入度需要递增。

• 相应地如何删除一条边？

只需将刚刚插入过程跌倒过来，假设从顶点 i 通往顶点 j 之间的确存在一条边，因此在邻接矩阵中对应那项便非空，而且这项将指向一个对应的边记录，因此为了删除这条边，只需将这条边对应的记录释放，并且归还给系统，然后令在邻接矩阵中对应于这一项的引用指向空。代码如下

假设经过对比已经确认这条边是存在的，那么通过矩阵中对应的这项引用找到这个记录并且将它释放掉，随后将这个引用置为空，也就是从物理上完成了这条边的摘除。再对图相关统计信息进行更新维护。

2.7 顶点动态操作

• 如何在图中引入一个新的顶点？

相对于边的操作，顶点的操作要更为复杂，原因在于在此前的边操作中整个矩阵的规模并不会发生变化，而顶点的插入以及删除就不是这样了。

假设此前邻接矩阵所实现的图如下左图，为了在其中引入一个新的顶点，整个过程以及最终的结果可以由右图表示。

1. 首先需要将邻接矩阵中以后的各行分别向后扩展一个单元，即增加一列。
2. 针对新引入顶点需在邻接矩阵中增加对应的一行。
3. 作为二级边表，还需在第一级的边表中增加一个相应单元，用来指示或记录新引入的这样一个行向量。
4. 对应于这个新引入的顶点，需要在顶点向量中加入一个新的对应元素。

为了插入一个新的顶点，步骤如下

1. 首先为每一个行向量分别增加一个单元，也就是在每一个行向量的尾部引入一个初始为空的记录，所以总体相当于各自延长一个单位。n 递增。
2. 接下来需要生成一个行向量，行向量中元素都是一系列的边记录，它的总数为n，而且其中所有边引用都初始化为空。

注意，在第一步延长了每一个已有的行向量之后便随手将n递增过，因此这里所生成的新的行向量实际长度要在原来基础上增加一个单位。总而言之，能够生成一个长度为新的n的行向量。

3. 接下来，取出这个行向量的地址，并且将它存入第一级的边表中，这一步是由一级边表中调用insert命令来完成的。整个一系列动作串联起来，完成相当于第二步和第三步。

最后，创建一个对应的顶点记录，并且存入于整个的顶点向量，如此完成一个新顶点的引入。尽管这个顶点与其他顶点之间还没有任何实质的连边。

• 如何实现顶点删除？
  
  整个过程是顶点插入过程的逆过程。

2.8 综合评价

对邻接矩阵表示法作概况和总结

邻接举证表示法的优点如上图，但缺点也是显而易见的，最主要的是空间性能。

无论图中实际边数是多少，这种表示法所消耗空间量总是固定为最大值n平方，而与实际边数无关。当然，如果实际边数能够达到这种规模，那自不在话下，如果这个数要远远地小于n平方呢？就意味着有巨大的浪费。

• 实际应用中情况如何呢？
  边数往往不会达到这么多，而是会远远小于最大的n平方这样一个界。

平面图也就是可以嵌入平面的图，简单地说所谓嵌入于平面，也就是将图绘制在一个平面上，比如一张足够大的纸上。当然这里有个条件，不相邻的边不能相交。

实际上平面图所具有的本质特征可以由欧拉公式来表示

对于任何一个平面图其中（顶点v 边总数e 区域面片总数f 以及连通域总数c ）必然满足上述恒等式。从欧拉公式出发可以得出这样结论：对平面图而言，从渐进意义上讲边的总数不可能超过顶点总数。

如此说来，对于这类图我们预备了n平方空间，但实际上有效的不过是O（n）量级比例。大致来说整个空间利用率为1/n。随着n的增加这样的比例会很快趋近于0，也就意味着极其低下的空间利用率。