检查是否删除图中的边将导致图拆分

Question

我有一个图形结构，我逐个删除边，直到满足某些条件。我的大脑已经完全停下来，我无法找到一种有效的方法来检测删除边缘是否会导致我的图形在两个或多个图形中分裂。

的暴力破解的办法是做一个BFS直到一个能达到从一个随机节点的所有节点，但这需要太多的时间与大图...

任何想法？

编辑：经过一番搜索，似乎我想要做的是非常相似的fleury的算法，我需要找到一个边缘是否是一个“桥梁”。

Answer 1

如何选择要去除的边缘？ 你能告诉我更多关于你的问题域吗？

你的图形有多大？也许BFS就好了！

写完之后，您试图找出边缘是否为网桥，我建议您使用度数度量的递减顺序删除边缘。

基本上，介于度是图中边（或顶点）中心性的度量。 具有更高中间值的边缘有更大的潜力成为图中的桥梁。

查看它在网络上的算法被称为'Girvan-Newman algorithm'。

Answer 2

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

Answer 3

移除时断开图形的边缘称为'bridges'。你可以在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; 
}