Breadth-First Search (BFS)

Breadth-first search (BFS) is an important graph search algorithm that is used to solve many problems including finding the shortest path in a graph and solving puzzle games (such as Rubik's Cubes). Many problems in computer science can be thought of in terms of graphs. For example, analyzing networks, mapping routes, and scheduling are graph problems. Graph search algorithms like breadth-first search are useful for analyzing and solving graph problems.

Breadth-first search starts by searching a start node, followed by its adjacent nodes, then all nodes that can be reached by a path from the start node containing two edges, three edges, and so on. Formally, the BFS algorithm visits all vertices in a graph \(G\) that are \(k\) edges away from the source vertex \(s\) before visiting any vertex \(k+1\) edges away. This is done until no more vertices are reachable from \(s\). The image below demonstrates exactly how this traversal proceeds:

^[1]

For a graph \(G = (V,E)\) and a source vertex \(v\), breadth-first search traverses the edges of \(G\) to find all reachable vertices from \(v\). It also computes the shortest distance to any reachable vertex. Any path between two points in a breadth-first search tree corresponds to the shortest path from the root \(v\) to any other node \(s\).

There are three types of vertices in BFS: tree vertices, those that have been visited; fringe vertices, those adjacent to tree vertices but not yet visited; and undiscovered vertices, those that we have not encountered yet. In the animation above, white indicates vertices that are undiscovered, grey indicates fringe vertices, and black indicates tree vertices.

To systematically search a connected component of a graph, begin with one vertex on the fringe, all others unseen, and perform the following step until all vertices have been visited: "move one vertex \(x\) from the fringe to the tree, and put any unseen vertices adjacent to \(x\) on the fringe." Graph traversal methods differ in how it is decided which vertex should be moved from the fringe to the tree. For breadth-first search, choose the vertex from the fringe that was least recently encountered; this corresponds using a queue to hold vertices on the fringe.

Fill out the following graph by labeling each node 1 through 12 according to the order that breadth-first search would visit the nodes in.

Solution

^[2]

What is the state of the queue at each iteration of BFS if it is called from node 'a'?

Solution

The below table shows the contents of the queue as the procedure. BFS visits vertices in the graph above. BFS will visit the same vertices as DFS.

\[\begin{array}{l|r} \textbf{Node Visited} & \textbf{Queue} \\ \hline \text{a} & \text{a} \\ \text{ } & \text{(empty)} \\ \text{b } & \text{b} \\ \text{f } & \text{b e f} \\ \text{i} & \text{b f i} \\ \text{ } & \text{f i} \\ \text{c} & \text{f i c} \\ \text{e} & \text{f i c e} \\ \text{ } & \text{ i c e} \\ \text{g } & \text{ i c e g} \\ \text{ } & \text{ c e g} \\ \text{ } & \text{ e g} \\ \text{d } & \text{ e g d} \\ \text{ } & \text{ g d} \\ \text{ } & \text{ d} \\ \text{ } & \text{ (empty)} \\ \text{ h} & \text{ h} \\ \text{ } & \text{ (empty) } \end{array}\]

Here is a pseudocode implementation of breadth-first search.

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

BFS(v){
    {add v to queue and mark it}
    Add(Q, v)
    Mark v as visited
    while (not IsEmpty(Q)) do
    begin
        w = QueueFront(Q)
        Remove(Q)
        {loop invariant : there is a path from vertex w to every vertex in the queue Q}
        for each unvisited vertex u adjacent to w do
        begin
            Mark u as visited
            Add(Q , u)
        end { for }
    end{ while
}

For the following graph, perform a breadth-first search. Determine the source node, the list of visited nodes (\(V\)), and the state of the queue (\(Q\)) at each step.

1: Source node = \(A\), \(V = [A]\), \(Q = []\)

2: Source node = \(A\), \(V = [A,B,C,D]\), \(Q = [B,C,D]\)

3: Source node = \(B\), \(V = [A,B,C,D,E,F,G]\), \(Q = [C,D,E,F,G]\)

4: Source node = \(C\), \(V = [A,B,C,D,E,F,G,H,I]\), \(Q = [D,E,F,G,H,I]\)

5: Source node = \(D\), \(V = [A,B,C,D,E,F,G,H,I,J,Z]\), \(Q = [E,F,G,H,I,J,Z]\)

6: Source node = \(E\), \(V = [A,B,C,D,E,F,G,H,I,J,Z]\), \(Q = [F,G,H,I,J,Z,K,L]\)

7: Source node = \(F\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L]\), \(Q = [G,H,I,J,Z,K,L]\)

8: Source node = \(G\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M]\), \(Q = [H,I,J,Z,K,L,M]\)

9: Source node = \(H\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [I,J,Z,K,L,M]\)

10:Source node = \(I\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [J,Z,K,L,M]\)

11:Source node = \(J\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [Z,K,L,M]\)

12:Source node = \(Z\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [K,L,M]\)

13:Source node = \(K\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [L,M,Y]\)

14:Source node = \(L\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [M,Y]\)

15:Source node = \(M\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = [Y]\)

10:Source node = \(Y\), \(V = [A,B,C,D,E,F,G,H,I,J,Z,K,L,M,Y]\), \(Q = []\)

Breadth-first search has a running time of \(O(V + E)\) since every vertex and every edge will be checked once. Depending on the input to the graph, \(O(E)\) could be between \(O(1)\) and \(O(V^2)\).

DFS vs BFS

Breadth-first search is less space efficient than depth-first search because BFS keeps a priority queue of the entire frontier while DFS maintains a few pointers at each level.

If it is known that an answer will likely be found far into a tree, DFS is a better option than BFS. BFS is good to use when the depth of the tree can vary or if a single answer is needed — for example, the shortest path in a tree. If the entire tree should be traversed, DFS is a better option.

BFS always returns an optimal answer, but this is not guaranteed for DFS.

Breadth-first search can be used to solve games where a series of choices result in either a winning or losing state. For example, BFS can help a player determine a winning sequence of moves for solving a Rubik's cube.

BFS is also used in the famous Dijkstra’s algorithm for computing the shortest path in a graph and the Ford-Fulkerson algorithm for computing the maximum​ flow in a flow network.

Here is an example of a map that BFS can take and return the shortest paths.

^[3]

BFS runs on the map above and determines what the shortest routes between the cities are and produces the map below, which shows the best paths from city to city.

^[4]

• Depth-First Search

• Dijkstra's Algorithm

• Ford-Fulkerson Algorithm

1. Matheny, B. Animated BFS.gif. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:Animated_BFS.gif
2. Drichel, A. Breadth-first-tree. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:Breadth-first-tree.svg
3. , R. MapGermanyGraph.svg. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:MapGermanyGraph.svg
4. , R. GermanyBFS.svg. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:GermanyBFS.svg