OMSCS-GA课程笔记03-Graph Algorithms

这个系列是Gatech OMSCS 高级算法课程(CS 6515: Intro to Grad Algorithms)的同步课程笔记。课程内容涉及动态规划、随机算法、分治、图算法、最大流、线性规划以及NP完备等高级算法的设计思想和相关应用，本节主要介绍图上的相关算法。

图是一种重要的数据结构，很多现实中的问题都可以抽象为对图的操作。本节课我们首先从图的遍历入手，在介绍图遍历的基础上推导图上的其它算法。

Strongly Connected Components

DFS

深度优先搜索(depth-first search, DFS)是对图进行遍历的基本方法。假设图G是一个无向图，通过DFS可以得到图上所有相连的节点。无向图上的DFS算法伪代码如下：

DFS(G):
  cc = 0

  for v in V:
    visited[v] = False
	
  for v in V:
    if not visited[v]:
      cc += 1
      Explore(v)

Explore(z):
  ccnum[z] = cc
  visited[z] = True

  for (z, w) in E:
    if not visited[w]:
      Explore(w)

DFS的复杂度为$O(n+m)$。

DFS是很多更高级图算法的基础。除了计算联通节点之外还可以使用DFS来计算联通节点之间的路径，不过此时需要对DFS算法进行一些修改，在进行遍历时使用prev[v]来记录当前节点的上一个节点：

DFS(G):
  cc = 0

  for v in V:
    visited[v] = False
    prev[v] = None
	
  for v in V:
    if not visited[v]:
      cc += 1
      Explore(v)

Explore(z):
  ccnum[z] = cc
  visited[z] = True

  for (z, w) in E:
    if not visited[w]:
      Explore(w)
      prev[w] = z

对于有向图我们同样可以使用DFS来计算联通节点。不过此时我们需要引入pre和post两个数组来记录节点的访问顺序：

DFS(G):
  clock = 1

  for v in V:
    visited[v] = False

  for v in V:
    if not visited[v]:
      Explore(v)

Explore(z):
  pre[z] = clock
  clock += 1

  visited[z] = True

  for (z, w) in E:
    if not visited[w]:
      Explore(w)

  post[z] = clock
  clock += 1

Types of Edges

在有向图上使用DFS相当于把图上的节点按照树进行展开。

根据pre和post两个数组上记录的值可以对原始图上的边进行分类：对于有向边(z, w)，树上的反向边会出现post[z] < post[w]，而其它情况下则满足post[z] > post[w]。

Topological Sorting

当图G的DFS tree存在反向边时称图上存在环。

如果有向图G上没有环则称其为一个有向无环图(directed acyclic graph, DAG)。对于DAG来说我们可以根据访问顺序对图上的节点进行排序，使得排序后的节点都是从低序号到高序号。具体来说，只需要使用DFS来计算节点顺序然后按照post数组的逆序进行排序即可。

这里我们额外需要说明的是拓扑排序后的图上会有两类节点，其中一类没有边进入称为source vertex，还有一类节点没有指向其它节点的边称为sink vertex。对于DAG来说，图上至少有一个source vertex和一个sink vertex。

同时注意到source vertex总是具有最大的post数值而sink vertex总是具有最小的post数值，因此另一种可行的拓扑排序算法是不断寻找图上的sink vertex然后删除。

Connectivity

图上的强联通分量(strongly connected components, SCC)是图上节点的集合，其中集合内的任意一对节点v和w之间存在相互联通的路径。

以下图为例，图上存在5个强连通分量。

有向图的一个重要性质在于其SCC之间构成一个DAG，称为metagraph。

因此在有向图上计算SCC的基本思想在于利用metagraph是一个DAG的性质。我们可以尝试寻找metagraph上的sink SCC然后从图上删除掉，不断重复这样的过程直至图为空。由于选择的是sink SCC，从其中任意一个节点进行访问都只能访问到SCC内的其它节点。

那么如何取寻找sink SCC呢？最直观的想法是从post数组中选择具有最小数值的那个节点。但遗憾的是具有最小post数值的节点不一定位于一个sink SCC中。

