Bridges Search

• Input: undirected graph with N nodes and M edges
• Output: array bridges of graph bridges
• Time complexity: $O(N + M)$

Bridge - is an edge of a graph whose deletion increases the graph's number of connected components

Description

Pick an arbitrary node as source_node and run depth first search from it.

Let's say we are in the DFS, looking through the edges starting from node u. The current edge (u, v) is a bridge if and only if none of the nodes v with its descendants in the DFS traversal tree has a back-edge to node u or any of its ancestors. This condition means that there is no other way from u to v except for edge (u, v).

Let entry_time[u] denote DFS entry time for node u.

Let lowpoint[u] denote the lowest entry time of neighbors of all descendants of u (including u itself) in the DFS tree.

$$ \operatorname{lowpoint[u]} = \operatorname{min} \begin{cases} \operatorname{entry\_time[u]}\\ \operatorname{entry\_time[p]} & \forall \text{ back-edge } (u, p)\\ \operatorname{lowpoint[v]} & \forall \text{ DFS edge } (u, v) \end{cases} $$

Now, there is a back edge from node u or one of its descendants to one of its ancestors if and only if node u has a child v for which lowpoint[v] $\leq$ entry_time[u]. If lowpoint[v] = entry_time[u], the back edge comes directly to u, otherwise it comes to one of the ancestors of u.

Thus, the current edge (u, v) in the DFS tree is a bridge if and only if lowpoint[v] > entry_time[u].

Example

Let's see how the Bridges Search algorithm works with an example. We use an undirected graph with 7 nodes.

Bridges Search algorithm starts from node 1 and set visited[1] = 1, entry_time[1] = 0, lowpoint[1] = 0, timer = 1.

Bridges Search moves to node 2 and set visited[2] = 1, entry_time[2] = 1, lowpoint[2] = 1, timer = 2.

Bridges Search moves to node 3 and set visited[3] = 1, entry_time[3] = 2, lowpoint[3] = 2, timer = 3.

Bridges Search moves to node 4 and set visited[4] = 1, entry_time[4] = 3, lowpoint[4] = 3, timer = 4.

Bridges Search moves to node 7 and set visited[7] = 1, entry_time[7] = 4, lowpoint[7] = 4, timer = 5.

Bridges Search backtrack from node 7 to node 4. Since lowpoint[7] = 4 > 3 = entry_time[4], Bridges Search marks edge (4, 7) as a bridge.

Considering edge (4, 1) Bridges Search update lowpoint[4] = 0.

Bridges Search backtrack from node 4 to node 3 and set lowpoint[3] = 0.

Bridges Search moves to node 6 and set visited[6] = 1, entry_time[6] = 5, lowpoint[6] = 5, timer = 6.

Bridges Search backtrack from node 6 to node 3. Since lowpoint[6] = 5 > 2 = entry_time[3], Bridges Search marks edge (3, 6) as a bridge.

Bridges Search backtrack from node 3 to node 2 and set lowpoint[2] = 0.

Bridges Search moves to node 5 and set visited[5] = 1, entry_time[5] = 6, lowpoint[5] = 6, timer = 7.

Bridges Search backtrack from node 5 to node 2. Since lowpoint[5] = 6 > 1 = entry_time[2], Bridges Search marks edge (2, 5) as a bridge.

Bridges Search backtrack from node 2 to node 1 without updating anything.

Bridges Search finished at node 1.

Code

                        def bridges_search(graph: Dict[int, List[int]]) -> List[Tuple[int, int]]:
                            n = len(graph)
                            visited = [False] * n
                            entry_time = [-1] * n
                            lowpoint = [-1] * n
                            timer = 0
                        
                            bridges = []
                        
                            def dfs(node: int, parent: int = -1):
                                nonlocal visited, entry_time, lowpoint, timer, bridges
                                visited[node] = True
                                entry_time[node] = timer
                                lowpoint[node] = timer
                                timer += 1
                        
                                for neighbour in graph[node]:
                                    if neighbour == parent:
                                        continue
                        
                                    if visited[neighbour]:
                                        lowpoint[node] = min(
                                            lowpoint[node],
                                            entry_time[neighbour],
                                        )
                                    else:
                                        dfs(neighbour, parent=node)
                                        lowpoint[node] = min(
                                            lowpoint[node],
                                            lowpoint[neighbour],
                                        )
                                        if lowpoint[neighbour] > entry_time[node]:
                                            bridges.append((node, neighbour))
                        
                            for node in range(len(graph)):
                                if False == visited[node]:
                                    dfs(node)
                        
                            return bridges