Depth first search and breadth first search, Data Structure & Algorithms

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.  

1844_DFS and BFS.png

 

Ans:

Depth first search (DFS):

917_DFS.png

 

Depth first search (DFS) beginning from vertex 3 as source and traversing above adjacency list one by one, the following result is obtained:

3-7-2-8-6-5-4-1

 Breadth First Search(BFS):

348_BFS.png

In this elements are inserted from rear and deleted from front. Before removing an element, insert its element in the queue. So result get of BFS in the given graph is:

3-7-2-8-6-5-4-1

Posted Date: 7/10/2012 2:58:43 AM | Location : United States







Related Discussions:- Depth first search and breadth first search, Assignment Help, Ask Question on Depth first search and breadth first search, Get Answer, Expert's Help, Depth first search and breadth first search Discussions

Write discussion on Depth first search and breadth first search
Your posts are moderated
Related Questions
Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

The complexity of multiplying two matrices of order m*n and n*p is    mnp

State  in brief about assertion Assertion: A statement which should be true at a designated point in a program.

padovan string

what are the applications of multikey file organization?

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

what is an algorithms

Q. Describe the term array.  How do we represent two-dimensional arrays in memory?  Explain how we calculate the address of an element in a two dimensional array.

Phong Shading Phong shading too is based on interpolation, but instead of interpolating the colour value, it is the normal vector, which is interpolated for each point and a co

Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu