Breadth-First Search (BFS)

For trees, you learned pre-order, in-order, and post-order. Graphs need something new: they have no root and can have cycles, so if we are not careful, we could go around a cycle forever. The fix is to remember which vertices we have already seen.

Recall the queue from the linear data structures lessons: you enqueue at the rear and dequeue from the front, like a line at the canteen. First in, first out.

BFS puts every newly found vertex at the rear of the queue. Since all level-1 vertices are found before any level-2 vertex, they are also in line first. So the queue automatically keeps the waves in order: closer vertices are always visited before farther ones.

In Part 2 you watched BFS from A. Now it is your turn to predict: this lab starts at D. Before each tap of Next step, say out loud which vertex leaves the queue next and which ones join. Then pick other starting vertices with the round buttons.

Whatever start you pick, the order follows the levels. From A (Part 2), the BFS order was A, B, D, C, E, F, G: A (level 0), then B and D (level 1), then C and E (level 2), then F and G (level 3).

BFS gives you more than a visit order. While it runs, it also answers a very common question: what is the fewest number of steps from the start to each vertex?

You saw this question in Part 1 : the route with the fewest hops between two computers, and "people you may know" (people 2 friendships away). Another example: the fewest links you must click to get from one web page to another. When every edge counts the same (an unweighted graph), "fewest steps" means "fewest edges".

BFS gets this answer for free because of the waves. It reaches every level-1 vertex before any level-2 vertex, and so on, so the first time BFS finds a vertex, it found it the shortest way. That is why a vertex's level is exactly the fewest edges needed to reach it from the start.

BFS visits everything reachable from the start, and nothing else. That makes it a quick test:

• Undirected graph: run BFS from any vertex. If every vertex gets visited, the graph is connected. If not, it is in separate pieces.
• Directed graph: BFS from S tells you exactly which vertices can be reached from S by following arrows.

This program builds the main example as an adjacency matrix, then runs BFS from A. Java's Queue works like the queue you learned: offer = enqueue at the rear, poll = dequeue from the front. LinkedList is one of Java's built-in queue types.

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
  static char[] names = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
  static int n = names.length;
  static int[][] adj = new int[n][n];

  static void addEdge(int a, int b) {   // undirected
    adj[a][b] = 1;
    adj[b][a] = 1;
  }

  static void bfs(int start) {
    boolean[] seen = new boolean[n];      // all false
    Queue<Integer> queue = new LinkedList<>();

    seen[start] = true;
    queue.offer(start);                   // enqueue

    while (!queue.isEmpty()) {
      int u = queue.poll();               // dequeue (front)
      System.out.print(names[u] + " ");   // visit

      for (int v = 0; v < n; v++) {       // A to Z order
        if (adj[u][v] == 1 && !seen[v]) {
          seen[v] = true;                 // mark now...
          queue.offer(v);                 // ...then enqueue
        }
      }
    }
  }

  public static void main(String[] args) {
    addEdge(0, 1); addEdge(0, 3);   // A-B, A-D
    addEdge(1, 2); addEdge(1, 4);   // B-C, B-E
    addEdge(2, 5); addEdge(3, 4);   // C-F, D-E
    addEdge(4, 5); addEdge(4, 6);   // E-F, E-G
    addEdge(5, 6);                  // F-G
    bfs(0);   // prints: A B D C E F G
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class BFS to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Here is how to read the new lines aloud. The matrix lines (names, adj, addEdge) are the same as in the Graphs lesson, Part 8.

 1import java.util.LinkedList;
 2import java.util.Queue;
 3
 4public class Main {
 5  static char[] names = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
 6  static int n = names.length;
 7  static int[][] adj = new int[n][n];
 8
 9  static void addEdge(int a, int b) {   // undirected
10    adj[a][b] = 1;
11    adj[b][a] = 1;
12  }
13
14  // BFS from start. Returns the level of every vertex.
15  // level[v] == -1 means "not seen yet" (it works like seen[v] == false).
16  static int[] bfsLevels(int start) {
17    int[] level = new int[n];
18    for (int i = 0; i < n; i++) {
19      level[i] = -1;
20    }
21    Queue<Integer> queue = new LinkedList<>();
22
23    level[start] = 0;                     // the start is level 0
24    queue.offer(start);
25
26    while (!queue.isEmpty()) {
27      int u = queue.poll();               // dequeue (front)
28      // YOUR CODE:
29      // Check every v from 0 to n - 1 (A to Z order).
30      // If v is a neighbor of u and v is not seen yet (level -1):
31      //   v is one level below u, so set its level,
32      //   then enqueue v.
33
34    }
35    return level;
36  }
37
38  // Given: prints the levels, like "A=0 B=1 ...".
39  static void printLevels(int[] level) {
40    for (int i = 0; i < n; i++) {
41      System.out.print(names[i] + "=" + level[i] + " ");
42    }
43    System.out.println();
44  }
45
46  public static void main(String[] args) {
47    // the main example (H has no edges)
48    addEdge(0, 1); addEdge(0, 3);   // A-B, A-D
49    addEdge(1, 2); addEdge(1, 4);   // B-C, B-E
50    addEdge(2, 5); addEdge(3, 4);   // C-F, D-E
51    addEdge(4, 5); addEdge(4, 6);   // E-F, E-G
52    addEdge(5, 6);                  // F-G
53
54    printLevels(bfsLevels(0));
55    // expected: A=0 B=1 C=2 D=1 E=2 F=3 G=3 H=-1
56    printLevels(bfsLevels(6));
57    // expected: A=3 B=2 C=2 D=2 E=1 F=1 G=0 H=-1
58    printLevels(bfsLevels(7));
59    // expected: A=-1 B=-1 C=-1 D=-1 E=-1 F=-1 G=-1 H=0
60  }
61}

 1for (int v = 0; v < n; v++) {       // A to Z order
 2  if (adj[u][v] == 1 && level[v] == -1) {
 3    level[v] = level[u] + 1;        // one level below u
 4    queue.offer(v);
 5  }
 6}

Not graded. Tap an answer to see if you got it, and read why.

Next lesson: Depth-first search (DFS), which goes deep first instead of wide.