图的关节点问题

基本概念

假如删除顶点 v 以及与 v 相关联的各边之后，将图的一个连通分量分割成两个或者更多的连通分量，则称顶点 v 为该图的一个关节点。
一个没有关节点的连通图称为重连通图，显然，在重连通图中，任意两个顶点之间至少存在两条路径，那么在删去某个顶点以及依附于该顶点的边时不会破坏图的连通性。
如果在连通图中至少删去 k 个顶点才会破坏图的连通性，则称此图的连通度为 k。

关节点和重连通图在实际中有较多应用，一个简单的例子，一个表示通信网的图的连通度越高，系统就越可靠，当某个站点出现故障或遭到破坏时，不会影响整个系统的工作。

求解原理

利用深度优先搜索便可求的图的关节点，并由此判断图是否是重连通的。

从图 G 的一个顶点 A 出发，通过深度优先遍历建立深度优先生成树，显然生成树中的边是原来图 G 中边的一部分，称其为树边，而除去树边剩余的边称为回边。

于是，对于树中任一顶点 v 而言，其孩子节点是在它之后搜索到的邻接点，而其双亲节点和由回边连接的祖先节点是在它之前搜索到的邻接点。

因此，由深度优先生成树可以总结出两类关节点的特性，进而求解关节点：

（1）如果生成树的根 r 有两棵或两棵以上的子树，那么该根顶点 r 是关节点；
（2）如果生成树的某非叶子顶点 v，它的某棵子树的根和子树的其他节点均没有指向 v 的祖先的回边，那么该顶点 v 是关节点。

具体操作

结合图本身的结构，使用一个数组来记录各个顶点访问顺序，通过判断访问顺序的前后关系来判断关节点。

修改 visited 数组为深度优先搜索遍历连通图时访问节点的顺序编号；

定义数组 low，用于表示当前节点 v 、后代节点（递归定义，包含后代的后代和回边连接的祖先） w+ 和回边连接祖先节点 k 的遍历顺序号的最小值，即

low[v] = Min { visited[v], low[w], visited[k] }，

其中 w 是顶点 v 在深度优先生成树上的孩子节点；k 是顶点 v 在深度优先生成树上由回边连接的祖先节点；(v, w) ∈ E(G)；(v, k) ∈ E(G)。

于是，

根据前面求解关节点（2）判定非叶节点是否为关节点：

对于某个顶点 v，若存在孩子节点 w，并且 low[w] ≥ visited[v] 时，则可以判定 v 是关节点，因为 low[w] ≥ visited[v] 表示 v 的后代 w 及其后代没有指回祖先的回边，那么一旦删除节点 v，后代 w 及其后代将独立称为一个连通分量，故判定 v 是关节点。

其中，visited[v] 是顶点 v 在深度优先生成树的前序序列编号，只需要增加计数变量并赋值给 visited[v] 即可；

low[v] 可以在深度优先生成树的后序遍历过程中求得，而后序序列中的次序恰好和递归退出 DFS 函数次序一致，因此可修改深度优先搜索，递归调用推出时计算 low[v]。

根据前面求解关节点（1）判定根节点是否为关节点：

深度优先搜索从根节点的一支返回时，根据计数变量，判断是否还有节点没有访问，如果有，则说明根节点至少有两棵子树，即根顶点有至少两个邻接点，于是可以判定根顶点为关节点。

代码实现（邻接表）

递归判断非叶节点中的关节点

// 深度优先搜索求关节点
void DFSArticul(ALGraph *G, int i, int *c, int *visited, int *low)
{
    visited[i] = ++(*c);
    int w, minv = visited[i]; // min{visited[i], low[w], visited[k]}
    ArcNode *p = G->vertices[i].firstarc;
    while (p) // 遍历 i 所有邻接点（孩子）计算 low[i]
    {
        w = p->adjvex; // 邻接点 w
        // w 未访问，是 i 的孩子
        if (0 == visited[w])
        {
            // 判断 w 为根的子树是否有回边
            DFSArticul(G, w, c, visited, low); // 计算 low[w]
            if (low[w] < minv) minv = low[w]; // w 子树中有回边
            // 指回双亲也当作回边不做区分，因此取等于
            if (low[w] >= visited[i]) printf("(%d)%c", i, G->vertices[i].data);
        }
        // w 已访问，说明这是条回边 visited[k]
        // 指回双亲也当作回边，但是不影响判断关键点，因此不做区分
        else if (minv > visited[w])
        {
            minv = visited[w];
        }
        p = p->nextarc;
    }
    low[i] = minv; // 计算 low[i]
}

从一支递归返回后再判断根节点是否关节点，完成所有关节点的判断

// 求关节点
void FindArticul(ALGraph *G)
{
    int w, c = 1, visited[MAX_VERTEX_NUM] = {0}, low[MAX_VERTEX_NUM];
    // 初始化 visited[0]
    visited[0] = 1; low[0] = 1; // 选取 0 作为根出发
    // 深度优先
    ArcNode *p = G->vertices[0].firstarc;
    w = p->adjvex; // 邻接点
    DFSArticul(G, w, &c, visited, low);
    // 判断根节点是不是关节点（子树个数）
    // 从根 0 的一个邻接点（孩子）出发深度遍历
    // 若返回时仍有节点没有访问
    // 说明根节点至少两棵子树，需要从根的另个邻接点（孩子）出发进行遍历
    // 可判定为关节点

    if (c < G->vexnum)
    {
        printf("(0)%c", G->vertices[0].data);
        p = p->nextarc;
        while(p)
        {
            w = p->adjvex; // 邻接点
            if (0 == visited[w]) DFSArticul(G, w, &c, visited, low);
            p = p->nextarc;
        }
    }
}

完整代码可参见：GitHub

DONE！

上篇: 使用 Travis CI 自动部署 Hexo 下篇: 图的最小生成树

基本概念
求解原理
具体操作
代码实现（邻接表）