Depth first traversal, Data Structure & Algorithms

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then recursively visits all the vertices adjoining to that node. The catch is that the graph may contain cycles, but the traversal must visit each vertex at most once. The solution to the problem is to keep track of the nodes that have been visited, so that the traversal does not experience the fate of infinite recursion.



Posted Date: 7/10/2012 3:36:16 AM | Location : United States

Related Discussions:- Depth first traversal, Assignment Help, Ask Question on Depth first traversal, Get Answer, Expert's Help, Depth first traversal Discussions

Write discussion on Depth first traversal
Your posts are moderated
Related Questions
Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma

Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays.  The first array should contain the numbers as they are generated.  The

What is a Binary Search Tree (BST)? A binary search tree B is a binary tree every node of which satisfies the three conditions: 1.  The value of the left-subtree of 'x' is le

Decision Tree - ID3 algorithm: Imagine you only ever do one of the following four things for any weekend:   go shopping   watch a movie   play tennis   just

What are the things require to implement ADT Abstract data types are very useful for helping us understand the mathematical objects which we use in our computations but, of cou

Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

Q. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (