Depth-first search (dfs) , Data Structure & Algorithms

In this respect depth-first search (DFS) is the exact reverse process: whenever it sends a new node, it immediately continues to extend from it. It sends back to previously explored nodes only if it lay out of options. Although DFS goes to unbalanced and strange-looking exploration trees related to the orderly layers created by BFS, the combination of eager exploration with the perfect memory of a computer creates DFS very useful. It sends an algorithm template for DFS. We send special algorithms from it by specifying the subroutines traverseTreeEdge, root, init, backtrack, and traverseNonTreeEdge.

DFS creates a node when it First discovers it; started all nodes are unmarked. The main loop of DFS seems for unmarked nodes s and calls DFS(s; s) to lead a tree rooted at s. The genuine call DFS(u; v) extends all edges (v;w) out of v. The argument (u; v) display that v was reached via the edge (u; v) into v. For root nodes s, we need the .dummy. argument (s; s). We display DFS(¤; v) if the special nature of the incoming node is irrelevant for the discussion at hand. Assume now that we explore edge (v;w) within the fact DFS(¤; v). If w has been seen after, w is a node of the DFS-tree. So (v;w) is not a tree node and hence we create traverseNonTreeEdge(v;w) and prepare no recursive call of DFS. If w has not been given before, (v;w) converts a tree edge. We therefore call traverseTreeEdge(v;w), mark w and create the recursive call DFS(v;w). When we return from this call we include the next edge out of v. Once all edges out of v are included, we call backtrack on the incoming edge (u; v) to operate any summarizing or clean-up operations return and required.

 

1300_Depth First Search (DFS).png

Posted Date: 7/27/2012 7:09:14 AM | Location : United States







Related Discussions:- Depth-first search (dfs) , Assignment Help, Ask Question on Depth-first search (dfs) , Get Answer, Expert's Help, Depth-first search (dfs) Discussions

Write discussion on Depth-first search (dfs)
Your posts are moderated
Related Questions
Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

write an algorithm for multiplication of two sparse matrices using Linked Lists

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Q. Write  down a   programme  in  C  to  create  a  single  linked  list also  write the functions to do the following operations (i)  To insert a new node at the end (ii

A shop sells books, maps and magazines. Every item is identified by a unique 4 - digit code. All books have a code starting with a 1, all maps have a code which starts with a 2 and

If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your mission (sho

Write an algorithm for binary search. Algorithm for Binary Search 1.  if (low> high) 2.  return (-1) 3.  Mid = (low + high)/2 4.  if ( X = = a[mid]) 5.  return (mid); 6.

Explain the Interfaces in Ruby Recall that in object-oriented programming, an interface is a collection of abstract operations that cannot be instantiated. Even though Ruby i

Write a program to create a hashed file that stores the records currently in the file " data_2013 ". Records should use the same fixed-length schema given previously, and should ag

Explain the theory of computational complexity A  problem's  intractability  remains  the  similar  for  all  principal  models  of   computations    and   all reasonable inpu