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
Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

Q.1 Write procedures/ Algorithm to insert and delete an element in to array. Q.2. Write an algorithm for binary search. What are the conditions under which sequential search of

Threaded Binary Tree : If a node in a binary tree is not having left or right child or it is a leaf node then that absence of child node is shown by the null pointers. The spac

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma

I need a person who has a good background in using R. Studio? In adition, a person who is good in using algorithms.

Description A heap is an efficient tree-based data structure that can be used as a priority queue. Recall that the abstract data type of a priority queue has the following opera

what happen''s in my computer when i input any passage

Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Define Merge Sort  Merge sort is a perfect example of a successful application of the divide and conquer method. It sorts a given array A[0...n-l] by separating it into two ha

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.