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
for(int i = 0; i for (int j = n - 1; j >= i ; j--){ System.out.println(i+ " " + j);

Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

The Space - Time Trade Off The best algorithm to solve a given problem is one that needs less space in memory and takes less time to complete its implementation. But in practic

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

Write an algorithm using pseudocode which takes temperatures input over a 100 day period (once per day) and output the number of days when the temperature was below 20C and the num

Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

I need help writing a pseudocode for my assignment can anyone help?

It is a naturally occurring sorting method exemplified through a card player arranging the cards dealt to him. He picks up the cards like they are dealt & added them into the neede