PsuedoCode

A bridge (sometimes called a cut edge) is an edge in a graph whose removal increases the number of components of the graph. A bridge might represent a critical link in a network or transportation network that would harm the entire system if it went down or were attacked. Edge (c, d) in the graph below is a bridge Notably, it can be shown that an edge in a graph is a bridge if and only if it does not belong to a cycle 1. Describe pseudocode for an algorithm that returns all bridges in a given graph Hint: you will want to modify DFS so that it marks all edges that belong to cycles. It's much easier to base this algorithm on a non-recursive Stack based) DFS than BFS or recursive DFS. Every non-tree-edge in a DFS (or BFS) traversal defines a cycle of the graph, so all you need to do is to mark the edges that belong to this cycle when you encounter a non- tree-edge of the traversal tree. Pseudocode for a stack-based DFS appears below