求割点与割边的算法

以下的讨论基于无向连通图。假设图G中点个数为n，边数为m

割点（Articulation Point）：去除该点后图变成非连通。

割边（Bridge, cut edge）：去除该边后图变成非连通。

首先考虑求割点的算法。

根据定义，首先想到的算法就是遍历图中所有的点，每次去除该点及对应的边，检测图是否连通（可用DFS或BFS）。该算法的时间复杂度为O(n*(n+m))

另外由Tarjan提出的算法的原理是：

对图作DFS遍历得到一棵树T，一个点u属于割点的充分必要条件是：

    1. u是T的根节点，也就是DFS访问的第一个点，并且u有至少两个孩子节点

    2. u是T中其它节点，u至少存在一个孩子节点v，通过v及其任何子树不能访问到u的任何祖先节点

其中，条件1很明显，也很容易编程实现；至于条件2，在DFS中，我们需要记录每个节点通过它的子节点能访问到的最早的节点。

为此，用一个数组d记录图中每个节点被DFS访问的顺序，另外一个数组low记录每个节点通过它的子节点能访问到的最早的节点，因此有：

low[u] = min(d[u], d[x] (x是通过u的子树能访问到的所有节点))

       = min (d[u],

                    d[v], (u, v)为后向边（返祖边），等价于d[v] < d[u]且在DFS生成树中不是u的父亲节点

                    low(v), (u, v)为树枝边（父子边），u是v的父亲节点

              )

因此，割点的充分必要条件即是：

    1. u是T的根节点，且u至少有两个孩子节点

    2. u不是T的根节点，(u, v)为树枝边（u为v在搜索树中的父亲），使得d[u] <= low[v]

如果图是用邻接表存储的话，时间复杂度是O(n+m)

对于割边的问题，基于同样的算法，一条边是割边的充分必要条件是：

    1. (u, v)是树枝边，u是v的父节点，low[v] > d[u]

最后，推荐一个不错的参考资料：slideshare-articulation