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

Question

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 way 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.

Answer 1

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'.

Answer 2

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.