Breadth-First Search/Traversal in a Graph.

Breadth-First Search ( or Tra­ver­sal)  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 neigh­bors. (Ref­er­ence — Wiki)

Mit Open Courseware session on Breadth first search

Approach:

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

Graph-BFS

Complete Code:

Output:
0 2 1 3 4 5

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: