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

Which sorting algorithms not have running time of o (n2), Which sorting al...

Which sorting algorithms does not have a worst case running time of  O (n 2 ) ? Merge sort

Red-black tree after insertion, The above 3 cases are also considered conve...

The above 3 cases are also considered conversely while the parent of Z is to the right of its own parent. All the different kind of cases can be illustrated through an instance. Le

Insert an element after an element pointed by some pointer, Consider a link...

Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer? O (1)

Algorithms & flowchart, write an algorithm to find the average number of oc...

write an algorithm to find the average number of occurances of MECHANIL in an english passage

Define algorithm, What is an Algorithm? An algorithm is a sequence of u...

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Applications in file systems of avl trees, 1. In computer science, a classi...

1. In computer science, a classic problem is how to dynamically store information so as to let for quick look up. This searching problem arises frequently in dictionaries, symbol t

find shortest path from a to z using dijkstra''s algorithm., Q.  In the gi...

Q.  In the given figure find the shortest path from A to Z using Dijkstra's Algorithm.    Ans: 1.  P=φ;  T={A,B,C,D,E,F,G,H,I,J,K,L,M,Z} Let L(A)

Write an algorithm of value in tax using pseudocode, A town contains a tota...

A town contains a total of 5000 houses. Every house owner has to pay tax based on value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.

Graphs, In this unit, we will describe a data structure called Graph. Actua...

In this unit, we will describe a data structure called Graph. Actually, graph is a general tree along no parent-child relationship. In computer science, Graphs have several applica

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