原文出处：MRRiddler

本篇主要涉及到图论的基本算法，不包含有关最大流的内容。图论的大部分算法都是由性质或推论得出来的，想朴素想出来确实不容易。

二分图(Is-Bipartite)

一个图的所有顶点可以划分成两个子集，使所有的边的入度和出度顶点分别在这两个子集中。

这个问题可以转换为上篇提到过的图的着色问题，只要看图是否能着2个颜色就行了。当然，可以回溯解决这个问题，不过对于着2个颜色可以BFS解决。

同样，一维数组colors表示节点已着的颜色。

伪代码：
IS-BIPARTITE(g,colors)
  let queue be new Queue
  colors[0] = 1
  queue.push(0)
  while queue.empty() == false
    let v = queue.top()
    queue.pop()
    for i equal to every vertex in g
      if colors[i] == 0
        colors[i] = 3 - colors[v]
        queue.push(i)
      else if colors[i] == colors[v]
        return false
    end
  end
  return true

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

DFS改良(DFS-Improve)

上篇文章提到过，搜索解空间是树形的，也就是在说BFS和DFS。那么在对图进行BFS和DFS有什么区别呢，这个问题要从解空间角度去理解。对图进行BFS的解空间是一颗树，可叫广度优先树。而DFS是多棵树构成的森林，可叫深度优先森林。

这里要对DFS进行小小的改良，它的性质会对解多个问题会很有帮助。原版DFS搜索的时候，会先遍历本顶点，再递归遍历临接的顶点。DFS改良希望能先递归遍历临接的顶点，再遍历本顶点，并且按遍历顺序逆序存储起来。

伪代码：
DFS-IMPROVE(v,visited,stack)
  visited[v] = true
  for i equal to every vertex adjacent to v
    if visited[i] == false
      DFS-IMPROVE(i,visited,stack)
  end
  stack.push(v)

这个改良版DFS有个很有用的性质就是，对于两个顶点A、B，存在A到B的路径，而不存在B到A的路径，则从记录的顺序中取出的时候，一定会先取出顶点A，再取出顶点B。以下为这个性质的证明。

假设：有两个顶点A和B，存在路径从A到B，不存在路径从B到A。 证明：分为两种情况，情况一，先搜索到A顶点，情况二，先搜索到B顶点。对于情况一，由命题可得，A一定存储在B之后，那么取出时先取出的是顶点A。对于情况二，先搜索到B顶点，由于B顶点搜索不到A顶点，则A一定存储在B之后，那么取出时仍先取出的是顶点A，命题得证。

DFS改良性质：对于两个顶点A、B，存在A到B的路径，而不存在B到A的路径，则从记录的顺序中取出的时候，一定会先取出顶点A，再取出顶点B。

欧拉回路(Eulerian-Path-And-Circuit)

在无向图中，欧拉路径定义为，一条路径经过所有的边，每个边只经过一次。欧拉回路定义为，存在一条欧拉路径且路径的起点和终点为同一个顶点。可以看到只有连通图才能有欧拉回路和欧拉路径。

这个算法很巧。如果一条路径要经过一个顶点，本质是从一条边到达一个顶点，然后从这个顶点通过另一条边出去。欧拉回路就是要求路径要经过所有的点，起点和终点还都是同一个顶点。那么就等价于要求所有顶点连接的边是2个。实际上，路径还可以经过顶点多次，那么就等价于要求所有顶点连接的边是偶数个。欧拉路径的要求就等价于所有顶点连接的边是偶数个，除了起点和终点两个顶点可以是奇数个。

先判断图是否是连通图。返回0代表没有欧拉回路或者欧拉路径，返回1代表有欧拉路径，返回2代表有欧拉回路。

伪代码：
EULERIAN-PATH-AND-CIRCUIT(g)
  if isConnected(g) == false
    return 0
  let odd = 0
  for v equal to every vertex in g
    if v has not even edge
      odd = odd + 1
  end
  if odd > 2
    returon 0
  if odd == 1
    return 1
  if odd == 0
    return 2

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

