This post is completed by 3 users

  • 1
 Add to List
Beginner

152. Breadth-First Search/Traversal in a Graph

Breadth-First Search ( or Tra­ver­sal) (BFS) in a Graph is quite similar to Binary Tree. Click here to read about BFS in Binary Tree.

Example:

Graph BFS

What is Breadth-First Search:

Breadth-first search (BFS) is an algo­rithm for tra­vers­ing or search­ing tree or graph data struc­tures. It starts at the tree root and explores the neigh­bor nodes first, before mov­ing to the next level of neigh­bors. (Ref­er­ence — Wiki)

Approach:

  1. For Graph as well we will use the Queue for performing the BFS.
  2. We will use the boolean[] to keep track of the nodes because, unlike trees during traversal, we might keep moving into the circles by visiting the same nodes repeatedly.
  3. In our example, we are using an adjacency List for the Graph Representation.
Graph-BFS
Graph-BFS

 
Output:
0 2 1 3 4 5

Related Problems: