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

For loop, for (i = 0; i sequence of statements } Here, the loop e... for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

Deletion algorithm for dequeue, Deletion Algorithm for dequeue Step 1:... Deletion Algorithm for dequeue Step 1: [check for underflow]   If front = 0 and rear = 0   Output "underflow" and return Step 2: [delete element at front end]   If front

Determine about the post conditions assertion, Determine about the Post con... Determine about the Post conditions assertion A  post condition is an assertion which should be true at completion of an operation. For instance, a post condition of the squ

Sort list of distinct numbers in ascending order - quicksort, (1) Sort a li... (1) Sort a list of distinct numbers in ascending order, using the following divide- and-conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains a

Omega notation, The ?-Notation (Lower Bound) This notation provides a l... The ?-Notation (Lower Bound) This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n 0 and

Sorted list followed by a few "random" elements, You have to sort a list L ... You have to sort a list L having of a sorted list followed by a few "random" elements. Which sorting methods would be especially suitable for this type of task?   Insertion sort

Difference between array and abstract data types, Difference between array ... Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Indexed sequential files, Indexed Sequential Files An index is inserted... Indexed Sequential Files An index is inserted to the sequential file to provide random access. An overflow area required to be maintained to permit insertion in sequence. I

Define threaded binary tree, Threaded Binary Tree:- By changing the NUL... Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using

find shortest path from a to z using dijkstra''s algorithm., Q.  In the gi... Q.  In the given figure find the shortest path from A to Z using Dijkstra's Algorithm.    Ans: 1.  P=φ;  T={A,B,C,D,E,F,G,H,I,J,K,L,M,Z} Let L(A)