Breadth-first search starts at a given vertex h, which is at level 0. In the first stage, we go to
all the vertices that are at the distance of one edge away. When we go there, we marked
as "visited," the vertices adjacent to the start vertex s - these vertices are placed into level 1.
In the second stage, we go to all the new vertices we can reach at the distance of two edges
away from the source vertex h. These new vertices, which are adjacent to level 1 vertex and not
previously assigned to a level, are placed into level 2. The BFS traversal ends when each vertex
has been finished.

The BFS(G, a) algorithm creates a breadth-first search tree with the source vertex, s, as its root.
The predecessor or parent of any other vertex in the tree is the vertex from which it was first
developed. For every vertex, v, the parent of v is marked in the variable π[v]. Another variable,
d[v], calculated by BFS has the number of tree edges on the way from s tov. The breadth-first
search needs a FIFO queue, Q, to store red vertices.

Algorithm: Breadth-First Search Traversal

BFS(V, E, a)

1.
2.             do color[u] ← BLACK
3.                 d[u] ← infinity
4.                 π[u] ← NIL
5.         color[s] ← RED                 ? Source vertex find
6.         d[a] ← 0                               ? Start
7.         π[a] ← NIL                           ? Stat
8.         Q ← {}                                ? Empty queue Q
9.         ENQUEUE(Q, a)
10        while Q is non-empty
11.             do u ← DEQUEUE(Q)                   ? That is, u = head[Q]
12.
13.                         do if color[v] ← BLACK    ? if color is black you've never seen it before
14.                                 then  color[v] ← RED
15.                                          d[v] ← d[u] + 1
16.                                          π[v] ← u
17.                                          ENQUEUE(Q, v)
18.                 DEQUEUE(Q)
19.         color[u] ← BLACK

 

 

Posted Date: 7/27/2012 8:14:48 AM | Location : United States

Ask an Expert

Related Discussions:- Breadth-first search, Assignment Help, Ask Question on Breadth-first search, Get Answer, Expert's Help, Breadth-first search Discussions

Write discussion on Breadth-first search
Your posts are moderated

Write your message here..

Related Questions

Convert a binary tree into its mirror image by traversing it, One can chang... One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.

What is string, What is String Carrier set of the String ADT is the s... What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s

Process of decision making under uncertainty, (a) Describe the steps involv... (a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c

Array and two-dimensional array, Q. Describe the term array.  How do we rep... Q. Describe the term array.  How do we represent two-dimensional arrays in memory?  Explain how we calculate the address of an element in a two dimensional array.

Sparse metrics, Q. Define the sparse metrics and also explain the represent... Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

Define the terms - key attribute and value set, Define the terms   ... Define the terms     i) Key attribute     ii) Value set  Key attribute:  An entity  type  usually  has  an attribute  whose  values  are  distinct  fr

State the ruby programming language, The Ruby Programming Language Alth... The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

String manipulation, what is string manipulation? what is string manipulation?

Process of in-order traversal, In-order Traversal  This process when ex... In-order Traversal  This process when executed iteratively also needs a stack and a Boolean to prevent the implementation from traversing any portion of a tree twice. The gener

Binary tree with depth 3, Q. Construct a complete binary tree with depth 3 ... Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t