Checking if removing an edge in a graph will result in the graph splitting

I have a graph structure where I am removing edges one by one until some conditions are met. My brain has totally stopped and i can't find an efficient wa开发者_Go百科y to detect if removing an edge will result in my graph splitting in two or more graphs.

The bruteforce solution would be to do an bfs until one can reach all the nodes from a random node, but that will take too much time with large graphs...

Any ideas?

Edit: After a bit of search it seems what I am trying to do is very similar to the fleury's algorithm, where I need to find if an edge is a "bridge" or not.

---

Edges that make a graph disconnected when removed are called 'bridges'. You can find them in O(|V|+|E|) with a single depth-first search over the whole graph. A related algorithm finds all 'articulation points' (nodes that, if removed, makes the graph disconnected) follows. Any edge between two articulation-points is a bridge (you can test that in a second pass over all edges).

//
// 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;
}

---

If you remove the link between vertices A and B, can't you just check that you can still reach A from B after the edge removal? That's a little better than getting to all nodes from a random node.

---

How do you choose the edges to be removed? Can you tell more about your problem domain?

Just how large Is your graph? maybe BFS is just fine!

After you wrote that you are trying to find out whether an edge is a bridge or not, I suggest you remove edges in decreasing order of their betweenness measure.

Essentially, betweenness is a measure of an edges (or vertices) centrality in a graph. Edges with higher value of betweenness have greater potential of being a bridge in a graph.

Look it up on the web, the algorithm is called 'Girvan-Newman algorithm'.