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
Write the algorithm for compound interest

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

A circular queue can be implemented through arrays or linked lists. Program 6 gives the array implementation of any circular queue. Program 6: Array implementation of any Circu

Program: Program segment for insertion of an element into the queue add(int value) { struct queue *new; new = (struct queue*)malloc(sizeof(queue)); new->value = val

What is Ruby Ruby has numerous simple types, including numeric classes such as Integer, Fixnum, Bignum, Float, Big Decimal, Rational, and Complex, textual classes like String,

Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

how to learn about time complexity of a particular algorithm

Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the sour

Range: A Structured Type in Ruby Ruby has a numerous structured types, comprising arrays, hashes, sets, classes, streams, and ranges. In this section we would only discuss rang

write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a