清华大学-计算机系912考研-初试-复试-知识点整理.zip

知识总结：图 ============ ## 知识脉络 本章讨论图结构以及与之相关的算法。相对于前面的序列以及树，图是一种更加一般的数据结构，借助图理论上可以表示世界上所有事物以及它们之间的联系。一般地，单向链表是入度和出度均为1的图，二叉树是入度为1而出度不超过2的图。仿照前面对树的研究思路，对图的研究主要是将图转化为一棵与之对应的树，从而利用对树的分析技巧来解决问题。 可以从遍历的角度将图转化为树，这里对应了两种遍历策略，即广度优先搜索和深度优先搜索。广度优先搜索总是优先访问更早访问的节点的邻居，而深度优先搜索却是优先访问最后访问节点的邻居。为了尽可能保存图结构中蕴含的信息，在遍历过程中要进行大量的标注工作，包括各个节点的发现时间`dtime`与访问时间`ftime`，各条边的类型（树边，跨边，前向边，后向边）以及父亲节点等。对于两种遍历何时应该标注何种情况，需要有清晰的理解才行，例如对于深度优先搜索，关键在于对`括号引理`的理解。 基于两种搜索策略可以导出大量和图相关的算法，比如基于`dfs`策略的`拓扑排序`问题和`双连通域分解`问题。对于`拓扑排序`问题，可以证明，所有的有向无环图`DAG`都是存在拓扑排序序列的。一般地，构造拓扑排序序列的算法有两种思路，即`零入度`算法与`零出度`算法，`零入度`算法是基于`拓扑排序`的定义，而`零出度`算法则是基于`dfs`访问次序与`拓扑排序`次序的关系。两种算法都可以达到`O(n + e)`的时间复杂度。 `双连通域分解`的关键在于`关节点`以及`双连通域`的定义，即对于任意节点`C`，如果将它移除后，将导致`C`的一棵真子树与它的真祖先无法连通，则`C`必是关节点。基于此，可以构造出`双连通域分解`的算法，即对图进行一次深度优先搜索，在对每一个节点访问过程中，动态地记录它的最高可达祖先(hca, Highest Connected Ancestor)，如果某一节点的孩子节点的`hca`是当前节点的真祖先，则当前节点必不是关节点，反之当前节点必是关节点。 `最小支撑树`问题也是图论中的经典问题，构造`最小支撑树`有两种经典算法，即`Prim`算法与`Kruscal`算法。对于`Prim`算法，关键在于理解以下事实，即`最小支撑树`总是采用两割之间的最短路径。在所有路径权值都不相等的图中，基于该事实已经可以构建出一种`最小支撑树`的生成算法，并且它的正确性是容易证明的。但是在权值可以相等的图中，最小支撑树往往并不唯一，此时可以注意到以下事实，即 + 任意一棵极小支撑树中的每一边，都是某一割的极短跨越边。 + 每一割的极短跨越边，都会被某一棵极小支撑树采用。 + 对于某棵支撑树，如果它的每一边都是某割的极短跨越边，该树也未必就是一棵极小支撑树。 此时，`Prim`算法的正确性就显得有点似是而非。好在可以证明，`Prim`算法每一步生成的树`T_k`，都是某一棵极小支撑树的子树，从而证明得到`Prim`算法在允许多边等权时仍然是正确的。 `Kruscal`算法也是基于贪心迭代策略的`最小生成树`的生成算法，在它的执行过程中主要涉及两个基本操作，即判断一条边连接的两个节点是否属于同一棵树，以及若不属于，则将这两棵树合并，因此利用一个并查集(`Union and Find Set`)可以方便地实现这些基本操作。`Kruscal`算法正确的证明也是类似于`Prim`正确性的证明。 为了规避`最小支撑树`的歧义性，可以采用一些其他策略，比如对整数权重的网络，可以人为引入一些微小的扰动，使得各边的权重不再相同。此外，还可以采用`合成数`策略来消除图算法的歧义性。 此外，在实际应用中往往还会遇到最短路径的问题。对于单源最短路径利用`Dijkstra`算法 可以方便地解决，`Dijkstra`算法也是基于贪心的策略，总是将当前到源点路径最短的节点归入到最短路径树当中，随后再基于该节点对其他节点的路径距离进行更新，容易证明该算法的正确性。然而，`Dijkstra`算法却不能适用于存在负权重边的图，此时需要对`Dijkstra`算法做出一些修改，或者不妨使用`Floyd`算法。 `Floyd`算法可以求到所有节点之间的最短路径，它是基于这样的思想，即任意两个节点之间最短路径，只有可能是直接连接的路径，或者经过若干个中间节点的一条路径。因此，在`Floyd`算法中，依次将每个节点作为中间节点，来更新所有其他节点之间的路径。`Floyd`算法在负权重边的情况下仍然可以正确工作，但是对负权重环路却无能为力，实际上，存在负权重回路时，图中不存在最短路径。 上面提到的各种算法，无论是`bfs`，`dfs`，`Prim`算法还是`Dijkstra`算法，都具有一些共同点，即总是根据一定的优先级，对下一个要访问的节点进行选择。因此可以将这几种算法，统一归入到优先级搜索(`PFS`, Priority First Search)的框架当中。这样可以发现一些它们内在的联系，比如在优先级搜索的框架下，`bfs`实际上是`Dijkstra`算法在各边等权重的情况下的退化情况。 ## 图的一些基本概念与术语 > 什么是图？为什么要有图这种数据结构？ 图是一种更一般的数据结构，根据马克思辩证唯物主义中[万物的普遍联系与永恒发展]的观点，图正是表示了一个集合中所有元素之间相互联系关系的一种数据结构，因此更具有普遍性，理论上可以描述宇宙中的所有关联关系。 从结构上来看，图相对于前面介绍过的`Vector`，或者`Tree`，也具有更一般的结构性质。`Vector`是一个线性结构，在`Vector`中，只能描述一个元素与它的前驱/后继之间的关联关系；`Tree`是一个半线性结构，可以描述一个元素与它的父结点以及若干子结点之间的关系，相对于`Vector`更加普遍，而`Tree`的退化形式即成为了一个`List`，从而证明了这里的观点。图是一个非线性结构，可以表示一个结点与集合中所有元素的关联关系，采用类比的方法，我们可以归纳出研究图的一般方法--将图转化为我们熟悉的树，从而借用树的分析技巧来解决图的问题。 > 图的分类。 图的分类比较复杂，这里只讨论几个容易混淆的概念。 简单的概念，一般是表示不含有环路。 + 简单图：不含有自环的图。 + 简单通路：沿途顶点互异的通路。 + 简单环路：除起点和终点外沿途所有顶点均互异的环路。 + 欧拉环路：经过图中各边一次且恰好一次的环路。比如说一笔画问题。 + 哈密尔顿环路：经过图中各顶点一次且恰好一次的环路。 ## 图的表示 由于图是表示一个集合中所有元素相互之间的关联关系的数据结构，因此表达这里的关联关系是表示图的重点。元素之间的关联关系我们又称之为邻接关系，对应有邻接矩阵，邻接表两种表示方法。除此以外，图中还存在顶点和边之间的关系，这种关系我们称之为关联关系，对应有关联矩阵表示法。 > 邻接矩阵表示法。 邻接矩阵是表示图中的邻接关系。简单说来，就是引入一个$n\times n$的矩阵，矩阵中的每个元素代表相应的两个顶点之间是否有邻接关系，或者这种邻接关系的强度。 > 邻接表表示法。 上面的邻接矩阵表示法其实具有比较大的冗余，因为它需要$O(n^2)$的空间，