实际上具有最大post数值的节点一定位于一个source SCC中。

因此计算SCC的第一步在于反转图上的边，然后在反转图上寻找source SCC。此时找的source SCC在原始图上是一个sink SCC。

这样有向图上计算SCC的算法主要流程为：

反转边的指向得到反转图
在反转图上使用DFS得到节点排序
在原始图上利用排序对节点进行遍历

当然计算SCC算法依赖于最大post数值的节点位于source SCC中这一性质。

2-Satisfiability

SAT Problem

SCC算法的一个应用是求解布尔可满足性问题(satisfiability, SAT)。在SAT问题中有n个布尔变量，我们希望能够找到满足语句要求的变量值：

从更严格的角度来说，对于包含n个布尔变量和m个从句的语句我们希望能够找到一个对布尔变量的赋值使得语句的布尔值为True。

k-SAT

根据每个从句的规模我们可以定义k-SAT问题，其中每个从句包含最多k个布尔变量。对于k-SAT问题人们已经证明在k大于2的情况下它是NP-complete，而对于2-SAT问题则存在多项式复杂度的解法。

对于2-SAT问题我们可以简化语句，首先满足只包含1个变量的从句然后从整个语句中删除它。

通过不断地简化我们最终会得到一个新的语句。显然两个语句的可满足性是等价的，因此只需要验证新的语句是否是可满足的即可。

Graph of Implications

语句化简后我们可以把它等价地表示为一张图，称为graph of implications。具体地，我们把n个变量的布尔取值表示为图上的节点，而m个从句则可以表示为2条对应的边。

如果语句是可满足的，那么graph of implications上不能存在任意变量$x$到$\bar{x}$的路径，否则会产生矛盾。换句话说，如果$x$和$\bar{x}$位于同一个SCC中，则语句是无法满足的。

SCC’s

这样我们就可以利用SCC的算法来解决2-SAT问题，如果每一对布尔变量都位于不同的SCC中则说明语句是可以满足的。

首先我们在图上寻找一个sink SCC，记为$S$。然后满足$S$中的所有条件，从图上删除SCC并不断重复上面的过程。这个算法的缺陷在于没有考虑S的补集$\bar{S}$，当$S$得到满足时$\bar{S}$可能是无法满足的。

为了解决这样的问题，我们可以考虑在图上寻找一个source SCC，记为$S’$。然后把$S’$设为False，并且从图上删除$S’$。最后寻找$S’$的补集$\bar{S’}$，其必为一个sink SCC，然后将其设为True即可。

2-SAT Algorithm

总结一下，利用SCC算法来求解2-SAT问题的方法如下：

Minimum Spanning Tree

Greedy Approach

贪心(greedy)是经典的算法设计思想，在贪心算法中我们把整个问题分解为若干个子问题然后通过最优化每一个子问题来试图优化原始问题。当然并不是所有的问题都可以使用贪心这样的方法来进行优化，比如说knapsack问题就无法通过贪心来进行求解。

MST Problem

最小生成树(minimum spanning tree, MST)是图上的经典问题，我们希望对于无向图G可以找到一个最小的子图来包含原始图的所有节点。显然这个最小的子图一定是一个树结构，称为最小生成树。

在介绍计算MST的算法前我们先来回顾一下树这种数据结构的性质。首先树是一个DAG，而且对于包含n个节点的树其边的数量为n-1，同时树上任意两个节点之间有且只有一条路径连接它们。关于树最重要的一条性质是如果一张图的边和节点数满足$\vert E \vert = \vert V \vert - 1$，那么它一定是一棵树。

Greedy Approach for MST

MST可以使用贪心的思想来进行计算。我们可以不断地在添加图上具有最小权重的边，同时保证生成的图是一棵树即可。这种计算MST的算法称为Kruskal算法(Kruskal’s algorithm)，它的复杂度为$O(m \log{n})$。

Kruskal算法的正确性则可以使用归纳法来进行证明。

Cuts

我们还可以借助图割(cut)的概念来处理MST问题。cut是指把图上的节点分为两个集合$S$和$\bar{S}$，其中连接两个集合的边称为cut edge。

