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

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

Collision resolution techniques, complete information about collision resol...

complete information about collision resolution techniques

Sorting, Define Hashing. Store the following values in a hash table of tabl...

Define Hashing. Store the following values in a hash table of table size 11 using division method: 25, 42, 96, 101, 102, 162, and 197. In case of collision, use other hash functio

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Delete a given node from a doubly linked list, Algorithm to Delete a given ...

Algorithm to Delete a given node from a doubly linked list Delete a Node from Double Linked List DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FOR

Show that towers of hanoi is o (2n), Question 1 Discuss the advantages of ...

Question 1 Discuss the advantages of implementation checks preconditions Question 2 Write a ‘C' program to search for an item using binary search Question 3 Show that To

Graphs, floyd warshall algorithm

floyd warshall algorithm

Explain state space tree, Explain State Space Tree If it is convenient ...

Explain State Space Tree If it is convenient to execute backtracking by constructing a tree of choices being made, the tree is known as a state space tree. Its root indicates a

Algorithm, write an algorithm for the gpa of six students

write an algorithm for the gpa of six students

Stack, using a program flowchart design a program to illustrate pop and pus...

using a program flowchart design a program to illustrate pop and push operation

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