以前学习了算法，然而因为没有记录下来，最近又要从新开始学习了，这次就将我的学习经验汇总成文章，记录下来。

科萨拉朱算法（英语：Kosaraju's algorithm），也被称为科萨拉朱—夏尔算法，是一个在线性工夫内寻找一个有向图 "图 (数学)")中的强连通重量的算法。

首先咱们须要晓得几个概念

有向图

边为有方向的图称作有向图（英语：directed graph或digraph）。

有向图的一种比拟严格的定义是这样的：一个二元组\( G=(V,E) \)，其中

  • \( V \)是节点的汇合；
  • \( {\displaystyle E\subseteq {(x,y)\mid (x,y)\in V^{2}\wedge x\neq y}} \)是边（也称为有向边，英语：directed edge或directed link；或弧，英语：arcs）的汇合，其中的元素是节点的有序对。

下图是一个简略的有向图：

强连通重量

有向图中，尽可能多的若干顶点组成的子图中，这些顶点都是互相可达到的，则这些顶点成为一个强连通重量。

其实求解强连通重量的算法并不止一种，除了Kosaraju之外还有赫赫有名的Tarjan算法能够用来求解。但相比Tarjan算法，Kosaraju算法更加==直观==，更加==容易了解==。

DFS 生成树

先来理解 DFS 生成树，咱们以上面的有向图为例：

有向图的 DFS 生成树次要有 4 种边（不肯定全副呈现）：

  1. 树边（tree edge）：示意图中以彩色边示意，每次搜寻找到一个还没有拜访过的结点的时候就造成了一条树边。
  2. 反祖边（back edge）：示意图中以红色边示意（即 \( 7 \rightarrow 1 \)），也被叫做回边，即指向先人结点的边。
  3. 横叉边（cross edge）：示意图中以蓝色边示意（即 \( 9 \rightarrow 7 \)），它次要是在搜寻的时候遇到了一个曾经拜访过的结点，然而这个结点 并不是 以后结点的先人。
  4. 前向边（forward edge）：示意图中以绿色边示意（即 \( 3 \rightarrow 6 \)），它是在搜寻的时候遇到子树中的结点的时候造成的。

这是应用 js 实现的一个简略的 DFS：

const depth1 = (dom, nodeList) => {    dom.children.forEach((element) => {        depth1(element, nodeList)     })     nodeList.push(dom.name) }

咱们思考 DFS 生成树与强连通重量之间的关系。

如果结点 \( u \)  是某个强连通重量在搜寻树中遇到的第一个结点，那么这个强连通重量的其余结点必定是在搜寻树中以 \( u \) 为根的子树中。结点 \( u \) 被称为这个强连通重量的根。

反证法：假如有个结点 \( v \) 在该强连通重量中然而不在以 $u$ 为根的子树中，那么 \( u \) 到 \( v \) 的门路中必定有一条来到子树的边。然而这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点曾经被拜访过了，这就和 \( u \) 是第一个拜访的结点矛盾了。得证。

Kosaraju 算法

该算法依附两次简略的 DFS 实现：

第一次 DFS，选取任意顶点作为终点，遍历所有未拜访过的顶点，并在回溯之前给顶点编号，也就是后序遍历。

第二次 DFS，对于反向后的图，以标号最大的顶点作为终点开始 DFS。这样遍历到的顶点汇合就是一个强连通重量。对于所有未拜访过的结点，选取标号最大的，反复上述过程。

两次 DFS 完结后，强连通重量就找进去了，Kosaraju 算法的工夫复杂度为 \( O(n+m) \) 。

这里利用下网上的算法，简略示意一下：

N = 7graph, rgraph = [[] for _ in range(N)], [[] for _ in range(N)]used = [False for _ in range(N)]popped = []# 建图def add_edge(u, v):    graph[u].append(v)    rgraph[v].append(u)# 正向遍历def dfs(u):    used[u] = True    for v in graph[u]:        if not used[v]:            dfs(v)    popped.append(u)# 反向遍历def rdfs(u, scc):    used[u] = True    scc.append(u)    for v in rgraph[u]:        if not used[v]:            rdfs(v, scc)            # 建图，测试数据         def build_graph():    add_edge(1, 3)    add_edge(1, 2)    add_edge(2, 4)    add_edge(3, 4)    add_edge(3, 5)    add_edge(4, 1)    add_edge(4, 6)    add_edge(5, 6)if __name__ == "__main__":    build_graph()    for i in range(1, N):        if not used[i]:            dfs(i)    used = [False for _ in range(N)]    # 将第一次dfs出栈程序反向    popped.reverse()    for i in popped:        if not used[i]:            scc = []            rdfs(i, scc)            print(scc)

动画演示

动画演示和规范的 Kosaraju 算法有点不一样：它是先 DFS 遍历顶点失去逆后序排序，而后再将有向图置为反向图，依照逆后序排序取出顶点，深度优先搜寻反向图。后果和 Kosaraju 算法统一。

援用、举荐

  • https://xie.infoq.cn/article/02144dc8c84e4b85cc9b27779
  • https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)#%E6%9C%89%E5%90%91%E5%9B%BE
  • https://oi-wiki.org/graph/scc/#kosaraju-%E7%AE%97%E6%B3%95
  • https://www.cnblogs.com/nullzx/p/6437926.html
  • https://www.cnblogs.com/RioTian/p/14026585.html
  • https://www.youtube.com/watch?v=TyWtx7q2D7Y
  • https://www.youtube.com/watch?v=R6uoSjZ2imo
  • https://redspider110.github.io/2018/08/22/0093-algorithms-scc...