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

Programs, Develop a program that accepts the car registration( hint: LEA 43...

Develop a program that accepts the car registration( hint: LEA 43242010)

Insertion of a node into an avl tree, Initially Nodes are inserted in an AV...

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

Operations on b-trees, Operations on B-Trees Given are various operatio...

Operations on B-Trees Given are various operations which can be performed on B-Trees: Search Create Insert B-Tree does effort to minimize disk access and t

Search on a hashed file, Write a program to simulate searching over a hashe...

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Algorithm to insert a node in between any two nodes, Q. Write down an algor...

Q. Write down an algorithm to insert a node in between any two nodes in a linked list         Ans. Insertion of a the node after the given element of the listis as follows

Average case anaysis, what is the impoartance of average case analysis of ...

what is the impoartance of average case analysis of algorithm

Determine in brief about the boolean, Determine in brief about the Boolean ...

Determine in brief about the Boolean Carrier set of the Boolean ADT is the set {true, false}. Operations on these values are negation, conjunction, disjunction, conditional,

File organization, Define File organization''s and it''s types

Define File organization''s and it''s types

Explain worst fit method, Worst Fit method:- In this method the system alw...

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

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