CODEWITHSUNDEEP
algorithmgraphdepth-first-search
Jake
Jake

Reputation: 16837

Is every bridge in a graph an edge in DFS search tree?

A question from Skiena's book of algorithm:

Suppose G is a connected undirected graph. An edge e whose removal disconnects the graph is called a bridge. Must every bridge e be an edge in a depth-first search tree of G?

My solution so far (need suggestions):

I think that the bridge is an edge whose end vertex is a cut node, because cut node removal disconnects the graph so removing that edge will also disconnect the graph. Edges in DFS search tree are tree edges & back edges, and only tree edges can be cut edges ( or bridges ) because back edge removal doesn't disconnect the graph.

Upvotes: 5

Views: 3690

Answers (1)

jpalecek
jpalecek

Reputation: 47762

Basically, yes. I have some remarks though:

I think that the bridge is an edge whose end vertex is a cut node, because cut node removal disconnects the graph so removing that edge will also disconnect the graph.

This is not exact. Particularly, if you read it as (bridge => edge has a cut node), that is true. But phrased as "a bridge is an edge whose end vertex...", it suggests the converse implication, which is not true. All in all, this sentence is largely irrelevant for the rest of the argument and I'd just omit it.

... only tree edges can be cut edges ( or bridges ) because back edge removal doesn't disconnect the graph.

Yeah, that's it. Plus you have to note that DFS explores all vertices (or labels all edges) of a connected graph.

Upvotes: 4

Related Questions