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

课程地址: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)$小,从而结论也成立。