这一周的内容主要介绍了图算法。

课程地址：https://www.coursera.org/specializations/algorithms

Course 2 Week 1

讨论之前，先规定记号的表示方法：令$n=$图中节点的个数，$m=$图中边的个数。

先来看最基本的图搜索算法：

这个图所搜算法基本上是对所有图算法的概括，下面介绍更具体的图算法。

BFS

Breadth-First Search (BFS)有几个特点：

  • 分层探索节点
  • 可以计算最短路径
  • 计算无向图的connected components

接下来来看具体算法：

Algorithm

来看一些BFS的特点。

Basic BFS Properties

Application: Shortest Paths

BFS的一个应用是计算最短路径，只要在运行BFS算法同时计算层数即可。

Application: Undirected Connectivity

计算connected components只要运行多次BFS即可。

DFS

Depth-First Search (DFS) 简单来说就是一条路走到黑，算法可以用两种形式表示，一种是将BFS中的queue换成stack，另一种是递归的形式：

Algorithm

Basic DFS Properties

Application: Topological Sort

DFS可以用来计算Topological Sort，首先给出Topological Sort的定义：

简单来说，DFS算法后探索到的节点的值越大，所以有如下算法：

算法的正确性以及运行时间：

Strongly Connected Components (SCC)

强联通分量(SCC)定义了有向图上的一个等价关系：

来看一个例子：

我们的目标是找出全部强联通分量，老师给出了Kosaraju’s Two-Pass Algorithm

Kosaraju’s Two-Pass Algorithm

首先给出伪代码：

这个算法分为两轮，第一轮先构造一个反向图Grev，从编号最大的节点开始做DFS，如果有多个邻接点，优先选择最小的节点，记录每个节点的访问次序，第一个走到终点的节点记录为1，以此类推。

第二轮在原图中，按照访问次序从大到小的方式做DFS，每次的起始点为”leader”，这样就可以计算出SCC。

光说比较抽象，来看一张图：

可以看到这个算法的运行时间为两次DFS的时间，所以为$O(m+n)$

Correctness of Kosaraju’s Algorithm

解释了算法，下面来证明其正确性，我们先给出如下引理：

Key Lemma

如果原图中有两个相邻的SCC：

令$f(v)$为Grev中每个节点第一轮DFS完成的时间，那么对于上图

我们从这个引理来证明结论的正确性，先看下图：

如果引理成立，那么根据算法，我们会先搜索最右边的$C_4$，等探索完这个部分后，在探索$C_2$或者$C_3$，以此类推。

引理的证明：

在Grev中，记$C_1 \bigcup C_2$被第一轮的DFS第一个访问的节点为$v$，考虑$v$在Grev中的位置，如下图：

如果$v\in C_1$，根据DFS的特点，我们从$v$开始访问完$C_1$中每个节点，然后访问$C_2$中节点，所以$C_1$中每个节点的次序都比$C_2$中每个节点小，从而结论成立。

如果$v\in C_2$，根据DFS的特点，我们从$v$开始访问节点，后续必然会访问$C_1$中节点，所以所以$C_1$中每个节点的次序都比$f(v)$小，从而结论也成立。