Learn the basic algorithms for traversing trees and graphs.
Premium Content - Free Preview
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 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.
In the description below, to process a Node means to mark the Node as visited, add it to the queue and print out its value,.
- Create a Queue for keeping track of the nodes or numbers that still need to be explored.
- process the starting Node. As long as you still have nodes in the Queue:
- Dequeue a Node and get its adjacent nodes as a list
- process every adjacent node in the list that's not yet visited.