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

Small program on Algorithms , Objective The goal of this project is to ext... Objective The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The ass

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ... Algorithm for Z-Buffer Method (a)  Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Size of stack, The size of stack was declared as ten. Thus, stack cannot ho... The size of stack was declared as ten. Thus, stack cannot hold more than ten elements. The major operations which can be performed onto a stack are push and pop. However, in a prog

Use of asymptotic notation in the study of algorithm, Q. What is the need o... Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Prims algorithm, Prim's algorithm employs the concept of sets. Rather than ... Prim's algorithm employs the concept of sets. Rather than processing the graph by sorted order of edges, this algorithm processes the edges within the graph randomly by building up

Implementation of stack, In this unit, we have learned how the stacks are i... In this unit, we have learned how the stacks are implemented using arrays and using liked list. Also, the advantages and disadvantages of using these two schemes were discussed. Fo

Question, A binary search tree is used to locate the number 43. Which of th... A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain. (a) 61 52 14 17 40 43 (b) 2 3 50 40 60 43 (c)

The smallest element of an array''s index, The smallest element of an array... The smallest element of an array's index is called its Lower bound.

C programming, bank database bank database

Procedures, what is far and near procedures in system programming? what is far and near procedures in system programming?