Breadth First Search (BFS) is an algorithm for traversing and searching a graph/tree layer-wise. It starts at an arbitrary node and explores all of the neighbour nodes before moving to the next depth level

For the above graph with 0 as the starting vertex, the traversing order will be 0 -> 1 -> 2 -> 3 -> 4

Implementation example


  • Using an array to track visited nodes to avoid processing a node more than once (graph may contain cycles)
  • Using a queue to track which nodes to visit next

UndirectedGraphByAdjacencyList is defined in Graph Data Structure