求无向连通图的割点(图论)

求无向连通图的割点(图论)

1. 割点与连通度

在无向连通图中，删除一个顶点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 被分割成两个连通分量。

2. 求割点的方法

暴力的方法：

依次删除每一个节点v用DFS（或BFS）判断还是否连通再把节点v加入图中

V V次DFS，时间复杂度为O(V∗(V+E)) O(V∗(V+E))。（题外话：有人在面试实习的时候，只想到暴力方法；面试官提示只要一次DFS就就可以找到割点，就是当时死活都没想出来）。

有关DFS搜索树的概念

在介绍算法之前，先介绍几个基本概念

DFS搜索树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树，如图(b)所示。树边：（在[2]中称为父子边），在搜索树中的实线所示，可理解为在DFS过程中访问未访问节点时所经过的边。回边：（在[2]中称为返祖边、后向边），在搜索树中的虚线所示，可理解为在DFS过程中遇到已访问节点时所经过的边。

基于DFS的算法

该算法是R.Tarjan发明的。观察DFS搜索树，我们可以发现有两类节点可以成为割点：

对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；对非叶子节点u（非根节点），若其子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。

对于根结点，显然很好处理；但是对于非叶子节点，怎么去判断有没有回边是一个值得深思的问题。

​​dfn[u]​​记录节点u在DFS过程中被遍历到的次序号，​​low[u]​​记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小），那么low[u]的计算过程如下：

下表给出图(a)对应的dfn与low数组值。

​​low[v] >= dfn[u]​​时，节点u才为割点。该式子的含义：以节点v为根的子树所能追溯到最早的祖先节点要么为v要么为u。

代码实现:

void dfs(int u) { //记录dfs遍历次序 static int counter = 0; //记录节点u的子树数 int children = 0; ArcNode *p = graph[u].firstArc; visit[u] = 1; //初始化dfn与low dfn[u] = low[u] = ++counter; for(; p != NULL; p = p->next) { int v = p->adjvex; //节点v未被访问，则(u,v)为树边 if(!visit[v]) { children++; parent[v] = u; dfs(v); low[u] = min(low[u], low[v]); //case (1) if(parent[u] == NIL && children > 1) { printf("articulation point: %d\n", u); } //case (2) if(parent[u] != NIL && low[v] >= dfn[u]) { printf("articulation point: %d\n", u); } } //节点v已访问，则(u,v)为回边 else if(v != parent[u]) { low[u] = min(low[u], dfn[v]); } }}

采用邻接表存储图，该算法的时间复杂度应与DFS相同，为

O(V+E) O(V+E) 。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。