Skip to content

findBridges ​

findBridges(graph) returns every undirected edge whose removal increases the number of connected components. It accepts an adjacency list or Graph<N, W>.

SignatureReturnsComplexity
findBridges(graph: usize[][])[usize, usize][]O(V + E)
findBridges(graph: Graph<N, W>)[usize, usize][]O(V + E)

The adjacency list is interpreted as undirected and should contain symmetric entries. Each result is a pair of vertex indices.

Example ​

tyrus
import { findBridges } from "tyrus:algorithm";

const bridges: [usize, usize][] = findBridges([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(bridges.length); // 1

Study result ​

tyrus
interface FindBridgesInfo {
    examinedEdgeCount: usize;
    discoveryIndices: usize[];
    lowLinks: usize[];
    resultCount: usize;
    bridges: [usize, usize][];
}
tyrus
import { ConnectivityInfo, FindBridgesInfo, findBridgesInfo } from "tyrus:algorithm";
const info: FindBridgesInfo = findBridgesInfo([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(info.bridges); // [[1, 3]]
print(info.examinedEdgeCount); // 8
print(info.discoveryIndices); // [0, 1, 2, 3]
print(info.lowLinks); // [0, 0, 0, 3]
print(info.resultCount); // 1