APP下载

基于Tarjan算法的极大点连通子图研究

2021-09-14付海奎陈国军王文波

电脑知识与技术 2021年22期

付海奎 陈国军 王文波

摘要:由于传统朴素算法求解无向图的双连通分量时间花费过高,为了在线性时间内求出双连通分量并得到极大连通子图。文章对Tarjan算法的思想以及具体实现做出了详细的分析。同时结合具体实例,验证了算法中割点的判定条件以及回溯数组初始化的有效性和适用性。最后,给出了Tarjan算法在求解极大连通子图过程中,结点和栈空间状态转化图。

关键词:极大连通子图;双连通分量;Tarjan算法

Abstract: Because the traditional naive algorithm takes too much time to solve the biconnected component of undirected graph, in order to find the biconnected component in linear time and obtain the maximally connected subgraph. The idea and implementation of Tarjan algorithm are analyzed in detail in this paper. At the same time, the validity and applicability of the decision condition of the cut point and the initialization of the backtracking array in the algorithm are verified by a concrete example. Finally, the state transition diagrams of node and stack space in the process of solving the maximally connected subgraphs of Tarjan algorithm are given.

Key words: Maximally Connected Subgraphs; Biconnected Component; Tarjan Algorithm

1 問题概述与分析

对于连通的无向图(undirected graph),若删除某个顶点或者某条边,无向图的连通性变得未知。如果只删除无向图中某条边,无向图的连通性和连通分量(connected component)发生改变,那么删除的这条边为无向图的桥。若一个无向图中不存在桥,这个无向图为边双连通图(edge-biconnected graph)。对于点双连通图,条件则更强一些。当顶点被删除时,与顶点相邻的边也要被删除。其中一个顶点被删除后,无向图的连通分量发生变化,该顶点为关节点(articulation vertex)。

在传统朴素算法中,寻找无向图中所有的桥和关节点需要多次DFS[1](depth-first search)。一次DFS可以求出无向图的连通分量,而每次DFS的渐近时间复杂度为[T(n)=O(N+E)],其中[N]为无向图的顶点数,[E]为无向图的边数。每次删除无向图中一条边再进行DFS,即可求出删除一条边后的连通分量。同理可以得出,对顶点进行相同的若干次删除操作,可求出无向图中所有的关节点。而两者的渐近时间复杂度分别为[O(E×(N+E))], [O(N×(N+E))],均为平方阶。朴素算法求解无向图的桥和关节点时间花费太高。……

登录APP查看全文