拓扑排序(Topological-Sorting)

将一张有向无环图的顶点排序，排序规则是所有边的入度顶点要在出度顶点之前。可以看到，无向和有环图都不存在拓扑排序，并且拓扑排序可能存在多种解。

拓扑排序有两种解法，一种是从搜索角度。

如果我能保障先递归遍历临接的顶点，再遍历本顶点的话，那么遍历的顺序的逆序就是一个拓扑排序。那么就可以直接用DFS改良求解出拓扑排序。

伪代码：
TOPOLOGICAL-SORTING-DFS(g)
  let visited be new Array
  let result be new Array
  let stack be new Stack
  for v equal to every vertex in g
    if visited[v] == false
      DFS-IMPROVE(v,visited,stack)
  end
  while stack.empty() == false
      result.append(stack.top())
      stack.pop()
  end
  return result

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

另一种是贪心选择。

直觉上，既然要所有边的出度顶点在入度顶点之前，可以从入度和出度角度来解决问题。可以让入度最小的排序在前，也可以让出度最大的排序在后，排序后，这个顶点的边都不会再影响问题了，可以去掉。去掉后再重新加入新的顶点，直到加入所有顶点。

这个问题还有个隐含条件，挑选出、入度最小的顶点就等价于挑选出、入度为0的顶点。这是因为图必须是无环图，所以肯定存在出、入度为0的顶点，那么出、入度最小的顶点就是出、入度为0的顶点。

直觉上这是一个可行的策略，细想一下，按出度最大排序和按入度为零排序是否等价。实际上是不等价的，按入度为零排序，如果出现了多个入度为零的顶点，这多个顶点排序的顺序是无关的，可以任意排序。而按出度最大排序，出现了多个入度最大的顶点，这多个顶点排序是有关的，不能任意排序。所以，只能按入度为零排序。实际上，这个想法就是贪心选择。下面以挑选入度为零的边作为贪心选择解决问题，同样地，还是先证明这个贪心选择的正确性。

命题：入度为零的顶点v排序在前。 假设：S为图的一个拓扑排序，l为此排序的首个顶点。 证明：如果l=v，则命题得证。如果l不等于v，将l顶点从S中去除，然后加入顶点v得到新的排序S‘。因为S去除l以后l以后的排序没有变，仍为拓扑排序，v入度为零，v前面可以没有顶点，所以S’也为图的一个拓扑排序，命题得证。

伪代码：
TOPOLOGICAL-SORTING-GREEDY(g)
  let inDegree be every verties inDegree Array
  let stack be new Stack
  let result be new Array
  for v equal to every vertex in g
    if inDegree[v] == 0
      stack.push(v)
  end
  while stack.empty() == false
    vertex v = stack.top()
    stack.pop()
    result.append(v)
    for i equal to every vertex adjacent to v
      inDegree[i] = inDegree[i] - 1
      if inDegree[i] == 0
        stack.push(i)
    end
  end
  return result.reverse()

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

强连通分量(Strongly-Connected-Components)

图中的一个顶点与另一个顶点互相都有路径可以抵达，就说这两个顶点强连通。图中有多个顶点两两之间都强连通，则这多个顶点构成图的强连通分量。

朴素的想法是，假如从一个顶点A可以搜索到另一个顶点B，如果从B顶点再能搜索回A顶点的话，A、B就在一个强连通分量中。不过，这样每两个顶点要进行两次DFS，复杂度肯定会很高。这里可以引入转置图(将有向边的方向翻转)的性质。这样问题就转换成了，从A顶点搜索到B顶点，将图转置后，如果再A顶点还能搜索到B顶点，A、B顶点就在一个强连通分量中。用算法表述出来就是先从A顶点DFS，然后将图转置，再从A顶点DFS，两次DFS都能搜索到B顶点的话，B顶点就与A顶点在同一个强连通分量中。然而朴素想法只能想到这里了。

