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

Queues, what is the difference between data type and abstract data type

what is the difference between data type and abstract data type

Areas of use - sequential files, Sequential files are most frequently utili...

Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

Data communication, #question.explain different types of errors in data tra...

#question.explain different types of errors in data transmission.

Algorithms, Write an algorithm to print all even numbers in descending orde...

Write an algorithm to print all even numbers in descending order and draw the flowchart

Algo for quicksort, Easy algorithm for beginner for quicksort with explanat...

Easy algorithm for beginner for quicksort with explanation

Implementation of a binary tree, Like general tree, binary trees are implem...

Like general tree, binary trees are implemented through linked lists. A typical node in a Binary tree has a structure as follows struct NODE { struct NODE *leftchild; i

Queue, what''s queue ?

what''s queue ?

Abstract data type-tree, Definition: A set of data values & related operati...

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

Binary trees, A binary tree is a special tree where each non-leaf node can ...

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

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