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
Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

QUESTION Explain the following data structures: (a) List (b) Stack (c) Queues Note : your explanation should consist of the definition, operations and examples.

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target

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

Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?

A graph G might be defined as a finite set V of vertices & a set E of edges (pair of connected vertices). The notation utilized is as follows: Graph G = (V, E) Consider the g

Program: Creation of a Circular linked list ALGORITHM (Insertion of an element into a Circular Linked List) Step 1        Begin Step 2      if the list is empty or new

write short note on algorithms

Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.

ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t