算法简介:求图的割边
算法简介
图割边
相关概念
- 连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图.
- 图的割点:如果去掉一个点以及与它连接的边,该点原来所在的图被分成两部分(不连通),则称该点为割点.
- 图的割边:在一个无向连通图中,如果删掉某条边后,该图不在连通,则称该边为割边.
相关算法
代码示例图
-
原图
-
深度遍历示意图
1. tarjan算法
* 时间复杂度:
- 深度优先遍历或广度优先遍历:O(N(N+M))
- tarjan算法:
用邻接矩阵存储:O(N^2)
用邻接表存储:O(N+M)
* 算法特点:
- 需要用DFS遍历图的所有顶点,记录num[顶点编号] = 顶点深度遍历时间戳
- 当遍历到顶点u时,枚举顶点u的所有出边,比如v,如何知道v不经过父节点u能否回到祖先节点呢?对子节点v再次DFS
- 需要记录每个子节点v在不经过父节点u的情况下,能够回到的最小时间戳(若存在v的父节点不止u一个的情况下):lows[v] = min(lows[v],nums[f])
- v回溯的时候获取当前节点的最小时间戳low[u]=min(low[u],low[v]),如果low[v]>=num[u],表示v不能不经过u回到祖先,即u为割点,如果low[v]>num[u],表示v不经过u,也没有其他的父节点,即u<->v是割边