Breadth First Search Algorithm


A breadth first search traversal method, visits all the successors of a visited node before visiting any successor of any of its child nodes. This is a contradiction to depth first traversal method; which visits the successor of a visited node before visiting any of its brothers, i.e., children of the same parent. A depth first traversal method tends to create very long, narrow trees; whereas breadth first traversal method tends to create very wide, short trees.

Given an input graph G = (V, E) and source vertex s, from where to begin. BFS systematically explores the edges of G to discover every vertex that is reachable from s. It produces a breadth first tree with root s that contains all such vertices that are reachable from s. For every vertex v reachable from s, the path in the breadth first tree from s to v corresponds to a shortest path. During the execution of the algorithm, each node n of G will be one of the three states, called the status of n as follows:

  • Status = 1 (ready state) : the initial state of a node n.
  • Status = 2 (waiting state) : the node n is on the queue or stack waiting to be processed.
  • Status = 3 (processed state) : the node has been processed.

Undirected Graph

graph breadth first search clip image002 Breadth First Search Algorithm

Adjacency list for above undirected graph.

graph breadth first search clip image004 Breadth First Search Algorithm

Algorithm:

Step 1: Initialize all nodes to ready state (status = 1)

Step 2: Put the starting node in queue and change its status to the waiting state (status = 2)

Step 3: Repeat step 4 and 5 until queue is empty

Step 4: Remove the front node n of queue. Process n and change the status of n to the processed state (status = 3)

Step 5: Add to the rear of the queue all the neighbors of n that are in ready state (status = 1), and change their status to the waiting state (status = 2). [End of the step 3 loop]

Step 6: Exit

Step 1: Initially add 2 to the queue.

graph breadth first search clip image006 Breadth First Search Algorithm

F=0

R=0

Step 2: Remove the front element 2 from queue by setting front = front +1 add to the queue the neighbors of 2.

graph breadth first search clip image008 Breadth First Search Algorithm

F=1

R=4

Step 3: Remove the front element 1 from queue by setting front = front +1 add to the queue the neighbors of 1.

graph breadth first search clip image010 Breadth First Search Algorithm

F=2

R=4

Step 4: Remove the front element 5 from queue by setting front = front +1 add to the queue the neighbors of 5.

graph breadth first search clip image012 Breadth First Search Algorithm

F=3

R=5

Step 5: Remove the front element 4 from queue by setting front = front +1 add to the queue the neighbors of 4.

graph breadth first search clip image014 Breadth First Search Algorithm

F=4

R=5

Step 6: Remove the front element 6 from queue by setting front = front +1 add to the queue the neighbors of 6

graph breadth first search clip image016 Breadth First Search Algorithm

F=5

R=5

Program illustrating Breadth First Search Algorithm

graph breadth first search clip image018 Breadth First Search Algorithm

graph breadth first search clip image020 Breadth First Search Algorithmgraph breadth first search clip image022 Breadth First Search Algorithm

graph breadth first search clip image024 Breadth First Search Algorithm

Output:

graph breadth first search clip image026 Breadth First Search Algorithm

graph breadth first search clip image028 Breadth First Search Algorithm

graph breadth first search clip image030 Breadth First Search Algorithm

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s