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

Big o notation, This notation gives an upper bound for a function to within... This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n))

What are circular queues, What are circular queues?  Circular queue: St... What are circular queues?  Circular queue: Static queues have a very large drawback that once the queue is FULL, even though we erase few elements from the "front" and relieve

DAA, what do we use asymptotic notation in study of algorithm?Describe vari... what do we use asymptotic notation in study of algorithm?Describe various asymptotic notation and give their significance.

Explain multiplication method, Multiplication Method: The multiplication m... Multiplication Method: The multiplication method operates in 2 steps. In the 1ststep the key value K is multiplied by a constant A in the range O

Find strongly connected components - dfs, A striking application of DFS is ... A striking application of DFS is determine a strongly connected component of a graph. Definition: For graph G = (V, E) , where V refer to the set of vertices and E refer to the

Write an algorithm for binary search, Q.1 Write procedures/ Algorithm to in... Q.1 Write procedures/ Algorithm to insert and delete an element in to array. Q.2. Write an algorithm for binary search. What are the conditions under which sequential search of

C++, #What is the pointer #What is the pointer

Branch and bound algorithm, Suppose we have a set of N agents and a set of ... Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a

Balance theorem, Question 1 Discuss the following theorems with respect to... Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation

Sorting algorithm, Sorting Algorithm A sorting algorithm is an algorit... Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff