CODEWITHSUNDEEP
algorithmgraph
Atishay
Atishay

Reputation: 1056

Biconnected Graph

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

Answers (2)

davin
davin

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

Brett Walker
Brett Walker

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

Related Questions