有多个算法被研究出来解决这个问题，下面先介绍Kosaraju算法。

• Kosaraju

Kosaraju算法使用了DFS改良的性质去解决问题，想法很有趣。Kosaraju算法现将图进行DFS改良，然后将图转置，再进行DFS。第二次DFS每个顶点能够搜索到的点就是一个强连通分量。算法正确性和说明如下。

通过DFS改良性质可以得出定理，一个强连通分量C如果有到达另一个强连通分量C’的路径，则C’比C先被搜索完，这个定理很明显，如果C中有路径到C’，那么根据DFS改良性质一定会先搜索到C，再搜索完C’，再搜索完C。将这个定理做定理1。

定理1：一个强连通分量C如果有到达另一个强连通分量C’的路径，则C’比C先被搜索完。

定理1还可以再进行推论，如果一个强连通分量C有到达另一个强连通分量C’的路径，则将图转置后，C比C’先被搜索完，这个推论也很明显，将图转置后，不存在C到C’的路径，存在C’到C的路径，而仍是先搜索C再搜索C‘，所以C比C‘先被搜索完，这个推论作为推论1。

推论1：如果一个强连通分量C有到达另一个强连通分量C’的路径，则将图转置后，C比C’先被搜索完。

以下为用结构归纳法对算法正确性进行证明。

命题：第二次DFS每个顶点能够搜索到的点就是一个强连通分量。 假设：n代表图中有多少个强连通分量。  证明：如果n=1，则第二次DFS就是搜索一遍所有顶点，命题得证。现在假设n=k时，命题成立。现证明n=k+1时，是否成立。假设搜索到第k+1个强连通分量的第一个顶点为u，u肯定能搜索到所有k+1个强连通分量的顶点。并且根据推论1，此时被转置后的图，所有从第k+1个强连通分量能到达的其他强连通分量都已经被搜索过了。所以u只能搜索到所有第k+1个强连通分量的顶点，即第二次DFS每个顶点只能够搜索到包含此顶点的强连通分量中的顶点，命题得证。

伪代码：
KOSARAJU-STRONGLY-CONNECTED-COMPONENTS(g)
  let visited be new Array
  let stack be new Stack
  for v equal to every vertex in g
    if visited[v] == false
      DFS-IMPROVE(v,visited,stack)
  end
  let gt = transpose of g
  for v equal to every vertex in g
    visited[v] = false
  end
  while stack.empty() == false
    vertex v = stack.top()
    stack.pop()
    if visited[v] == false
      DFS(v,visited)
      print '\n Found a Strongly Connected Components \n'
  end
  
DFS(v,visited)
  visited[v] = true
  print v
  for i equal to every vertex adjacent to v
    if visited[i] == false
      DFS(i,visited,stack)
  end

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

Kosaraju算法需要进行两次DFS，那么可不可以只进行一次DFS，边遍历边找强连通分量？Tarjan就是这样的算法。

• Tarjan

同样，还是要基于DFS搜索性质来思考问题。DFS创建出的深度优先搜索树会先被访问根节点再被访问子孙节点。什么时候会出现强连通分量？只有子孙节点有连通祖先节点的边的时候。如果从某个节点，其子孙节点都只有指向自己子孙节点的边的时候，这是明显没有构成强连通分量的。那么，出现了子孙节点指向其祖先节点的时候，从被指向的祖先节点一直搜索到指向的子孙节点所经过所有顶点就构成了一个强连通分量。如果出现了多个子孙节点都指向了祖先节点怎么办？最早被指向、访问的祖先节点到最晚指向、访问的子孙节点构成了“最大“的强连通分量，这才是想要找的强连通分量。如果遇到了一个指向祖先节点的子孙节点，就算构成一个强连通分量，会导致找到多个互相嵌套的强连通分量。那么，要记录访问顺序就要为每个节点设置一个被访问顺序的编号，让属于同一个强连通分量的顶点编号一致。上面讨论的是构成了一个强连通分量怎么处理，如果没有多个节点构成的强连通分量怎么处理？在搜索节点之前，为这个节点默认设置上被访问的顺序编号，这样如果没有搜索到多个节点构成的强连通分量，每个节点就是自己的强连通分量。

