From 2b1adc2d5a07e32b2c821f8424b67c4cd235e38c Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E9=9B=B7=E8=92=BB?= <34390285+hsfzLZH1@users.noreply.github.com> Date: Sun, 14 Jul 2019 18:53:12 +0800 Subject: [PATCH] Update scc.md MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 添加了一个句号。更改了一个英文句号。 --- docs/graph/scc.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/docs/graph/scc.md b/docs/graph/scc.md index d5504a7e..1d9c3ded 100644 --- a/docs/graph/scc.md +++ b/docs/graph/scc.md @@ -52,7 +52,7 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中,对于结点 $u$ 和与其相邻的结点 $v$ (v 不是 u 的父节点)考虑 3 种情况: 1. $v$ 未被访问:继续对 $v$ 进行深度搜索。在回溯过程中,用 $LOW[v]$ 更新 $LOW[u]$ 。因为存在从 $u$ 到 $v$ 的直接路径,所以 $v$ 能够回溯到的已经在栈中的结点, $u$ 也一定能够回溯到。 -2. $v$ 被访问过,已经在栈中:即已经被访问过,根据 $LOW$ 值的定义(能够回溯到的最早的已经在栈中的结点),则用 $DFN[v]$ 更新 $LOW[u]$ . +2. $v$ 被访问过,已经在栈中:即已经被访问过,根据 $LOW$ 值的定义(能够回溯到的最早的已经在栈中的结点),则用 $DFN[v]$ 更新 $LOW[u]$ 。 3. $v$ 被访问过,已不在在栈中:说明 $v$ 已搜索完毕,其所在连通分量已被处理,所以不用对其做操作。 将上述算法写成伪代码: @@ -70,7 +70,7 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 对于一个连通分量图,我们很容易想到,在该连通图中有且仅有一个 $DFN[u]=LOW[u]$ 。该结点一定是在深度遍历的过程中,该连通分量中第一个被访问过的结点,因为它的 DFN 值和 LOW 值最小,不会被该连通分量中的其他结点所影响。 -因此,在回溯的过程中,判定 $DFN[u]=LOW[u]$ 的条件是否成立,如果成立,则栈中从 $u$ 后面的结点构成一个 SCC。 +因此,在回溯的过程中,判定 $DFN[u]=LOW[u]$ 的条件是否成立,如果成立,则栈中从 $u$ 后面的结点构成一个 SCC 。 ### 实现 @@ -105,7 +105,7 @@ Kosaraju 算法依靠两次简单的 DFS 实现。 第二次 DFS,对于反向后的图,以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。 -两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为 $O(n+m)$ +两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为 $O(n+m)$ 。 ### 实现 -- 2.11.0