首页 > 编程语言 >[tarjan强连通分量算法] 目的,图解,思路,伪代码,实例

[tarjan强连通分量算法] 目的,图解,思路,伪代码,实例

时间:2023-04-22 14:02:45浏览次数:55  
标签:tarjan min 连通 访问 dfn low 图解 节点

强连通分量算法(Tarjan's Strongly Connected Component Algorithm)

利用深度优先算法找到一个非强连通的有向图中的所有强连通子图。无向图可以被认为是同时具备u->v和v->u的图。

一些概念
  • 强连通:在有向图中,任意点u与v之间存在有来回两个方向的通路,类似存在一个环;

  • 强连通图:图中任意两点存在强连通;

  • 强连通分量:图中存在强连通的子图;

  • DFN(u):定义为第一次访问点u时的时间戳;

  • LOW(u):定义为u或u的子树能够回溯到的最早的栈中节点的DFN(u)。

思路

当dfn[u] = low[u]时,以u为根的子树上所有节点是一个强连通分量。

  1. 首次访问某点u时,令low[u] = dfn[u] = index(or time)(初始化)

  2. 每到达一个点u,将其入栈(dfs的内容)

  3. 遍历所有与点u相连的点v:

    • 若v不在栈中(树枝边)即未被访问过,递归方法继续往v后面搜索(如dfs()/tarjan()),最终会得出新的low[v];即low[u]=min(low[u], low[v]);

    • 若v在栈内即已被访问,通过比较low[u]和v第一次被访问时的序列号/次数,来更新low[u],即low[u] = min(low[u], dfn[v])。

图解(来自史上最清晰的Tarjan算法详解-segementFault

image

强连通分量:[{0,1,2,3},{4},{5}]

第一步:从节点0开始
  • 首先访问 0 -> 2 -> 4 -> 5并将其加入栈。根据访问顺序标记为1至4。这里也可以从0往1走。

  • 对于节点5(栈内第一个元素),没有后续的节点了,检查到dfn[5] = low[5] = 4,所以退栈,得{5}为一个强连通分量。

image

第二步:返回节点4
  • 节点4只有一个子树(节点5,已退栈),因此low[4] = min(low[4], low[5]) = low[4] = 3。

  • 节点4后无其他子节点,且low[4] = dfn[4],退栈,得到第二个强连通分量。

image

第三步:返回节点2,并访问节点3及其子树
  • low[2] = min(low[2], low[4]) = 2,节点4(已出栈)是其中一个子节点, 节点2仍有后续子节点;

  • 继续探索节点2的另一个子节点3。节点3入栈,初始化dfn[3] = low[3] = 5;

  • 发现节点3有通向节点0的路径,且节点0仍在栈中,有low[3] = min(low[3], dnf[0]) = 1;

  • 发现节点3有通向节点5的路径,但5已退栈,无需更新low[3]。

image

image

第四步:从节点3返回节点2
  • 根据刚刚得到的新low[3]更新low[2] = min(low[2], low[3]) = 1;

  • 节点2无其他后续子节点,返回0

image

第五步:返回节点0,并访问节点1及其子树
  • 根据low[2]更新low[0],low[0] = min(low[0], low[2]) = 1;

  • 发现节点1,dfn[1] = low[1] = 6;

  • 发现后续节点3且3还在栈内,low[1] = min(low[1], dfn[3]) = 5

image

第六步:返回节点0
  • dfn[0] = low[0] = 1, 退栈至0,得

image

伪代码

void tarjan(int u) {
  ++index;
  dfn[u] = low[u] =index;                // 节点u的初始值
  stack.push(u);                         // 入栈
  for (auto& e : edges[u]) {             // 遍历与u相连的点
	if (!visited[e]) {               // 若e未被访问过
	  tarjan(e);                     // 继续向下找其子节点
	  low[u] = min(low[u], low[v]);
	}
	else if (e is in stack) {        // 若e被访问过且还在栈内
	  low[u] = min(low[u], dfn[e]);
	}
  }
  if (dfn[u] == low[u]) {                // 遍历完所有子节点后,检查是否相等
    while (!stack.empty()) {             // 循环退栈并打印
	  v = stack.pop();
	  print v;
	}
  }
}

实例

标签:tarjan,min,连通,访问,dfn,low,图解,节点
From: https://www.cnblogs.com/Akira300000/p/17342951.html

相关文章

  • SpringMvc 视图解析
    重定向forward前缀若要返回/WEB-INF/pages/success.jsp,则直接return"success";即可。若要返回webapp下的helloworld.jsp页面:相对路径../../hello,需return"../../helloworld";forward前缀,转发一个页面,不会进行拼串。需return"forward:/helloworld.jsp";格式:forward:转......
  • 移除给定 Q 个顶点后给定图中的连通分量计数
    移除给定Q个顶点后给定图中的连通分量计数是一个经典的图论问题。给定一个无向图G,和一个由Q个节点组成的集合S,问题的目标是找出在S中所有节点被移除后,G中剩余的连通分量的数量。这个问题在许多实际的应用中都有着广泛的应用,例如网络安全、社交网络分析等。解决这个问题的一种基......
  • LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前3题非常简单,但第4题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大夜......
  • 超详细的图解SSH原理(真的超详细哦~~~~~~~~~)
    1.初见SSHSSH是一种协议标准,其目的是实现安全远程登录以及其它安全网络服务。SSH仅仅是一协议标准,其具体的实现有很多,既有开源实现的OpenSSH,也有商业实现方案。使用范围最广泛的当然是开源实现OpenSSH。2.SSH工作原理 在讨论SSH的原理和使用前,我们需要分析一个问题:为什......
  • OpenCV图像连通区域分析(14)
    图像连通区域图像的连通域是指图像中具有相同像素值并且位置相邻的像素组成的区域,连通域分析是指在图像中寻找出彼此互相独立的连通域并将其标记出来。提取图像中不同的连通域是图像处理中较为常用的方法,例如在车牌识别、文字识别、目标检测等领域对感兴趣区域分割与识别。一般情况......
  • Codeforces Round #286 (Div. 1) B. Mr. Kitayuta's Technology (强连通分量)
    题目地址:http://codeforces.com/contest/506/problem/B先用强连通判环,然后转化成无向图,找无向图连通块,若一个有n个点的块内有强连通环,那么需要n条边,即正好首尾相连形成一条环,那么有了这个环之后,在这个块内的所有要求都能实现。如果没有强连通环,那么就是一棵树,那么只需要n-1条边即......
  • Codeforces Round #Pi (Div. 2) E. President and Roads (最短路+强连通求割边)
    题目地址:codeforces#pi(DIV2)E题目很水。。就是先求两边最短路,然后把可能为最短路的边挑出来,然后判断是否yes只需要转化成无向图跑一遍tarjan,找出割边,割边就是yes,然后剩下的边就让它的值为最短路-1就行了,如果-1后变成了非正数,就是no.但是!!!居然卡spfa!!那是不是说cf以后就不......
  • 【云原生 • Prometheus】图解Prometheus数据抓取原理
    【云原生•Prometheus】图解Prometheus数据抓取原理discovery模块利用各种服务发现协议发现目标采集点,并通过channel管道将最新发现的目标采集点信息实时同步给scrape模块,scrape模块负责使用http协议从目标采集点上抓取监控指标数据。如上图,discovery服务发现模块经过Discoverer......
  • 强连通分量 - Kosaraju Algorithm
    推荐在唯一官方原文阅读,但本文不是转载,是多平台发布。Kosaraju算法(akaKosaraju-Sharir算法)是一个求强连通分量的算法。其时间复杂度为\(O(n+m)\)(邻接表)或\(O(m^2)\)(邻接矩阵)。该算法相比Tarjan算法要更简单一些。(个人观点)本算法的基础是反图(也被称作逆图、转置图)。基本原理......
  • 31、图像连通域分析
    图像的连通域是指图像中具有相同像素值并且位置相邻的像素组成的区域,连通域分析是指在图像中寻找出彼此互相独立的连通域并将其标记出来。提取图像中不同的连通域是图像处理中较为常用的方法,例如在车牌识别、文字识别、目标检测等领域对感兴趣区域分割与识别。一般情况下,一个......