算法表述为，从某个节点开始搜索，默认设置自己为一个强连通分量。只要节点有子孙节点，就要等待子孙节点都搜索完，再更新自己强连通分量信息。只要节点有指向祖先节点，也要更新自己的强连通分量。判断子孙节点构成的强连通分量”大“还是自己构成的强连通分量”大“，自己属于最”大“的强连通分量。也就是说，算法找出了所有顶点的所属的最“大”强连通分量。

数组disc表示顶点被访问顺序的编号，数组low表示顶点所在的强连通分量编号。最后当顶点在disc和low中编号一致时，代表顶点是所在强连通分量中第一个被搜索到的顶点。此时，输出所在的强连通分量所包括的顶点。

伪代码：
TARJAN-STRONGLY-CONNECTED-COMPONENTS(g)
  let disc be new Array
  let low be new Array
  let stack be new Stack
  let isInStack be new Array
  for i from 1 to the number of vertex in g
    disc [i] = -1
    low [i] = -1
  end
  for u from 1 to the number of vertex in g
    if disc[i] != -1
      TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(u,disc,low,stack,isInStack)
  end
   
TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(u,disc,low,stack,isInStack)
  let time be static
  time = time + 1
  disc[u] = low[u] = time
  stack.push(u)
  isInStack[u] = true
  for v equal to every vertex adjacent to u
    if disc[v] == -1
      TARJAN-STRONGLY-CONNECTED-COMPONENTS-UTIL(v,disc,low,stack,isInStack)
      low[u] = min(low[u],low[v])
    else if isInStack[v] == true
      low[u] = min(low[u],disc[v])
  end
  let w = 0
    if low[u] == disc[u]
      while stack.top() != u
        w = stack.top()
        isInStack[w] = false
        stack.pop()
        print w
      end
      w = stack.top()
      isInStack[w] = false
      stack.pop()
      print w
      print '\n Found a Strongly Connected Components \n'

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

图的割点(Articulation Points)、桥(Bridge)、双连通分量(Biconnected Components)

• 图的割点(Articulation-Points)

图的割点也叫图的关节点，定义为无向图中分割两个连通分量的点，或者说去掉这个点，图中的连通分量数增加了。可以看到如果求出了连通分量，那么不同连通分量中间的顶点就是割点。什么时候某个顶点不是这样的割点？如果这个顶点的子孙顶点有连接这个顶点祖先顶点的边，那么去掉这个顶点，这个顶点的子孙顶点和祖先顶点仍然连通。那么，寻找割点的过程就等价于寻找子孙顶点没有连接祖先顶点的顶点。这个问题的求解过程类似于Tarjan强连通分量的求解过程。

不过，这个问题有个例外就是根顶点，对一般顶点的处理方式处理根顶点行得通吗？根顶点肯定没有子孙顶点指向祖先顶点，但是根顶点可以是割点。所以，根顶点需要特殊处理。根顶点什么时候是割点？当根顶点有多颗子树，且之间无法互相到达的时候。那么，存不存在根顶点有多颗子树，且之间可以互相到达？不存在，如果互相之间可以到达，那在根顶点搜索第一颗子树的时候，就会搜索到可到达的子树，就不会存在多颗子树了。所以，根顶点有多颗子树，那么这多颗子树之间一定无法互相到达。根顶点有多颗子树，且之间无法互相到达的时候就等价于根顶点有多颗子树。所以，只要根顶点有多颗子树，那么根顶点就是割点。

