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
Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Q. Describe the representations of graph. Represent the graph which is given to us using any two methods Ans: The different ways by which we can represent graphs are:

There are ten stations on a railway line: Train travels in both directions (i.e. from 1 to 10 and then from 10 to 1).  Fare between each station is $2. A passenger input

A graph with n vertices will absolutely have a parallel edge or self loop if the total number of edges is greater than n-1

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

what is tower of management with example

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn