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
What is the best case complexity of quick sort In the best case complexity, the pivot is in the middle.

If a Dequeue is implemented via arrays, then this will suffer with the similar problems which a linear queue had suffered. Program 8 gives the array implementation of Dequeue.

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.

State in detail about the Integer Carrier set of the Integer ADT is the set {..., -2, -1, 0, 1, 2, ...}, and  operations on these values are addition, multiplication, subtrac

What are stacks? A stack is a data structure that organizes data similar to how one organizes a pile of coins. The new coin is always placed on the top and the oldest is on the

A geography class decide to measure daily temperatures and hours of sunshine each day over a 12 month period (365 days) Write an algorithm, using a flowchart that inputs tempera

I am looking for some help with a data mining class with questions that are about neural networks and decision trees. Can you help? I can send document with questions.

what is tree

Implementation of Stack :- Stacks can be executed in the 2 ways: a)  Arrays b)  Linked List

D elete a specific Node from Double Linked List as follows DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FORW [ BACK [LOC]]:= FORW[LOC]& BACK [FORW[