付海奎 陈国军 王文波

摘要：由于传统朴素算法求解无向图的双连通分量时间花费过高，为了在线性时间内求出双连通分量并得到极大连通子图。文章对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））]，均为平方阶。朴素算法求解无向图的桥和关节点时间花费太高。应寻求一种新的算法，在线性时间内求出最优解。算法最理想的状态是对无向图DFS一次，可求出所有桥和关节点。此时的时间花费最低，时间复杂度[1]为[O（N+E）]。

Robert Endre Tarjan（美国计算机科学家、1986年图灵奖得主）[2]提出了关于求解有向图的强连通分量的Tarjan算法。考虑到无向图是有向图的特殊情形，当有向图中相连的两个点之间存在往返的路径时，有向图可转化为无向图。由此可以得出无向图的线性Tarjan算法。本篇文章在有向图的基础上，引入了无向图的回溯数组。通过图形动态描述了DFS过程中low数组的更新情况，并对回溯过程中每个结点的low值更新进行了详细的叙述。对于割点的判断，从根节点和非根结点两个维度出发，系统论证了割点的判断依据。最后具体分析了在入栈和出栈操作中，每个双连通分量对应的极大连通子图的求解过程。

2 Tarjan算法的思想和基本理论

Tarjan算法采用DFS遍历整个无向图，通过对DFS搜索树的分析和研究。引入了时间戳即深度优先数和用于记录搜索树中每个结点深度优先数的回溯数组。回溯数组记录的深度优先数是该结点所能连接的最小的深度优先数。回溯数组是通过递归初始化，然后回溯更新的方式确定下来的。在递归访问结点的过程中，将遍历的结点依次入栈。回溯结点时，将栈中的元素循环出栈，直到遇到割点则跳出循环。而每次出栈的元素，刚好对应关节点的一个极大点连通子图。为了使算法容易理解，本篇文章将父子结点对应的边入栈。

2.1 无向图的实例

为了后续算法的具体实现和问题讨论的方便，这里不考虑独立点和非连通图。选定了0～6共7个顶点8条边作为无向图的研究对象，顶点之间的连接关系如下图所示。

图1展示了7个顶点8条边的无向图连接平面图[3]。对图1中的无向图，从顶点0开始进行一次深度优先遍历，得到相应的DFS遍历树。无向图的搜索树主要有两种边，顶点之间的实线为无向图的树边（tree edge），虚线为无向图的回边（back edge）。每次访问新的结点即父亲结点到儿子节点的连接都会产生一条树边。回边一方面为了表示已被访问过的子孙结点与祖先结点的连接关系，另一方面将平面图各个结点之间的连通关系体现出来。

2.2 无向图的深度优先数