CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page

Was this helpful?

  1. Algorithms
  2. Searching

Breadth First Search (BFS)

PreviousDepth First Search (DFS)NextShortest Paths

Last updated 5 years ago

Was this helpful?

Breadth First Search (BFS), like , is a method of traversing a graph. BFS simply traverses in a different order, but otherwise is very similar to DFS.

The main difference is that BFS visits all children before any subgraphs. In a tree, we call this level order.

For the example tree above, a level order traversal would go in this order: D B F A C E G.

Step by Step

Let's see how we might implement BFS.

Some data structures we will need are:

  • A graph to traverse.

  • A queue Q to keep track of which nodes need to be processed next.

  • A list of booleans marked to keep track of which nodes were already visited.

First, let's start with a vertex in the graph by marking it and adding it to the queue.

The next step is to remove A from the queue and add its children (B and C) to the queue. Also, we need to mark all of the children.

Next, we'll move onto the next item on the queue (B). We'll do the same thing that we did with A: remove B, mark all its children, and add its children to the queue. Since C is already marked, we do not add it to the queue again.

Now, we'll move on to the next item on the queue, C, and do the same thing. Again, we won't add C or A because they are both marked.

Finally, we'll visit the two remaining nodes in the queue, D and E. Since all of the nodes are marked now, there aren't any other nodes to visit.

(Optional) edgeTo and distTo to keep track of information that might be useful for other applications (like ).

Dijkstra's Algorithm
Depth First Search (DFS)