Learn the basic algorithms for traversing trees and graphs.

# Breadth-First Search

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 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.

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,.

**BFS Algorithm**:

- 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.

End of Free Content Preview. Please Sign in or Sign up to buy premium content.

## Comments

## Igor Naverniouk

Sep 17, 3:34 PMWhy is "0 2 3 5 4 1" not a correct answer for input #1?

## Learneroo

Sep 17, 3:41 PMIt's a valid BFS, but for this challenge you should visit nodes on one level in the order they were in their line of input.

## Igor Naverniouk

Sep 17, 3:49 PMThat's not specified in the problem statement.

## Learneroo

Sep 17, 4:04 PMThanks. It was mentioned previously, and I updated it so it's mentioned here as well.