Going Broad In A Graph: BFS Traversal

Vaidehi Joshi
Sep 18, 2017 · 15 min read
Breadth-first search graph traversal

Searching through a graph

If you’re feeling a serious cases of déjà vu and thinking to yourself that we’ve already covered breadth-first search earlier in this series, then you’d be correct! In fact, we’ve covered depth-first search in this series as well! So why is it showing up again, since we already are experts at both of these algorithms?

Graph traversal: a definition
DFS and BFS: a quick review
Graph traversal can begin anywhere!

Step-by-step BFS traversal

Once we’ve chosen a starting point for our search, we have one major thing out of the way. The process of actually searching by breadth in a graph can be boiled down to a few steps, which we’ll continue to repeat again and again, until we have no more nodes left to check.

  1. Visit the topmost node in the queue, and mark it as such.
  2. If that node has any neighbors, check to see if they have been “visited” or not.
  3. Add any neighboring nodes that still need to be “visited” to the queue.
  4. Remove the node we’ve visited from the queue.
BFS, part 1
BFS, part 2
BFS, part 3
BFS, part 4
BFS, part 5
Shortest paths in BFS graph traversal
The power of BFS traversal

The power of using breadth-first search to traverse through a graph is that it can easily tell us the shortest way to get from one node to another.

This is particularly helpful for huge graphs, which are fairly common in computer science problems. For example, in the image illustrated here, we might have many nodes and many levels, and want to be able to know how many steps to get from level 0 to the last level (whatever that might be). Having easy access to the shortest path(s) in this graph is super useful in solving this problem.

The complexities of breadth-first search

Learning about an algorithm like breadth-first search graph is exciting, but it’s not nearly as fun without knowing how efficient it actually will be in traversing through a graph! The best way to understand the runtime complexity of BFS graph traversal is by examining how it actually operates on a graph representation — in other words, by examining how the algorithm will function on a real graph, in its programmatic format.

An adjacency list representation of a graph using BFS
Marking vertices as “visited”
  1. Then, after changing its value from FALSE to TRUE in the “visited” array, we’d enqueue it.
  2. Next, when dequeing the vertex, we need to examine its neighboring nodes, and iterate (loop) through its adjacent linked list. Node b has two neighboring nodes, located at indices 0 and 5 respectively.
  3. If either of those neighboring nodes hasn’t been visited (doesn’t have a state of TRUE in the “visited” array), we’d mark it as visited, and enqueue it.
  4. Finally, we’ll keep doing this until we reach a NULL (empty) pointer in the linked list, before moving on to the next node in the queue. Once the queue is totally empty, we know that we’re done running the algorithm.
The runtime complexity of BFS graph traversal

If we must visit every node once, and check every edge in its adjacency list, the runtime complexity for both a directed and undirected graph is the sum of the vertices and their edges as represented by the graph in its adjacency list representation, or O(V + E)

For an undirected graph, this means we visit all the vertices (V), and 2|E| edges. For a directed graph, this means we visit all the vertices (V) and |E| edges. The size of an adjacency list representation of a graph is directly related to how much time it will take us to traverse through it using breadth-first search, which makes it a linear algorithm!

Resources

Because BFS (and DFS!) are both well-known algorithms, it’s not too difficult to find resources that dive into the nitty-gritty of how they operate. If you’re looking to learn more, or want to read about some the more complex aspects of this algorithms, here are some great resources to start with!

  1. Breadth-First Search, Department of Computer Science, Harvard
  2. Breadth-first Search (BFS) on Graphs Part 2 — Implementation, Sesh Venugopal
  3. Breadth-First Search (BFS), MIT OpenCourseWare
  4. Graph Traversals — Breadth First and Depth First, CollegeQuery

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.