以前学习了算法,然而因为没有记录下来,最近又要从新开始学习了,这次就将我的学习经验汇总成文章,记录下来。
科萨拉朱算法 (英语: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 种边(不肯定全副呈现):
- 树边(tree edge):示意图中以彩色边示意,每次搜寻找到一个还没有拜访过的结点的时候就造成了一条树边。
- 反祖边(back edge):示意图中以红色边示意(即 \(7 \rightarrow 1 \)),也被叫做回边,即指向先人结点的边。
- 横叉边(cross edge):示意图中以蓝色边示意(即 \(9 \rightarrow 7 \)),它次要是在搜寻的时候遇到了一个曾经拜访过的结点,然而这个结点 并不是 以后结点的先人。
- 前向边(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…