Breadth first search, Data Structure & Algorithms

Assignment Help:

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part of the search. The approach adopted in breadth first search is to begin search at a vertex(source). Once you begun at source, the number of vertices that are visited as part of the search is 1 and all the remaining vertices need to be visited.

Then, search the vertices that are adjacent to the visited vertex from left to order. In this way, all of the vertices of the graph are searched.

Let the digraph of Figure. Assume that the search begun from S. Now, the vertices (from left to right) adjacent to S that are not visited as part of the search are B, C, A. So, B,C and A are visited after S as portion of the BFS. Then, F is the unvisited vertex adjacent to B. hence, the visit to B, C & A is followed by F. The unvisited vertex adjacent of C is D. Thus, the visit to F is followed by D. There are no unvisited vertices adjacent to A. At last, the unvisited vertex E adjacent to D is visited.

So, the sequence of vertices visited as part of BFS is S, B, C, A, F, D and E.


Related Discussions:- Breadth first search

Algorithm for sorting a deck of cards, What is wrong with the following alg...

What is wrong with the following algorithm for sorting a deck of cards (considering the basic properties of algorithms)? I. Put the cards together into a pile II. For each ca

Operation of algorithm, Operation of Algorithm The following sequence o...

Operation of Algorithm The following sequence of diagrams shows the operation of Dijkstra's Algorithm. The bold vertices show the vertex to which shortest path has been find ou

Adjacency matrix, Q. Give the adjacency matrix for the graph drawn below:  ...

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

Physical database design and sql queries, In this part, students are allowe...

In this part, students are allowed to implement the following simplifications in their table and data design. o Availability for the beauty therapists don't have to be considere

Determine the complexity, 1)    The set of the algorithms whose order is O ...

1)    The set of the algorithms whose order is O (1) would run in the identical time.  True/False 2)    Determine the complexity of the following program into big O notation:

C++, 7. String manipulation 7.a Write a C Program using following strin...

7. String manipulation 7.a Write a C Program using following string manipulation functions a) strcpy b) strncpy c) strcmp d) strncmp e) strlen f) strcat

Which of the sorting algorithm is stable, Which of the sorting algorithm is...

Which of the sorting algorithm is stable   Heap sorting is stable.

Simulation of queues, Simulation of queues: Simulation is the process of f...

Simulation of queues: Simulation is the process of forming an abstract model of a real world situation in order to understand the effect of modifications and the effect of introdu

Algorithm, Algorithm to find sum of square of a number

Algorithm to find sum of square of a number

Splaying procedure, For splaying, three trees are maintained, the central, ...

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target

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