寻找无向图中的割点(边)-Tarjan 算法

date
Jan 30, 2022
slug
图算法在表格行恢复中的应用
status
Published
tags
Algorithm
Graph
OCR
summary
图算法在表格行恢复中的应用
type
Post

问题定义

在无向连通图中,如果删除某个顶点后,图不再连通,则称这样的顶点为割点(Articulation Points or Cut Vertices)。如果在连通图上至少删掉 k 个顶点才能破坏图的连通性,则称改连通图的连通度为 k。下面是几个带有割点的图的示例:

暴力算法

最暴力的方法是一次移除连通图中的节点,判断移除后的图是否连通。对每一个节点的操作流程如下:
  1. 从连通图中移除节点 u
  1. 判断剩下的节点之间是否相连(用 BFS 或者 DFS 遍历)
  1. 把 v 加回到连通图中
假设一个连通图有 V 个节点,E 条边,并且使用 adjacency list 来表示连通图,则时间复杂度为

Tarjan 算法

在 DFS tree 中判断一个节点 u 是否是割点,可以通过以下两个条件判断:
  1. u 是根节点,并且有至少两个子节点,则 u 是一个割点
  1. u 不是根节点,以 u 为分界,图可以分为两部分,一部分是已经访问过的节点,一部分是没有被访问过的节点,在没有被访问过的节点中至少有一个点在不经过 u 的情况下,无法回到已经访问过的点
  1. 叶子节点肯定不是割点
条件 1 很好判断,对于判断条件 2,我们需要维护两个数组,一个用来保存每个节点被遍历到的次序,记为 disc ,另一个保存所有节点,在不通过父节点的情况下能够访问到的最早的节点次序,记该数组为 low ,那么如果满足 low[v] >= disc[u] (v 最早只能访问到在 u 之后被访问到的节点)则说明节点 u 为割点。该条件如果把 = 号去掉,即可用来判断割边,因为 low[v] > disc[u] 时,表示 v 无法回到 u,此时 (u,v) 即表示一条割边,注意割边的判断无需要关心 u 是否为根节点。
GeeksforGeeks 中有完整的可执行代码,visualgo 上可以看到整个 DFS 的可视化过程。下面的示例割点为 [1, 3, 4],割边为 [(0,1), (3,4)]
notion image

实际应用-表格行结构恢复

在表格行恢复问题中,需要判断两个文本框是否为同一行,相当于对所有两两组合的文本框关系进行二分类,这部分的网络结合了 LayoutXLMStrucText 的关系分支,以后有机会可以再单独写一篇。
测试中发现,即使模型预测的 f1 很高,但还是免不了会出现某一行的某个节点和其它行的某个节点有关系,导致两行被合并,如下图,第一行和第二行合并了,第四行和第五行合并了。
Before Tarjan
Before Tarjan
以下为使用了 Tarjan 算法后的效果,每一行都明确的分开了。
After Tarjan
After Tarjan
参考:
【图论】求无向连通图的割点
在无向连通图中,删除一个顶点v及其相连的边后,原图从一个连通分量变成了两个或多个连通分量,则称顶点v为割点,同时也称关节点(Articulation Point)。一个没有关节点的连通图称为重连通图(biconnected graph)。若在连通图上至少删去k 个顶点才能破坏图的连通性,则称此图的连通度为k。 关节点和重连通图在实际中较多应用。显然,一个表示通信网络的图的连通度越高,其系统越可靠,无论是哪一个站点出现故障或遭到外界破坏,都不影响系统的正常工作;又如,一个航空网若是重连通的,则当某条航线因天气等某种原因关闭时,旅客仍可从别的航线绕道而行;再如,若将大规模的集成电路的关键线路设计成重连通的话,则在某些元件失效的情况下,整个片子的功能不受影响,反之,在战争中,若要摧毁敌方的运输线,仅需破坏其运输网中的关节点即可。 (a)中G7 是连通图,但不是重连通图。图中有三个关节点A、B 和G 。若删去顶点B 以及所有依附顶点B 的边,G7 就被分割成三个连通分量{A、C、F、L、M、J}、{G、H、I、K}和{D、E}。类似地,若删去顶点A 或G 以及所依附于它们的边,则G7 被分割成两个连通分量。 暴力的方法: 若用邻接表(adjacency list),需要做\(V\)次DFS,时间复杂度为\(O(V*(V+E))\)。(题外话:我在面试实习的时候,只想到暴力方法;面试官提示只要一次DFS就就可以找到割点,当时死活都没想出来)。 在介绍算法之前,先介绍几个基本概念 DFS搜索树:用DFS对图进行遍历时,按照遍历次序的不同,我们可以得到一棵DFS搜索树,如图(b)所示。 树边:(在[2]中称为父子边),在搜索树中的实线所示,可理解为在DFS过程中访问未访问节点时所经过的边。 回边:(在[2]中称为返祖边、后向边),在搜索树中的虚线所示,可理解为在DFS过程中遇到已访问节点时所经过的边。 该算法是R.Tarjan发明的。观察DFS搜索树,我们可以发现有两类节点可以成为割点: 对根节点u,若其有两棵或两棵以上的子树,则该根结点u为割点; 对非叶子节点u(非根节点),若其子树的节点均没有指向u的祖先节点的回边,说明删除u之后,根结点与u的子树的节点不再连通;则节点u为割点。 对于根结点,显然很好处理;但是对于非叶子节点,怎么去判断有没有回边是一个值得深思的问题。 我们用 dfn[u]记录节点u在DFS过程中被遍历到的次序号, low[u] 记录节点u或u的子树通过非父子边追溯到最早的祖先节点(即DFS次序号最小),那么low[u]的计算过程如下: \[low[u] = \left \{ { \matrix { { \min \{ low[u],\ low[v]\} } & {(u,v)为树边} \cr { \min \{ low[u],\ dfn[v]\} } & {(u,v)为回边且v不为u的父亲节点} \cr } } \right.

© PanicByte 2021 - 2022