Let G = (V, E) be an undirected, connected graph. A vertex u E Vis bridge vertex

Question

Let G = (V, E) be an undirected, connected graph. A vertex u E Vis bridge vertex if removal of v (and edges incident on v) makes the graph disconnected. Suppose that v EV be a bridge vertex. Is there a vertex u E V such that if we perform DFS on G starting at u, the vertex v will be a leaf node in the resulting DFS tree? Given an O(m+n)-time algorithm that gets a graph G (which is undirected and con nected) as input and outputs a vertex v that is not a bridge vertex. Describe your algorithm, derive the time bound, prove the correctness of your algorithm.

Explanation / Answer

            BRIDGE(G):

            Compute DFS(G)

            Traverse DFS tree to find bridge vertex:

                        For all u in DFS(G):

                                    For all v adjacent (u)

                                                Check if subtree rooted at v has a connection to one of the ancestors of u

                                                            If yes then u is not a bridge

                                                Otherwise

                                                            u is a bridge vertex

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.