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. Its 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.

C a eo