Breadth-first search, Data Structure & Algorithms

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)

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]
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

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
Related Questions
Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

Q. What do you understand by the term Hashing?  How do the collisions occur during hashing?  Explain the different techniques or methods for resolving the collision.

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse

Encryption the plain-text using the round keys: 1. (Key schedule) Implement an algorithm that will take a 128 bit key and generate the round keys for the AES encryption/decryp

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

Z-Buffer Algorithm Also known as the Depth-Buffer algorithm, this image-space method simply selects for  display the polygon or portion of a polygon that is nearest to the view

In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g. (define stack1 (make-stack))  (define stack2 (make-stack)) W

Differentiate between Nonpersistent and 1-persistent Nonpersistent: If the medium is idle, transmit; if the medium is busy, wait an amount of time drawn from a probability dist