tarjan算法
2021-06-08 09:05
标签：强连通分量 step 算法 顺序 最小值 深搜 tar 出现 节点 求强连通/割点/桥 将图深搜，形成深搜树，按遍历顺序标号->dfn[i] 将low[i]初始化为dfn[i] 回溯时low[i]=min(low[i],low[i的儿子]) DFN［］作为这个点搜索的次序编号（时间戳） LOW［］作为每个点在这颗树中的，子树根编号的最小值 如果找到DFN［］＝＝LOW［］就说明这个节点是这个强连通分量的根节点（毕竟这个LOW［］值是这个强连通分量里最小的。） 在深搜树中，如果对于某个点u，与它相连的点v（v不是u的父亲）。 如果 low[v]>=dfn[u] , 那么也就是以v为根的深搜子树中的点所连接的点没有已经标记时间戳的。 也就是以v为根的子树是封闭的，那么一旦去掉点u,这棵子树中的点就称为了一个新的连通分量。 那么点u就是割点了。 若边 e （其对应的两个节点分别为 u 与 v）dfn[u]
我们发现从v节点出发,在不经过(u, v)的前提下,不管走哪一条边, 我们都无法抵达u节点,或者比u节点更早出现的节点, 此时我们发现v所在的子树似乎形成了一个封闭圈,那么(u, v)自然也就是桥了。 桥的两端一定是割点 tarjan算法 标签：强连通分量 step 算法 顺序 最小值 深搜 tar 出现 节点 原文地址：https://www.cnblogs.com/zhangshaojia/p/14531875.htmlstep1
step2
step3
判断
有向图中
无向图中
下一篇：C++优化列表