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
Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n

How to create an General Tree and how to search general tree?

Q. State the difference between a grounded header link list and a circular header link list?     Ans: A header linked list is a linked list which all the time c

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s

Write a C++ program with header and source les to store street addresses using the Doubly Linked List ADT. Modify the Node class from Lab Assignment 3 so that it becomes a node in

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

The below formula is used to calculate n: n = (x * x)/ (1 - x). Value x = 0 is used to stop the algorithm. Calculation is repeated using values of x until value x = 0 is input. The

Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Q. The two Binary Trees are said to be similar if they are both empty or if they are both non- empty and left and right sub trees are similar. Write down an algorithm to determine