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)

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







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
Enumerate about the concept of container A Container can have a size() operation. We can also ask (somewhat redundantly) whether a Container is empty. And even though a Contain

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

How To implement stack using two queues , analyze the running time of the stack operations ?

algorithm for multiplication of two sparse matrices using linked lists..

Beauty Salon is a system to be designed to manage the booking and the payment of a single beauty parlour. Beauty Therapists: A beauty parlour has a number of staff members mo

Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

Linked List  A linked list is a linear collection of data elements called nodes. The linear order is given by pointer. Every node is divided into 2 or more parts.

Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

A spanning tree of any graph is only a subgraph that keeps all the vertices and is a tree (having no cycle). A graph might have many spanning trees. Figure: A Graph