关于前端:kosaraju-算法

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

科萨拉朱算法 （英语：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 = 7
graph, 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…