Breadth First Search on Graphs

Prereq: Graph Intro

Tree vs Graph Traversal

A tree is a connected, acyclic undirected graph. Statistically, most interview graph problems are about connected and undirected graphs. For simplicity, let's define a tree as a graph without any cycle. The search algorithms we have learned in tree modules are applicable to graphs as well.

Hopefully, by this point, you are very familiar with DFS on trees and BFS on trees. Since the difference between a tree and a graph is the possibility of having a cycle, we just have to handle this situation. We use an extra visited variable to keep track of vertices we have already visited to prevent re-visiting and getting into infinite loops. visited can be any data structure that can answer existence queries quickly. For example, a hash set or an array where each element maps to a vertex in the graph can both do this in constant time.