专栏首页程序员维他命Tarjan 算法求解强连通分量

Tarjan 算法求解强连通分量

在 《Tarjan 算法的思路》中我们已经给出了 Tarjan 算法中的比较重要的几个元素,我们在这里重新复习一下:

  1. DFN[] 数组:数组存储访问顺序,也就是遍历的点会分配一个序号(从小到大),然后序号存在这个数组当中:DFN[u]为节点 u 搜索的次序编号;
  2. LOW[] 数组:表示该点能直接间接到达时间最小的顶点。例如:LOW[u]为节点 u 的子树能够追溯到最早的栈中节点的次序号;
  3. stack 存储该连通子图中的所有点。

下面我们来聊一聊这几个东西要怎么用。

什么是强连通分量

我们先给出一个强连通分量的定义:在有向图 G 中,如果两个顶点 u, v 之间存在一条 u 到 v 的路径,也存在一个 v 到 u 的路径,则称这两个顶点 u, v 是强连通的(strongly connected)。如果有向图 G 的任意两个顶点都强连通,则称 G 是一个强连通图。

非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。

下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量,总共三个强连通分量。

算法过程

我们先给出一个演示 Tarjan 算法的经典图,从根结点 1 开始DFS,把遍历到的节点入栈(1-3-5-6),当搜索到 u=6 的时候,DFN[6] = LOW[6],当 DFN == LOW 的时候,我们认为找到一个强连通分量。然后执行弹栈操作,直到 u == v 为止,{6} 为一个强连通分量。

此时我们在图中标记一下 6 节点,计作 DFN = 4,LOW = 4。之后回溯到 5 节点,发现 DFN[5] == LOW[5] ,同 6 节点一样继续进行弹栈操作, {5} 为一个强连通分量。

回溯到结点 3,继续 DFS 搜索到结点 4,把 4 进栈。这时发现节点 4 向节点 1 有后向边,节点 1 还在栈中。所以 LOW[4] = 1。由于节点 6 已经弹栈, 边 (4, 6) 是指向非栈中节点的横叉边,因此不更新 LOW[4]。回溯返回到结点3,(3, 4) 为树枝边,所以 LOW[3] = LOW[4] = 1

横叉边:从某个结点指向搜索树中另一个子树中的某结点的边 树枝边:DFS 时经过的边,即 DFS 搜索树上的边。

回溯到根结点 1,最后 DFS 到点 2。访问边 (2, 4),此时点 4 还在栈中,所以 LOW[2] = DFN[4] = 5 返回 1 后,发现 DFN[1] = LOW[1],所以我们就将栈中的点全部取出,组成一个强连通分量 {1, 3, 4, 2}

至此,算法结束。我们通过一次 DFS ,求出了图中全部的三个强连通分量 {1, 3, 4, 2}{5}{6}

可以发现,在 Tarjan 算法中,每个顶点都被访问了一次,且只进出一次栈,每条边也只被访问了一次,所以算法时间复杂度为 O(n + m)

本文分享自微信公众号 - 程序员维他命(J_Knight_)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java集合之CopyOnWriteArrayList源码分析

    CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉...

    用户4143945
  • 更快更简单|飞桨PaddlePaddle显存分配与优化最佳实践

    飞桨(PaddlePaddle)为用户提供技术领先、简单易用、兼顾显存回收与复用的显存优化策略,在Transformer、BERT、DeepLabV3+上Max...

    用户1386409
  • 再谈Java泛型---下

    表面上看起来没什么问题,这个方法声明确实没有任何问题,但问题是调用该方法传入的实际参数时可能不是我们所期望的,例如:

    用户4143945
  • 为博客添加恋爱天数小工具

    AlexTao
  • HashMap和TreeMap的内部结构

    1、基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashM...

    用户4143945
  • 30分钟看懂XGBoost的基本原理

    xgboost是一种集成学习算法,属于3类常用的集成方法(bagging,boosting,stacking)中的boosting算法类别。它是一个加法模型,基...

    AI科技大本营
  • 再谈ThreadLocal

    大家对于ThreadLocal肯定很熟悉了,但是真正在项目中使用过的估计就不多了,有的牛人也许已经使用n多次了。

    用户4143945
  • 再谈泛型java---上

    可以看得出来,每次从list里取数据的时候,需要强制转换,所以这里就很容易报异常:ClassCastException.

    用户4143945
  • LeetCode 141:环形链表 Linked List Cycle

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • Go语言程序设计

    字符串处理:strings.Join(os.Args[1:]," ") 标准输入输出:

    用户5760343

扫码关注云+社区

领取腾讯云代金券