Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Breadth-First Search/Traversal in a Graph.

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

Exam­ple:

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 Course­ware ses­sion on Breadth first search

Approach:

  1. For Graph as well we will use the Queue for per­form­ing the BFS.
  2. We will use the boolean[] to keep a track of the nodes because unlike tree dur­ing tra­ver­sal we might keep mov­ing into the cir­cles by vis­it­ing same nodes repeatedly.
  3. In our exam­ple we are using adja­cency List for the Graph Rep­re­sen­ta­tion.
Graph-BFS

Graph-BFS

Com­plete Code:

Output:
0 2 1 3 4 5

You may also like...