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

Brute force, Determine the number of character comparisons made by the brut...

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Find the optimal control, 1. Use the Weierstrass condition, find the (Stron...

1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where

The space - time trade off, The Space - Time Trade Off The best algorit...

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic

An undirected graph g with n vertices and e edges, An undirected graph G wi...

An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

Execute algorithm to convert infix into post fix expression, Q. Execute you...

Q. Execute your algorithm to convert the infix expression to the post fix expression with the given infix expression as input Q = [(A + B)/(C + D) ↑ (E / F)]+ (G + H)/ I

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

Program segment for the deletion of any element from the queue delmq(i)  /* Delete any element from queue i */ { int i,x; if ( front[i] == rear[i]) printf("Queue is

Searching techniques, Searching is the procedure of looking for something. ...

Searching is the procedure of looking for something. Searching a list containing 100000 elements is not the similar as searching a list containing 10 elements. We discussed two sea

Define game trees, Game trees An interesting application of trees is th...

Game trees An interesting application of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can picture the sequence of possible moves by m

Binary search tree (bst), Q. Explain what do we understand by Binary Search...

Q. Explain what do we understand by Binary Search Tree (BST)? Make a BST for the following given sequence of the numbers. 45, 32, 90, 21, 78, 65, 87, 132, 90, 96, 41, 74, 92

The game tree, An interesting application or implementation of trees is the...

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves

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