Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

Algorithm Visualization

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

BFS(root)
  Pre: root is the node of the BST
  Post: the nodes in the BST have been visited in breadth first order
  q ← queue
  while root = ø
    yield root.value
    if root.left = ø
      q.enqueue(root.left)
    end if
    if root.right = ø
      q.enqueue(root.right)
    end if
    if !q.isEmpty()
      root ← q.dequeue()
    else
      root ← ø
    end if
  end while
end BFS

Applications

  • Copying garbage collection, Cheney’s algorithm
  • Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth-first search)
  • (Reverse) Cuthill–McKee mesh numbering
  • Ford–Fulkerson method for computing the maximum flow in a flow network
  • Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
  • Construction of the failure function of the Aho-Corasick pattern matcher.
  • Testing bipartiteness of a graph.

References

Implementations

Shortest Path

  • 1

    # TODO: Implement in Python

  • 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 BFS() {
  const W = []; // W[i] indicates the length of the shortest path from start node to the i-th node
  const Q = [];
  let i;
  for (i = 0; i < G.length; i++) {
    W.push(MAX_VALUE);
    
  }
  W[s] = 0;
  Q.push(s); // add start node to queue
  
  while (Q.length > 0) {
    const node = Q.shift(); // dequeue
    for (i = 0; i < G[node].length; i++) {
      if (G[node][i]) { // if the edge from current node to the i-th node exists
        if (W[i] > W[node] + G[node][i]) { // if current path is shorter than the previously shortest path
          W[i] = W[node] + G[node][i]; // update the length of the shortest path
          Q.push(i); // add child node to queue
          
        }
      }
    }
  }
  return W[e];
}

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

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

const minWeight = BFS(s);

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}`);
}

Tree

  • 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

    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 BFS(s) { // s = start node
  const Q = [];
  Q.push(s); // add start node to queue
  
  while (Q.length > 0) {
    const node = Q.shift(); // dequeue
    for (let i = 0; i < G[node].length; i++) {
      if (G[node][i]) { // if current node has the i-th node as a child
        Q.push(i); // add child node to queue
        
      }
    }
  }
}

BFS(0);