Breadth-First Search

DFS vs. BFS

DFS is a simple algorithm, but the path it finds to a Node may not be the shortest. In cases where that matters, you'll want to use Breadth-First Search (BFS) instead. Instead of following a path all the way to the end, BFS goes through a graph one level at a time:

You can view BFS in action with this Algorithm visualizer. Pick a start vertex and then click Run BFS.

BFS Algorithm

BFS begins at one node in a graph and visits all the neighboring nodes. It then goes to each of those neighbors to explore their unvisited neighbors in order. So it goes through the entire graph one level at a time, until the whole graph has been visited.

DFS was simple to implement, since you could use recursion to stack up the Nodes. However, BFS goes through the Nodes one level at a time, so you need a structure to keep track of the next nodes to be processed.

Q: What structure can be used to access items in the order they were put in?
A: A Queue (such as a LinkedList).

Before clicking below, see if you can describe of an Algorithm that uses a Queue to print the Nodes in a Graph in BFS order.