图的搜索技巧是整个图算法领域的核心。
图的表示
有两种标准方法：
1.邻接链表
2.邻接矩阵
邻接链表是将一个结点所有相邻的结点放到一个链表中，将所有的链表放在一个数组中，就表示了整个图的结点和边。
邻接矩阵是用一个 n * n 的矩阵（n 为结点的个数）来表示图，其中 A[ij] 表示结点 i 和结点 j 之间是否存在边。
邻接链表扩展方便，占用空间较少，但是查找速度略慢。
广度优先搜索
思路是优先处理离源结点近的结点。
广度优先搜索的过程是这样的：
1.将源结点放入队列
2.开始循环的处理队列，直到队列为空
处理的做法是从队列中出栈一个元素，将元素的相邻结点（还没有被放入过）放入队列中
过程中的细节包括两方面：
1.结点标记颜色（白、灰、黑），来标记是否进入过队列，相邻结点是否都处理完毕
2.结点填写额外的数据，如 d 表示到根结点的距离，π 表示结点的父结点
广度优先搜索的运行时间为 O(V+E)，即邻接链表大小的一个线性函数。
书中给出了一堆引理，定理，证明运行广度优先搜索后，结点的 d
是结点到根结点的最短路径长度，可以由结点的 π 一路向上找出一条最短路径。
广度优先树，是上述算法运行后得到的结果，还可以被称为图 G 的前驱子图。
深度优先搜索
思路是在图中尽量深入的探索，处理完结点的所有出发边后再回来处理该结点。
深度优先搜索形成的前驱子图和广度优先搜索不同，是一个深度优先森林。且算法能够保证所有的深度优先树是不相交的。
深度优先搜索树能够提供关于图结构的重要信息。
深度优先搜索的运行时间为 θ(V+E)
括号化定理、白色路径定理
边可以分为树边、后向边、前向边、横向边，书中解释了如何给边分类
在对无向图的深度优先搜索中，从来不会出现前向边和横向边
拓扑排序
拓扑排序是有向无环图中所有结点的一种线性次序，该次序满足，对图的任意一条边（u, v），u 在次序中处于 v 的前面。
我们可以用拓扑排序来给一堆有相对次序的事件指明一个线性次序，例如穿衣服的次序。
生成拓扑排序的方法是，利用深度优先搜索遍历图，用一个链表来存储拓扑排序的结果，当深度优先搜索算法给某个结点标记 f（完成时间）时，将结点插入到链表的头部。
生成拓扑排序的运行时间为 θ(V+E)
一个有用的引理：引理 22.11，一个有向图是无环的当且仅当对其进行的深度优先搜索不产生后向边。
可以引申出一个面试题：如何确定一个有向图是否有环？
书中还给出了上述生成算法的正确性证明
强连通分量
强连通分量是指，有向图的一个最大（意思是尽可能的大）结点集，其中的任意两个结点都可以互相到达。通俗的说就是有向图中的环组成的结点集，不能连通的环就是一个强连通分量。
一个概念，有向图的转置，是指将图中所有边反向后形成的有向图。图的转置和图有相同的强连通分量
如何计算一个有向图的强连通分量？
1.先对有向图进行深度优先搜索
2.生成图的转置图
3.对转置图进行深度优先搜索，特别的是在主循环中探索结点时，按照第一步中计算的结点完成时间降序进行探索
又是一个概念，分量图，定义为通过收缩所有相邻结点都在同一个强连通分量中的边，就得到了分量图。通俗的说就是将计算完强连通的图进行收缩，规则是每个强连通分量都收缩成一个结点，那么剩下的边就是强连通分量以外的边（连接强连通分量的边，或者说不在环中的边）
分量图是一个有向无环图（因为环都在强连通分量中了）
接下来书中花了一些篇幅证明上述计算强连通分量算法的正确性，引理 22.13、引理22.14、推论 22.15 以及最后的定理 22.16
其中的关键在于理解算法中对转置图的深度优先探索形成的森林为何就是图的强连通分量
网友评论