Reputation: 1056
How do you find out whether an undirected graph is Biconnected or not using its depth first search traversal. Is there any other way than traversing the whole graph to find disconnected pieces of the graph.
Upvotes: 1
Views: 1119
Reputation: 45575
You calculate the low(v)
for every vertex in linear time (i.e. during the execution of the DFS). And there exists a bridge (i.e. an edge whose removal will disconnect the graph ==> not biconnected) iff there's a non-root vertex whose low
value is itself OR if the root has more than one child.
It's explained here on point 5.2 http://www.cse.ohio-state.edu/~lai/780/graph.pdf
Upvotes: 3
Reputation: 3586
I have no answer to this, but my gut feeling would suggest that you would have to do the depth first search traversal as the biconnected property of the graph is a property of the whole graph and not any subset of the graph.
Upvotes: 2