同样地，数组disc表示顶点被访问顺序的编号，数组low表示顶点所在的强连通分量编号。数组parent找出根顶点。

伪代码：
ARTICULATION-POINTS(g)
  let disc be new Array
  let low be new Array
  let result be new Array
  let parent be new Array
  let visited be new Array
  for i from 1 to the number of vertex in g
    result [i] = false
    visited [i] = false
    parent [i] = -1
  end
  for u from 1 to the number of vertex in g
    if visited[i] == false
      ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)
  end
  for i from 1 to the number if vertex in g
    if result[i] == true
      print '\n Found a Articulation Points i \n'
  end
   
ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)
  let time be static
  time = time + 1
  let children = 0
  disc[u] = low[u] = time
  visited[u] = true
  for v equal to every vertex adjacent to u
    if visited[v] == false
      children = children + 1
      parent[v] = u
      ARTICULATION-POINTS-UTIL(u,disc,low,result,parent,visited)
      low[u] = min(low[u],low[v])
      if parnet[u] == -1 and children > 1
        result[u] = true
      if parent[u] != -1 and low[v] >= disc[u]
        result[u] = true
    else if v != parent[u]
      low[u] = min(low[u],disc[v])
  end

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

• 桥(Bridge)

桥定义为一条边，且去掉这个边，图中的连通分量数增加了。类似于寻找割点，寻找桥就是寻找这样一条，一端的顶点的子孙顶点没有连接这个顶点和其祖先顶点的边。求解过程和求割点基本一致。

伪代码：
BRIDGE(g)
  let disc be new Array
  let low be new Array
  let parent be new Array
  let visited be new Array
  for i from 1 to the number of vertex in g
    visited [i] = false
    parent [i] = -1
  end
  for u from 1 to the number of vertex in g
    if visited[i] == false
      BRIDGE-UTIL(u,disc,low,parent,visited)
  end
   
BRIDGE-UTIL(u,disc,low,parent,visited)
  let time be static
  time = time + 1
  disc[u] = low[u] = time
  for v equal to every vertex adjacent to u
    if visited[v] == false
      parent[v] = u
      BRIDGE-UTIL(u,disc,low,parent,visited)
      low[u] = min(low[u],low[v])
      if low[v] > disc[u]
        print '\n Found a Bridge u->v \n'
    else if v != parent[u]
      low[u] = min(low[u],disc[v])
  end

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数

• 双连通分量(Biconnected-Components)

双连通图定义为没有割点的图。双连通图的极大子图就为双连通分量。双连通分量就是在割点分割成多个连通分量处，共享割点。也就是说双连通分量是去掉割点后构成的连通分量，加上割点和到达割点的边。可以看出，双连通分量可分为不含有割点、一个割点、两个割点三种情况。对于不含有割点，说明图为双连通图。对于含有一个割点，可能为初始搜索的顶点到第一个割点之间的边构成的双连通分量，可能为遇到一个割点后到不再遇到割点之间的边构成双连通分量。对于含有两个割点，两个割点之间的边构成了一个双连通分量。

求解此问题，只要在求割点的算法上做更改就可以了。按照求割点的算法求解割点，找到一个割点，输出找到的边，然后删除找到的边的记录，再去搜索下一个割点。每搜索完图某个顶点的可达顶点，输出找到的边。这样就涵盖了所有的情况。

伪代码：
BICONNECTED-COMPONENTS(g)
  let disc be new Array
  let low be new Array
  let stack be new Stack
  let parent be new Array
  for i from 1 to the number of vertex in g
    disc [i] = -1
    low [i] = -1
    parent [i] = -1
  end
  for u from 1 to the number of vertex in g
    if disc[i] == -1
      BICONNECTED-COMPONENTS-UTIL(u,disc,low,stack,parent)
    let flag = flase
    while stack.empty() == false