基于cut的概念，Kruskal算法可以理解为不断地寻找当前图上的最小cut edge。

Prim’s Algorithm

除了Kruskal算法之外，Prim算法(Prim’s algorithm)同样是计算MST的经典算法。

Markov Chains and PageRank

PageRank是图算法的重要应用，早期Google的搜索引擎就是基于PageRank来实现的。要理解PageRank还需要引入Markov链(Markov chain)的概念，很多工程问题都会使用Markov链来进行建模和求解。

Markov Chains

Markov链是一种概率模型，它可以表示为一张有向图。此时图上的顶点表示系统可能的状态，图上的边和权重分别表示状态转移的方向和概率。具体来说，节点$i$到$j$的有向边权重表示系统从状态$i$转移到状态$j$的概率：

\[P(i, j) = Pr(j \vert i)\]

同时它还要满足归一化条件：

\[\sum_j P(i, j) = 1, \ \forall i\] \[0 \leq P(i, j) \leq 1, \ \forall i, j\]

实际上Markov链的状态转移概率还可以表示为一个矩阵，称为状态转移矩阵(transition matrix)。它的每个元素即为上面定义的状态转移概率，因此每一行都具有归一性。

k-Step Transition

如果我们忽略状态转移矩阵中具体的概率，将全部非零项设置为1，就能得到图的邻接矩阵(adjacency matrix)。邻接矩阵的一个重要性质是它的$k$次幂$A^k$中任意元素$A^k(i, j)$表示从$i$出发经过$k$步移动到$j$的路径数量。

状态转移矩阵也有类似的性质：$P^k$中任意元素$P^k(i, j)$表示从$i$出发经过$k$步移动到$j$的概率。

Stationary Distribution

当步数$k$比较大时$P^k$中每一行都会收敛到同一个行向量上。

实际上可以证明当步数趋于无穷时，$P^k$中每一行都会收敛到某个向量$\pi$上。这表示无论从图上的哪个节点出发，经过足够多的步数后落到状态$j$的概率都是$\pi(j)$。这个行向量(概率分布)称为Markov链的平稳分布(stationary distribution)。

我们关心Markov链何时具有平稳分布，是否只具有唯一的平稳分布，以及多快可以收敛到平稳分布。

Linear Algebra View

从线性代数的角度来看，从初始状态分布$\mu_0$通过Markov链进行状态转移相当于行向量$\mu_0$与矩阵$P$的乘积：

\[\mu_0 P = \mu_1\]

对于平稳分布$\pi$则有：

\[\pi P = \pi\]

即$\pi$是矩阵(线性变换)$P$的一个不动点，或者说$\pi$是矩阵$P$对应特征值1的特征向量。实际上1还是矩阵$P$的最大特征值，即$\pi$是矩阵$P$的主特征向量(principal eigenvector)。需要额外说明的是矩阵$P$可能有多个主特征向量，即平稳分布$\pi$可能是不唯一的。

Bipartite Markov Chain

当Markov链具有如下所示的二分图结构时，初始状态会决定最终收敛到的平稳分布。要避免这种情况可以为图上的每个节点添加一个自循环边，这相当于为矩阵$P$添加了对角元。我们称此时的Markov链是非周期(aperiodic)的。

Multiple SCCs

另一种需要避免的情况是图上具有若干个不同的强连通分量，如果我们移动到某个SCC中时会陷入其中无法离开。因此我们希望图上只有一个强连通分量，这可以为图上的每一对节点赋予有向边来实现，相当于保证任意两个状态都是可以相互转换的。我们称此时的Markov链是不可约(irreducible)的。

Ergodic MC

当Markov链满足非周期和不可约条件时称其为遍历(ergodic)的，此时的Markov链具有唯一的平稳分布$\pi$。对于PageRank算法来说，它相当于在一张由网页组成的巨型图上进行随机游走，当这张图满足相应的条件时无论从何处开始游走最终都会收敛到平稳分布$\pi$上。此时某个页面的重要性即为$\pi$对应位置的概率。