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



Depth first search (DFS):



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


 Breadth First Search(BFS):


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:


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
Describe Binary Search Tree (BST)? Make a BST for the given sequence of numbers. 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the obtained tree in Preorder, Inord

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

Binary search technique:-  This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is separated into t

Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

You are given an undirected graph G = (V, E) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight of either {1,2,...,W}, where W

Question 1 Describe the following- Well known Sorting Algorithms Divide and Conquer Techniques Question 2 Describe in your own words the different asymptotic func

Two linked lists are having information of the same type in ascending order. Write down a module to merge them to a single linked list that is sorted merge(struct node *p, stru