检查在图中删除一条边是否会导致图分裂。

Question

我有一个图结构，在满足一定条件的情况下逐步删除边。我想知道如何高效地检测删除一条边是否会导致图分裂成两个或更多的子图，但是我的头脑已经完全停滞了。

暴力解决方案是进行广度优先搜索(BFS)，直到可以从任意节点到达所有节点，但对于大型图来说，这将耗费太多时间...

你有什么好的想法吗？

编辑：经过一番搜索后，似乎我正在尝试做的与弗洛伊德算法非常相似，需要找出一条边是否是“桥”。

- Milan

---

你为什么要一条接一条地删除边缘？许多算法会一次删除一条边来完成其他任务。也许有更简单的方法来实现你想要的结果？ - Marius

Answer 1

在移除后使得图形不连通的边称为 '桥梁'。您可以通过对整个图进行单次深度优先搜索，在O（|V|+|E|）中找到它们。相关算法找到所有 '关节点'（如果删除，则使图形断开连接的节点）。连接两个关节点之间的任何边都是一个桥梁（您可以在所有边的第二遍遍历中测试它）。

//
// g: graph; v: current vertex id; 
// r_p: parents (r/w); r_a: ascents (r/w); r_ap: art. points, bool array (r/w)
// n_v: bfs order-of-visit 
//
void dfs_art_i(graph *g, int v, int *r_p, int *r_v, int *r_a, int *r_ap, int *n_v) {
    int i;
    r_v[v] = *n_v;
    r_a[v] = *n_v;
    (*n_v) ++;

    // printf("entering %d (nv = %d)\n", v, *n_v);
    for (i=0; i<g->vertices[v].n_edges; i++) {
        int w = g->vertices[v].edges[i].target;
        // printf("\t evaluating %d->%d: ", v, w);
        if (r_v[w] == -1) {    
            // printf("...\n");
            // This is the first time we find this vertex
            r_p[w] = v;
            dfs_art_i(g, w, r_p, r_v, r_a, r_ap, n_v);
            // printf("\n\t ... back in %d->%d", v, w);
            if (r_a[w] >= r_v[v]) {
                // printf(" - a[%d] %d >= v[%d] %d", w, r_a[w], v, r_v[v]);
                // Articulation point found
                r_ap[i] = 1;
            }
            if (r_a[w] < r_a[v]) {
                // printf(" - a[%d] %d < a[%d] %d", w, r_a[w], v, r_a[v]);
                r_a[v] = r_a[w];
            }
            // printf("\n");
        }
        else {
            // printf("back");
            // We have already found this vertex before
            if (r_v[w] < r_a[v]) {
                // printf(" - updating ascent to %d", r_v[w]);
                r_a[v] = r_v[w];
            }
            // printf("\n");
        }
    }
}

int dfs_art(graph *g, int root, int *r_p, int *r_v, int *r_a, int *r_ap) {
    int i, n_visited = 0, n_root_children = 0;
    for (i=0; i<g->n_vertices; i++) {
        r_p[i] = r_v[i] = r_a[i] = -1;
        r_ap[i] = 0;
    }
    dfs_art_i(g, root, r_p, r_v, r_a, r_ap, &n_visitados);    

    // the root can only be an AP if it has more than 1 child
    for (i=0; i<g->n_vertices; i++) {
        if (r_p[i] == root) {
            n_root_children ++;
        }
    }
    r_ap[root] = n_root_children > 1 ? 1 : 0;
    return 1;
}

- tucuxi

Answer 2

你如何选择要删除的边呢？ 能否详细介绍一下你的问题领域？

你的图有多大呢？也许BFS就足够了！

在你写道你正在尝试找出一条边是否是桥时，我建议你按它们的介数度量值递减顺序删除边。

实际上，介数是衡量图中边（或顶点）中心性的一种度量。具有更高介数值的边具有更大的潜力成为图中的桥。

在网上查找，这个算法被称为“Girvan-Newman算法”。

- Vitaliy

Answer 3

如果您删除顶点A和B之间的链接，难道您不能在边缘删除后检查是否仍然可以从B到达A吗？这比从随机节点到达所有节点要好一些。

- John Kugelman