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
Stacks are often used in evaluation of arithmetic expressions. An arithmetic expression contains operands & operators. Polish notations are evaluated through stacks. Conversions of

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most

1. A string s is said to be periodic with a period α, if s is α k for some k > 2. (Note that α k is the string formed by concatenating k times.) A DNA sequence s is called a tand

Write an algorithm for binary search. What are its limitations? .

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

Write the algorithm for compound interest

Comparison of Gouraud and Phong Shading Phong shading requires more calculations, but produces better results for specular reflection than Gouraud shading in the form of more r

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff