Skip to content
dsa450for five year olds

Graph · 26 of 43

Find bridge in a graph

Find every road that, if it washed away, would cut the map into two parts.

HardDepth first search with low-link
Simple way
time O(E * (V + E))
room O(V + E)
Clever way
time O(V + E)
room O(V + E)

The problem, simply

You get an undirected graph: V islands and two-way roads. A bridge is a road that, if you remove it, leaves some islands that can no longer reach each other.

List all bridges, in any order.

A story to remember it

Picture it

graph
0123456

Two triangles joined by the road 1-3, and island 6 hanging off 4. Cutting 1-3 or 4-6 splits the map. Cutting any road of a triangle does not.

  • answer

Examples

Two triangles and a tail

In
V = 7, edges = [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3],[4,6]]
Out
[[4,6],[1,3]]

Every road on a triangle has a second way around. The other two do not.

A triangle with a chain

In
V = 5, edges = [[0,1],[0,2],[1,2],[1,3],[3,4]]
Out
[[3,4],[1,3]]

0, 1, 2 is a loop. The chain 1, 3, 4 has no second way, so both of its roads are bridges.

A plain loop

In
V = 3, edges = [[0,1],[1,2],[2,0]]
Out
[]

Cut any road and you can still go the other way around.

Two roads between the same islands

In
V = 2, edges = [[0,1],[0,1]]
Out
[]

If one road washes away, the other is still there. Code that skips the parent island instead of the parent road gets this wrong.

Way 1: the simple way

Try removing each road and check if its two ends can still reach each other.

  1. For each road u-v, block it.
  2. Search from u without using the blocked road. If v is not reached, the road is a bridge.
  3. Unblock and move on.
java
class BridgesBrute {
    public static List<int[]> findBridges(int V, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();          // {neighbor, road number}
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int id = 0; id < edges.length; id++) {
            adj.get(edges[id][0]).add(new int[]{edges[id][1], id});
            adj.get(edges[id][1]).add(new int[]{edges[id][0], id});
        }
        List<int[]> bridges = new ArrayList<>();
        for (int cut = 0; cut < edges.length; cut++) {
            int u = edges[cut][0], v = edges[cut][1];
            boolean[] seen = new boolean[V];
            Deque<Integer> line = new ArrayDeque<>();
            line.add(u);
            seen[u] = true;
            while (!line.isEmpty()) {
                int x = line.poll();
                for (int[] nb : adj.get(x)) {
                    if (nb[1] != cut && !seen[nb[0]]) { seen[nb[0]] = true; line.add(nb[0]); }
                }
            }
            if (!seen[v]) bridges.add(new int[]{u, v});      // the ends got split apart
        }
        return bridges;
    }
}

How long it takes: one search per road, O(E * (V + E)). Extra room: the road lists, O(V + E).

Way 2: the clever way

One depth first walk is enough. This is Tarjan's idea.

  1. When you first reach island u, set time[u] = low[u] = timer++.
  2. For each road from u (skip only the exact road you came in on):
  3. If the other end v is already stamped, it is a side road back up. Set low[u] = min(low[u], time[v]).
  4. If v is new, walk into it. When you come back, set low[u] = min(low[u], low[v]). If low[v] > time[u], the road u-v is a bridge.

The badges in the pictures show time/low.

Stamp arrival times, carry the lowest reachable time back up

01 / 16

graph
01234560/0
stackcall stack
dfs(0)top

Start at 0. Its arrival time is 0, and the lowest time it can reach is 0 for now. The badge shows time/low.

bridges
none yet
  • looking now
  • checking
  • seen
  • answer
  • path
  • just added
java
class BridgesTarjan {
    private int timer;
    private int[] time, low;
    private List<List<int[]>> adj;
    private List<int[]> bridges;

    public List<int[]> findBridges(int V, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int id = 0; id < edges.length; id++) {
            adj.get(edges[id][0]).add(new int[]{edges[id][1], id});
            adj.get(edges[id][1]).add(new int[]{edges[id][0], id});
        }
        time = new int[V];
        low = new int[V];
        Arrays.fill(time, -1);
        timer = 0;
        bridges = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (time[i] == -1) walk(i, -1);                  // every piece of the map
        }
        return bridges;
    }

    private void walk(int u, int cameBy) {
        time[u] = low[u] = timer++;
        for (int[] nb : adj.get(u)) {
            int v = nb[0], road = nb[1];
            if (road == cameBy) continue;                    // skip only the road we used
            if (time[v] != -1) {
                low[u] = Math.min(low[u], time[v]);          // side road back up
            } else {
                walk(v, road);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > time[u]) bridges.add(new int[]{u, v});
            }
        }
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}};
        for (int[] b : new BridgesTarjan().findBridges(7, edges)) System.out.println(b[0] + " - " + b[1]);
    }
}

How long it takes: one walk, every island and road handled a constant number of times, O(V + E). Extra room: the road lists and the arrays, O(V + E), and the call stack can be V deep.

Watch out for

  • The test is low[v] > time[u], strictly greater. With >= you are finding cut islands (articulation points), a different problem.
  • When v is already stamped, use time[v], not low[v]. Using low[v] happens to work for bridges but breaks the cut island version, so build the right habit.
  • A static timer that is never reset gives wrong times on the second test case.
  • Start a walk from every unstamped island; the map may come in pieces.

What interviewers ask next

  • Cut islands (articulation points): u is one if it has a child v with low[v] >= time[u]. The start island is special: it is one only if it has two or more children in the walk.
  • "Critical connections in a network" on LeetCode is exactly this problem.
  • How to make the network safe? Squash each part with no bridges into one dot. The bridges then form a tree, and you need about half as many new roads as that tree has leaves.
  • Can you avoid recursion for a million islands? Yes, with your own stack that remembers which road index each island is on.

Remember this

Grown-up words: islands are vertices, roads are edges, the arrival stamp is the discovery time, the lowest reachable time is the low-link value, a side road back up is a back edge, the walk is depth first search, and the whole method is Tarjan's bridge-finding algorithm.