论文部分内容阅读
摘要：由于传统朴素算法求解无向图的双连通分量时间花费过高，为了在线性时间内求出双连通分量并得到极大连通子图。文章对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 无向图的深度优先数 当无向图的各个结点的连接关系以及各个元素在数据结构中存储位置被确定时，这个无向图的DFS搜索树也就随之确定。每个结点在搜索树的位置和遍历的先后顺序也是固定不变的。为了记录各个结点遍历的顺序，引入全局变量dfs_clock时间戳，将其初始化为0。在DFS过程中，每当访问一个新的结点dfs_clock就自增。同时用数组dfs[n]存储每个结点被访问的先后顺序即深度优先数，深度优先数的数值越小结点被访问的时间越早。
图中的蓝色箭头为DFS递归访问的儿子结点的方向，淡黄色箭头为儿子结点到父亲结点的回溯方向。箭头上的数字编号是递归和回溯执行的顺序。从结点0开始进行DFS，每个结点的深度优先数存储在一维数组dfs[n]中并与数组的下标建立起映射关系。
2.3 无向图结点的回溯数组
通过观察图1和图2，我们可以知道：因为深度优先搜索树引入了回边，图2的连通性与图1是等价的，并且DFS遍历树还表示出了结点的子孙关系。考虑到图2传递的信息更多，因此应在图2的基础上对问题进行深入的研究。尝试删除深度优先遍历树的不同结点，再观察剩余结点的连通性和连通分量，可以发现关节点的判定依据和连通分量数量关系。
A1、A2、A3为三个连通区域，连通区域中可能包含若干个连通的结点。三个图中F为父亲结点，S1和S2为儿子结点。删除三个图中F结点及其与F结点相邻的边。A和C对比可以发现：C中F结点不是关节点，A和B中的F结点为关节点且A和B中均存在桥。由于C中两个子节点均存在连接祖先结点的回边，C中的F结点被删除后，整个图的连通性并未发生改变，相应的连通分量数目也未发生变化。相反地，由于A中两个子节点没有回边，F结点被删除后，整个图的连通性与连通分量发生了变化。
A、B、C三个图中F结点均有两个子结点且回边的数量依次增加，F结点被删除之后连通分量的数目依次减少。可以猜想：某个结点是否为关节点与儿子结点是否有连接祖先结点的回边有关，并且儿子结点回边的数量与删除父亲结点后的连通分量的数目有着一定的数量关系。不难验证：如果F结点只有一个子结点且唯一的子结点不存在回边。当F结点被删除后，连通分量数目必然增加，F显然是关节点。
通过对非根结点的分析，可以得出这样的结论：若非根结点F所有的子结点存在连接F的父亲结点的回边，那么F一定不是关节点;相反地，若F的所有的子结点中有一个儿子结点不存在回边，F结点就是割点。
当F为DFS搜索树的根结点时，若F有多个儿子结点，那么F结点被删除后连通分量的数目就会增加，此时F为关节点。显然当F只有一个儿子结点时，F被删除后连通分量的数目不变，依然为1。
经过以上所有的分析和討论，我们可以把F结点推广到所有结点。可以很清楚地发现，搜索树的结点可以分成根结点和非根结点。对于根结点，直接判断儿子结点的数量是否为1。非根结点的处理略有复杂，需要记录每个儿子结点所能连接的最小的深度优先数，然后与父亲结点的dfs[F]进行比较。这里需要用到一个回溯数组low[]，用于记录每个结点去除父亲结点所能连接的最小的深度优先数。如low[S]，表示S结点以及S的后代中所能连接的最小的深度优先数。用Si表示F结点的儿子结点，将low[Si]（i=0，1，2…）与dfs[F]进行比较，若存在一个子节点Si，使得low[Si]
关键词：极大连通子图;双连通分量;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 无向图的深度优先数 当无向图的各个结点的连接关系以及各个元素在数据结构中存储位置被确定时，这个无向图的DFS搜索树也就随之确定。每个结点在搜索树的位置和遍历的先后顺序也是固定不变的。为了记录各个结点遍历的顺序，引入全局变量dfs_clock时间戳，将其初始化为0。在DFS过程中，每当访问一个新的结点dfs_clock就自增。同时用数组dfs[n]存储每个结点被访问的先后顺序即深度优先数，深度优先数的数值越小结点被访问的时间越早。
图中的蓝色箭头为DFS递归访问的儿子结点的方向，淡黄色箭头为儿子结点到父亲结点的回溯方向。箭头上的数字编号是递归和回溯执行的顺序。从结点0开始进行DFS，每个结点的深度优先数存储在一维数组dfs[n]中并与数组的下标建立起映射关系。
2.3 无向图结点的回溯数组
通过观察图1和图2，我们可以知道：因为深度优先搜索树引入了回边，图2的连通性与图1是等价的，并且DFS遍历树还表示出了结点的子孙关系。考虑到图2传递的信息更多，因此应在图2的基础上对问题进行深入的研究。尝试删除深度优先遍历树的不同结点，再观察剩余结点的连通性和连通分量，可以发现关节点的判定依据和连通分量数量关系。
A1、A2、A3为三个连通区域，连通区域中可能包含若干个连通的结点。三个图中F为父亲结点，S1和S2为儿子结点。删除三个图中F结点及其与F结点相邻的边。A和C对比可以发现：C中F结点不是关节点，A和B中的F结点为关节点且A和B中均存在桥。由于C中两个子节点均存在连接祖先结点的回边，C中的F结点被删除后，整个图的连通性并未发生改变，相应的连通分量数目也未发生变化。相反地，由于A中两个子节点没有回边，F结点被删除后，整个图的连通性与连通分量发生了变化。
A、B、C三个图中F结点均有两个子结点且回边的数量依次增加，F结点被删除之后连通分量的数目依次减少。可以猜想：某个结点是否为关节点与儿子结点是否有连接祖先结点的回边有关，并且儿子结点回边的数量与删除父亲结点后的连通分量的数目有着一定的数量关系。不难验证：如果F结点只有一个子结点且唯一的子结点不存在回边。当F结点被删除后，连通分量数目必然增加，F显然是关节点。
通过对非根结点的分析，可以得出这样的结论：若非根结点F所有的子结点存在连接F的父亲结点的回边，那么F一定不是关节点;相反地，若F的所有的子结点中有一个儿子结点不存在回边，F结点就是割点。
当F为DFS搜索树的根结点时，若F有多个儿子结点，那么F结点被删除后连通分量的数目就会增加，此时F为关节点。显然当F只有一个儿子结点时，F被删除后连通分量的数目不变，依然为1。
经过以上所有的分析和討论，我们可以把F结点推广到所有结点。可以很清楚地发现，搜索树的结点可以分成根结点和非根结点。对于根结点，直接判断儿子结点的数量是否为1。非根结点的处理略有复杂，需要记录每个儿子结点所能连接的最小的深度优先数，然后与父亲结点的dfs[F]进行比较。这里需要用到一个回溯数组low[]，用于记录每个结点去除父亲结点所能连接的最小的深度优先数。如low[S]，表示S结点以及S的后代中所能连接的最小的深度优先数。用Si表示F结点的儿子结点，将low[Si]（i=0，1，2…）与dfs[F]进行比较，若存在一个子节点Si，使得low[Si]