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
Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree.              A n s . The algorithm to check whether a Binary tree is as Binary Search

What is an algorithm?  What are the characteristics of a good algorithm? An algorithm is "a step-by-step process for accomplishing some task'' An algorithm can be given in many

1. develop an algorithm which reads two decimal numbers x and y and determines and prints out wether x>y or y>x. the input values, x and y, are whole number > or equal to 0, which

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

What are stacks? A stack is a data structure that organizes data similar to how one organizes a pile of coins. The new coin is always placed on the top and the oldest is on the

A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

Q. Let X = (X1, X2, X3,....Xn) and Y= (Y1, Y2, Y3,....Xm) be the two linked lists respectively. Write down an algorithm to merge the lists together to get the linked list Z such th