这篇文章主要介绍有向图的一些常见算法，相关的遍历算法其实和无向图思想有很多相同之处，你可以先阅读这篇文章。

当边开始带有方向时，很多情况的分析就略显复杂。一般我们最长使用的是DFS,因为我们可以在其中引入“时间戳”(Stamp)概念，方便区分父子关系。

在DFS中，边可以被分为四类：

  • Tree Edge: 遍历时发现的指向未访问节点的边
  • Back Edge: 指向祖先节点的边，这意味着图中可能存在着环
  • Forward Edge: 指向子孙节点的边
  • Cross Edge: 指向既不是祖先，也不是子孙节点的边，例如树中指向兄弟节点的边就属于这一类

检测是否有向无环图(DAG)

这个算法的核心思想就是：沿着一条有向路径不断前进,将途经的节点存入栈中,如果发现下一个节点已经在栈中,就说明这存在一个环.

为了方便地反映节点目前的状态，我们定义三种status:

  • WHITE: 未被访问
  • GRAY: 当前在栈中
  • BLACK: 访问结束离开栈中
Algorithm: Is_DAG(graph, status)
Input: A directed graph G, the starting vertex u, and an array which stores the status of each vertex
Output: boolean value

Fn Is_DAG(Graph, status)
    mark all vertex in G as WHITE status
    for each vertex u in G
        if(status[v]==WHITE) //始终从未访问的节点开始
            if(Has_Cycle(G,v,status)==true) return false
        endif
    endfor
    return true




Procedure Has_Cycle(G, u, status)
    status[u]=GRAY
    for each vertex v in G.adj[u]:
        if(status[v]==GRAY): return true // 已在栈中，形成一个环
        else if (status[v]==WHITE):
            if (Has_Cycle(G, v, status)==true) return true
        endif
    endfor
    status[u]=BLACK //标记为完全处理
    return false

获取强连通分量(SCC) – Tarjan 算法

Tarjan 算法是统计有向图中强连通分量数量的高效算法，算法寻找强连通分量的思路和上方一致，但是它另外定义了两个变量来方便判断强连通分量的“根”。

前置概念

  1. 时间戳

    我们可以设置一个不断递增的变量，每次访问一个结点时，这个节点就会记录这个时间戳信息。如此，我们就可以获得了次序信息（这也是拓扑排序的基础）。这个信息由dfn[]存储

  2. low值

    这个变量记录了从当前节点出发，所经过的所有节点中最小的dfn值。结合上面所示算法的思想，很容易理解这个值的作用。如果存在环，那么前向遍历时一定会经过自己的上游节点或者自身，这时候low就会更新。如果不存在环，那些low值就是自己的dfn值

  3. 根

    每一个强连通分量都可以用一个结点来表示，我们称之为强连通分量的根。如果选取这个根呢？──dfn最小的节点即可。从这个节点遍历一定可以访问完分量中所有节点。

而整个算法中判定的最关键条件就是: low[u]=dfn[u].

形象一点理解就是，这个根就是整个SCC的入口，在内部转一圈后，又可以转回自己。

伪代码实现

Algorithm: Tarjan_SCC_Count(G)
Input: A DAG stored in adj-list
Output: the number of SCCs and its size

Fn Tarjan_SCC_Count(G)
    init dfn[1..n],low[1..n]
    init inStack[1..n]={FALSE}
    init timer=0, scc_number=0
    init empty stack S
    init empty array SCC_List // store the root and size of each SCC

    for each vertex v in G:
        if (dfn[v]==0):
            DFS(v)
        endif
    endfor

    return scc_number

Procedure DFS(v)
    timer++
    dfn[v]=low[v] = timer
    S.push(v)
    inStack[v]=TRUE

    for each vertex u in G.adj[v]:
        if(dfn[u]==0):
            DFS(u)
            low[v]=min(low[v],low[u])
        else if(inStack[u]==TRUE): // the cross node
            low[v]=min(low[v],dfn[u])
        endif
    endfor

    if(low[v]==dfn[v]):  // check whether it's the root
        scc_number++
        scc_size=Count_Size(v)
        SCC_List.push({v})

Procedure Count_Size(v)
    current_size=0
    Repeat:
        u=S.pop()
        inStack[u]=FALSE //
        current_size++
    Until u==v  // backward to the root

    return current_size

这里我们可以考虑一种 “8” 字形的情况：

A       D
  ↘   ↙
↑   B   ↑
  ↙   ↘
E       C

在这种情况下，假设从 A 点开始栈中的顺序应该是：

A1          // 右边的数字代表对应的low值
A1B2
A1B2C3
A1B2C3D4    // 在D点的DFS阶段会遇到B点，发现已在栈中，需要更新low值
A1B2C2D2
A1B2C2D2E5  // 这里依然会继续入栈，是因为B的邻接点有两个
A1B2C2D2E1  // 在E点，会遇到A点，发现已在栈中
A1B1C2D2E1  // B点会随E点的low值改变而改变
A1B1C2D2    // 按照 E->D->C->B->A 的顺序出栈
A1B1C2
A1B1
A1

这里比较有趣的是，强连通分量的数量依然为1, 因为整个图其实就是一个巨大的强连通分量。

但是这5个点的low值并没有统一为 1，这里可以看出SCC的根的向心作用。C，D被B钩住，而B，E又被A钩住。这是“缩点”的理解基础。