Java graph bridges: track edge identity when parallel edges exist

Last updated: 29 Sept 20264 min read

tutorial

A bridge is an undirected edge whose removal increases the number of connected components in the graph.

Download Java source kit

This complete program targets Java 8. Its displayed output is checked by the tutorial validation script.

Skip the parent edge, not the parent vertex

The transport graph assigns one identity to each undirected edge and uses that identity on both adjacency entries. DFS skips only the exact edge used to reach the current vertex. If two parallel links connect the same vertices, the other link remains a valid return path and neither is a bridge.

Discovery order and the lowest reachable discovery order supply the bridge test. After visiting an unvisited neighbor, its low value is compared with the current discovery value. The fixture starts a new DFS for every unvisited vertex so a disconnected component is not silently omitted.

The recursion limit is part of this implementation

The API caps vertices at five hundred and edges at five thousand, validates both endpoints and returns sorted original edge IDs. It supports self-loops and parallel links. Larger graphs need an explicit stack or a measured recursion policy; changing the input bound without that review changes the failure risk.

A bridge describes graph connectivity, not a guarantee that a real network fails when that connection stops. Routing, capacity and external paths are different evidence. DFS traversal and Directed components answer related but distinct graph questions.

Working program

import java.util.*;
public class TransportBridgeEdges {
    static class Edge {final int target,id;Edge(int target,int id){this.target=target;this.id=id;}}
    static void visit(int vertex,int parentEdge,List<List<Edge>> graph,int[] discovered,int[] low,int[] clock,List<Integer> bridges) {
        discovered[vertex]=low[vertex]=++clock[0];
        for(Edge edge:graph.get(vertex)) {
            if(edge.id==parentEdge)continue;
            if(discovered[edge.target]==0) {
                visit(edge.target,edge.id,graph,discovered,low,clock,bridges);
                low[vertex]=Math.min(low[vertex],low[edge.target]);
                if(low[edge.target]>discovered[vertex])bridges.add(edge.id);
            } else low[vertex]=Math.min(low[vertex],discovered[edge.target]);
        }
    }
    static List<Integer> bridges(int vertices,int[][] links) {
        if(vertices<1 || vertices>500 || links.length>5000)throw new IllegalArgumentException("graph bounds");
        List<List<Edge>> graph=new ArrayList<>();for(int i=0;i<vertices;i++)graph.add(new ArrayList<>());
        for(int id=0;id<links.length;id++) {
            int[] edge=links[id];if(edge.length!=2 || edge[0]<0 || edge[0]>=vertices || edge[1]<0 || edge[1]>=vertices)throw new IllegalArgumentException("endpoint");
            graph.get(edge[0]).add(new Edge(edge[1],id));graph.get(edge[1]).add(new Edge(edge[0],id));
        }
        List<Integer> critical=new ArrayList<>();int[] discovered=new int[vertices],low=new int[vertices],clock={0};
        for(int vertex=0;vertex<vertices;vertex++)if(discovered[vertex]==0)visit(vertex,-1,graph,discovered,low,clock,critical);
        Collections.sort(critical);return critical;
    }
    public static void main(String[] args) {
        System.out.println(bridges(4,new int[][]{{0,1},{1,2},{2,0},{1,3}}));
        System.out.println(bridges(2,new int[][]{{0,1},{0,1}}));
    }
}

Output

[3]
[]

Costs and boundaries

DFS and adjacency construction take O(v+e) time and storage. Sorting b returned bridge IDs adds O(b log b) time. Recursive stack depth can reach v, which is why this fixture bounds vertices; a simple path is an adversarial depth case.

Common Mistakes

Skip the exact parent edge when parallel links are allowed.
Visit every disconnected component.
Do not omit stack depth from the input contract.