An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. A naive solution to finding bridges in a graph is to:
1.Delete an edge E
2.Perform DFS Exploration to check if the Graph is still connected
3.Restore Edge E. E is a bridge only if DFS exploration determines that the graph is disconnected without E.

A more efficient solution, which can find bridges in linear time, is to perform a DFS (depth-first-search) on the graph. At each step:
1. Number the vertex with a counter. The first vertex visited should be labelled 0, the second vertex labelled 1, etc.
2. Each vertex should also keep track of the lowest numbered vertex that can be reached with the DFS. This can be done recursively by looking at the smallest “low” of its children
3. If the lowest vertex that can be reached with the DFS is greater than its own label, that means the edge with its parent is a bridge. This is because the vertex cannot reach its parent with the DFS, implying that the edge is not part of a cycle.

Applications

  • Finding vulnerabilities in Graphs and Electrical Circuits

Complexity

  • Time: worst Naive: ![](https://latex.codecogs.com/svg.latex?O( E \cdot( V + E ))), Efficient: ![](https://latex.codecogs.com/svg.latex?O( V + E ))
  • Space: worst ![](https://latex.codecogs.com/svg.latex?O( V \cdot E ))

References

Implementations

Python

  • 1

    # TODO: Implement in Python

JavaScript

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

    console.log(`original array = [${D[0].join(', ')}]`);

function pow(base, expo) {
  let ans = 1;
  for (let i = 0; i < expo; i++) {
    ans *= base;
  }
  return ans;
}

function digit(i, exp) {
  return parseInt(D[0][i] / pow(10, exp) % 10);
}

for (let exp = 0; exp < 3; exp++) {
  
  console.log(`Digit: ${exp}`);
  
  let i;
  for (i = 0; i < D[0].length; i++) {
    const d = digit(i, exp);
    
    D[2][d] += 1;
    
  }
  for (i = 1; i < 10; i++) {
    
    D[2][i] += D[2][i - 1];
    
  }
  for (i = D[0].length - 1; i >= 0; i--) {
    const d = digit(i, exp);
    
    D[2][d] -= 1;
    
    D[1][D[2][d]] = D[0][i];
    
  }
  for (i = 0; i < D[0].length; i++) {
    
    D[0][i] = D[1][i];
    
  }
  for (i = 0; i < 10; i++) {
    D[2][i] = 0;
    
  }
}

console.log(`sorted array = [${D[0].join(', ')}]`);

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

    console.log(`original array = [${D[0].join(', ')}]`);

function mergeSort(start, end) {
  if (Math.abs(end - start) <= 1) return;

  let mergeFrom = 0;
  let mergeTo = 1;
  let width;
  let i;
  for (width = 1; width < end; width *= 2) {
    
    for (i = 0; i < end; i += 2 * width) {
      merge(mergeFrom, i, Math.min(i + width, end), Math.min(i + 2 * width, end), mergeTo);
    }
    // this could be copy(mergeTo, mergeFrom, start, end);
    // but it is more effecient to swap the input arrays
    // if you did copy here, you wouldn't need the copy at the end
    mergeFrom = (mergeFrom === 0 ? 1 : 0);
    mergeTo = 1 - mergeFrom;
  }
  if (mergeFrom !== 0) {
    
    copy(mergeFrom, mergeTo, start, end);
  }
}

function merge(mergeFrom, start, middle, end, mergeTo) {
  let i = start;
  let j = middle;
  let k;
  // in an actual merge implementation, mergeFrom and mergeTo would be arrays
  // here for the ability to trace what is going on better, the arrays are D[mergeFrom] and D[mergeTo]

  for (k = start; k < end; k++) {

    if (i < middle && (j >= end || D[mergeFrom][i] <= D[mergeFrom][j])) {

      D[mergeTo][k] = D[mergeFrom][i];
      i += 1;
    } else {

      D[mergeTo][k] = D[mergeFrom][j];
      j += 1;
    }
  }
}

function copy(mergeFrom, mergeTo, start, end) {
  let i;
  for (i = start; i < end; i++) {

    D[mergeTo][i] = D[mergeFrom][i];

  }
}

mergeSort(0, D[0].length);

console.log(`sorted array = [${D[0].join(', ')}]`);

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

    console.log(`original array = [${D.join(', ')}]`);

function mergeSort(start, end) {
  if (Math.abs(end - start) <= 1) return [];
  const middle = Math.ceil((start + end) / 2);

  mergeSort(start, middle);
  mergeSort(middle, end);

  console.log(`divide left[${start}, ${middle - 1}], right[${middle}, ${end - 1}]`);
  
  return mergeSort.merge(start, middle, end);
}

mergeSort.merge = (start, middle, end) => {
  const leftSize = middle - start;
  const rightSize = end - middle;
  const maxSize = Math.max(leftSize, rightSize);
  const size = end - start;
  const left = [];
  const right = [];
  let i;

  for (i = 0; i < maxSize; i++) {
    if (i < leftSize) {
      left.push(D[start + i]);
      
    }
    if (i < rightSize) {
      right.push(D[middle + i]);
      
    }
  }
  
  console.log(`left array = [${left.join(', ')}], ` + `right array = [${right.join(', ')}]`);

  i = 0;
  while (i < size) {
    if (left[0] && right[0]) {
      if (left[0] > right[0]) {
        D[start + i] = right.shift();
        
        console.log(`rewrite from right array[${i}] = ${D[start + i]}`);
        
      } else {
        D[start + i] = left.shift();
        
        console.log(`rewrite from left array[${i}] = ${D[start + i]}`);
        
      }
    } else if (left[0]) {
      D[start + i] = left.shift();
      
      console.log(`rewrite from left array[${i}] = ${D[start + i]}`);
      
    } else {
      D[start + i] = right.shift();
      
      console.log(`rewrite from right array[${i}] = ${D[start + i]}`);
      
    }

    i++;
  }

  const tempArray = [];
  for (i = start; i < end; i++) tempArray.push(D[i]);
  
  console.log(`merged array = [${tempArray.join(', ')}]`);
  
};

mergeSort(0, D.length);

console.log(`sorted array = [${D.join(', ')}]`);

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

    function DFSExplore(graph, source) {
  const stack = [[source, null]];
  const visited = [];
  let node;
  let prev;
  let i;
  let temp;
  for (i = 0; i < graph.length; i++) {
    visited.push(false);
  }

  while (stack.length > 0) {
    temp = stack.pop();
    node = temp[0];
    prev = temp[1];

    if (!visited[node]) {
      visited[node] = true;

      for (i = 0; i < graph.length; i++) {
        if (graph[node][i]) {
          stack.push([i, node]);
        }
      }
    }
  }

  return visited;
}

const visited = DFSExplore(G, 0);
let check = true;
for (let i = 0; i < visited.length; i++) check &= visited[i];

if (check) {
  console.log('The Graph is CONNECTED');
} else {
  console.log('The Graph is NOT CONNECTED');
}

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

    function DFS(node, parent, weight) { // node = current node, parent = previous node
  if (minWeight < weight) return;
  if (node === e) {
    
    if (minWeight > weight) {
      minWeight = weight;
    }
    
    return;
  }
  D[node] = true; // label current node as discovered
  
  for (let i = 0; i < G[node].length; i++) {
    if (G[node][i]) { // if the path from current node to the i-th node exists
      if (!D[i]) { // if the i-th node is not labeled as discovered
        DFS(i, node, weight + G[node][i]); // recursively call DFS
      }
    }
  }
  D[node] = false; // label current node as undiscovered
  
}

const s = Randomize.Integer({ min: 0, max: G.length - 1 }); // s = start node
let e; // e = end node
do {
  e = Randomize.Integer({ min: 0, max: G.length - 1 });
} while (s === e);
const MAX_VALUE = Infinity;
let minWeight = MAX_VALUE;

console.log(`finding the shortest path from ${s} to ${e}`);

let D = []; // D[i] indicates whether the i-th node is discovered or not
for (let i = 0; i < G.length; i++) D.push(false);
DFS(s, undefined, 0);

if (minWeight === MAX_VALUE) {
  console.log(`there is no path from ${s} to ${e}`);
} else {
  console.log(`the shortest path from ${s} to ${e} is ${minWeight}`);
}

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    const G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
  [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

function DFS(node, parent) { // node = current node, parent = previous node
  
  for (let i = 0; i < G[node].length; i++) {
    if (G[node][i]) { // if current node has the i-th node as a child
      DFS(i, node); // recursively call DFS
    }
  }
}

DFS(0);

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    let D; // D[i] indicates whether the i-th node is discovered or not

function DFS(node, parent, weight) { // node = current node, parent = previous node
  
  D[node] = true; // label current node as discovered
  for (let i = 0; i < G[node].length; i++) {
    if (G[node][i]) { // if the edge from current node to the i-th node exists
      if (!D[i]) { // if the i-th node is not labeled as discovered
        DFS(i, node, weight + G[node][i]); // recursively call DFS
      }
    }
  }
  D[node] = false; // label current node as undiscovered
  
}

for (let i = 0; i < G.length; i++) { // start from every node
  
  console.log(`start from ${i}`);
  
  D = [];
  for (let j = 0; j < G.length; j++) D.push(false);
  DFS(i, undefined, 0);
}

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

    const G = [
  [0, 1, 0, 0, 1, 0],
  [1, 0, 0, 0, 1, 0],
  [0, 0, 0, 1, 0, 0],
  [0, 0, 1, 0, 1, 1],
  [1, 1, 0, 1, 0, 0],
  [0, 0, 0, 1, 0, 0],
];

/*
  NOTE: Code assumes NO parallel edges
*/

let timer = 0; // adj keeps track of the neighbors of each node

const bridges = [];
const adj = [];

const util = (u, disc, low, parent) => {
  // u is the node that is currently being processed in the DFS (depth-first search)
  // disc is the numbering of the vertices in the DFS, starting at 0
  // low[v] is the lowest numbered vertex that can be reached from vertex v along the DFS
  // parent is the node that u came from

  // visited [u] = true;
  disc[u] = low[u] = timer++;

  console.log(`Nodes adjacent to ${u} are: [ ${adj[u]} ]`);
  
  /* adj [u].forEach (function (v) {
    graphTracer.visit (v, u).delay ();
    graphTracer.leave (v, u).delay ();
  }); */
  const trace = (v) => {
    
  };

  adj[u].forEach((v) => {
    if (disc[v] > -1 && v === parent) {
      trace(v);
      
      console.log(`${u}'s neighbor ${v} is u's parent. Not visiting it.`);
      
    } else if (disc[v] > -1 && v !== parent) {
      trace(v);
      
      console.log(`${u}'s neighbor ${v} is not u's parent. Comparing low[u] with disc[v]`);
      
      if (low[u] > disc[v]) {
        
        console.log(`low[${u}] is greater than disc[${v}]. Setting low[${u}] to disc[${v}]`);
        
        low[u] = disc[v];
      }
    }

    if (disc[v] === -1) {
      trace(v);
      
      console.log(`${u}'s neighbor ${v} has not been visited yet`);

      console.log(`recursively calling util (${v}, [${disc}], [${low}],${u})`);
      
      util(v, disc, low, u);

      console.log('--------------------------------------------------------------------');

      console.log(`Setting low [${u}] to ${Math.min(low[u], low[v])}`);
      
      low[u] = Math.min(low[u], low[v]);

      if (low[v] === disc[v]) {
        
        console.log(`low [${v}] === disc [${v}], low[${v}]=${low[v]}, disc[${v}]=${disc[v]}`);
        console.log(`${u} -> ${v} is a bridge. Adding ${u}->${v}to the set of bridges found`);
        
        bridges.push([u, v]);
      }
    }
  });
};

(function findBridges(graph) {
  const disc = filledArray(graph.length, -1);
  const low = filledArray(graph.length, -1);

  function filledArray(length, value) {
    return Array(...Array(length)).map(Number.prototype.valueOf, value);
  }

  // PRECOMPUTATION: store every node's neighbor info in auxiliary array for efficient retrieval later
  (function computeAdj() {
    graph.forEach((config) => {
      const temp = [];
      config.forEach((isEdge, i) => {
        isEdge && temp.push(i);
      });
      adj.push(temp);
    });
  }());

  console.log(`Initializing: <b>disc</b>: ${disc} <b>low</b>: ${low}`);
  console.log('');
  console.log('Beginning efficient Bridge Finding');
  console.log('NOTE: call to util () follows pattern: util (nodeToVisit, disc, low, parent). See code for clarity');
  console.log('');

  console.log('Starting the main for loop (for each node)');
  
  for (let v = 0; v < graph.length; v++) {
    if (disc[v] === -1) {
      
      console.log(`${v} has not been visited yet. Calling util (${v},  [${disc}], [${low}],${v}) from the for loop`);
      
      util(v, disc, low, v);
      
      console.log(`Returned in for loop after util (${v}, [${disc}], [${low}], [${v}])`);
      
    }
  }
}(G));

console.log(`There are ${bridges.length} bridges in the Graph`);
for (let i = 0; i < bridges.length; i++) {
  console.log(`${bridges[i][0]}-->${bridges[i][1]}`);
}
console.log('NOTE: All bridges are both ways (just like in the Naive Algorithm) because the Graph is undirected. So, edge A->B and B->A, both are bridges');

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

    const G = [
  [0, 1, 0, 0, 0, 0],
  [1, 0, 0, 1, 1, 0],
  [0, 0, 0, 1, 0, 0],
  [0, 1, 1, 0, 1, 1],
  [0, 1, 0, 1, 0, 0],
  [0, 0, 0, 1, 0, 0],
];

// Depth First Search Exploration Algorithm to test connectedness of the Graph (see Graph algorithms/DFS/exploration), without the tracer & logger commands
function DFSExplore(graph, source) {
  const stack = [[source, null]];
  const visited = {};
  let node;
  let prev;
  let i;
  let temp;

  while (stack.length > 0) {
    temp = stack.pop();
    node = temp[0];
    prev = temp[1];

    if (!visited[node]) {
      visited[node] = true;

      for (i = 0; i < graph.length; i++) {
        if (graph[node][i]) {
          stack.push([i, node]);
        }
      }
    }
  }

  return visited;
}

function findBridges(graph) {
  let tempGraph;
  const bridges = [];
  let visited;

  for (let i = 0; i < graph.length; i++) {
    for (let j = 0; j < graph.length; j++) {
      if (graph[i][j]) { // check if an edge exists

        tempGraph = JSON.parse(JSON.stringify(graph));
        tempGraph[i][j] = 0;
        tempGraph[j][i] = 0;
        visited = DFSExplore(tempGraph, 0);

        if (Object.keys(visited).length === graph.length) {
          
          console.log('Graph is CONNECTED. Edge is NOT a bridge');
          
        } else {
          
          console.log('Graph is DISCONNECTED. Edge IS a bridge');
          
          bridges.push([i, j]);
        }
      }
    }
  }

  return bridges;
}

const bridges = findBridges(G);

console.log('The bridges are: ');
for (const i in bridges) {
  console.log(`${bridges[i][0]} to ${bridges[i][1]}`);
}
console.log('NOTE: A bridge is both ways, i.e., from A to B and from B to A, because this is an Undirected Graph');