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

Define spanning tree, Define Spanning Tree A Spanning Tree of a connect...

Define Spanning Tree A Spanning Tree of a connected graph is its linked acyclic sub graph (i.e., a tree) that having all the vertices of the graph.

Explain cam software, Explain CAM software CAD/CAM software has been re...

Explain CAM software CAD/CAM software has been recognized as an essential tool in the designing and manufacturing of a product due to its ability to depict the designs and tool

Write an algorithm for binary search., Write an algorithm for binary search...

Write an algorithm for binary search. Algorithm for Binary Search 1.  if (low> high) 2.  return (-1) 3.  Mid = (low + high)/2 4.  if ( X = = a[mid]) 5.  return (mid); 6.

Program segment for deletion of any element from the queue, Program segment...

Program segment for deletion of any element from the queue delete() { int delvalue = 0; if (front == NULL) printf("Queue Empty"); { delvalue = front->value;

Determine the precondition of a binary search, Determine the precondition o...

Determine the precondition of a binary search For instance, precondition of a binary search is that array searched is sorted however checking this precondition is so expensive

Infix expression into the postfix expression, Q. Convert the given infix ex...

Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix

Deletion, sir how can i explain deletion process in a data structure

sir how can i explain deletion process in a data structure

Find the complexity of an algorithm, Q.1 What is an algorithm? What are the...

Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

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