Breadth-first search, Data Structure & Algorithms

Assignment Help:

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

 

 


Related Discussions:- Breadth-first search

Simplifying assumptions of wire frame representation, Simplifying Assumptio...

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

Matrices multiplication, Write an algorithm for multiplication of two spars...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

What is assertions, What is Assertions Introduction At every point...

What is Assertions Introduction At every point in a program, there are generally constraints on the computational state that should hold for program to be correct. For ins

Advanced data structures, In this unit, the following four advanced data st...

In this unit, the following four advanced data structures have been practically emphasized. These may be considered as alternative to a height balanced tree, i.e., AVL tree.

Add the special form let to the metacircular interpreter, (1)  (i) Add the ...

(1)  (i) Add the special form let to the metacircular interpreter Hint: remember let is just syntactic sugar for a lambda expression and so a rewrite to the lambda form is all t

Need help with working out. I dont really get it, Suppose there are exactly...

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

Double linked list, In a doubly linked list, also called as 2 way list, eac...

In a doubly linked list, also called as 2 way list, each node is divided into 3 parts. The first part is called previous pointer field. It contains the address of the preceding

Graph traversal schemes, Various graph traversal schemes Graph Traversa...

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

Bayesian statistics question, Suppose that there is a Beta(2,2) prior distr...

Suppose that there is a Beta(2,2) prior distribution on the probability theta that a coin will yield a "head" when spun in a specified manner. The coin is independently spun 10 tim

Illustrate hls colour model, HLS Colour Model  This model has the doub...

HLS Colour Model  This model has the double-cone representation shown in Figure 3.40. The three colour parameters in this model are called hue (H), lightness (L), and Saturati

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd