Breadthfirst search (BFS)
Breadthfirst 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 breadthfirst search are useful for analyzing and solving graph problems.
Contents
Breadth First Search
Breadthfirst 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:
For a graph \(G = (V,E)\) and a source vertex \(v\), breadthfirst 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 breadthfirst 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 breadthfirst 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 breadthfirst search would visit the nodes in.
What is the state of the queue at each iteration of BFS if it is called from node 'a'?
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}{lr} \textbf{Node Visited} & \textbf{Queue} \\ \hline \text{a} & \text{a} \\ \text{ } & \text{(empty)} \\ \text{b } & \text{b} \\ \text{f } & \text{b 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}\]
Implementing Breadth First Search
Here is a pseudocode implementation of breadthfirst search.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 

For the following graph, perform a breadthfirst 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,D,E]\), \(Q = [B,D,E]\)
3: Source node = \(B\), \(V = [A,B,D,E,C]\), \(Q = [D,E,C]\)
4: Source node = \(D\), \(V = [A,B,D,E,C]\), \(Q = [E,C]\)
5: Source node = \(E\), \(V = [A,B,D,E,C,F]\), \(Q = [C,F]\)
6: Source node = \(C\), \(V = [A,B,D,E,C,F]\), \(Q = [F]\)
7: Source node = \(F\), \(V = [A,B,D,E,C,F,G,H]\), \(Q = [G,H]\)
8: Source node = \(G\), \(V = [A,B,D,E,C,F,G,H]\), \(Q = [H]\)
9: Source node = \(H\), \(V = [A,B,D,E,C,F,G,H]\), \(Q = []\)
Complexity of Breadth First Search
Breadthfirst 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
Breadthfirst search is less space efficient than depthfirst 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.
Applications
Breadthfirst 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 FordFulkerson 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.
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.
See Also
References
 Matheny, B. Animated BFS.gif. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:Animated_BFS.gif
 Drichel, A. Breadthfirsttree. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:Breadthfirsttree.svg
 , R. MapGermanyGraph.svg. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:MapGermanyGraph.svg
 , R. GermanyBFS.svg. Retrieved June 8, 2016, from https://en.wikipedia.org/wiki/File:GermanyBFS.svg