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
Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

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 rec

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

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For

(1) Sort a list of distinct numbers in ascending order, using the following divide- and-conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains a

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

write an algorithm given each students name and grade points for six courses.find his grade point average and group students into the gpa groups 3.5

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

Explain principle of Optimality It indicates that an optimal solution to any instance of an optimization problem is composed of  optimal solutions to its subinstances.

Threaded Binary Tree:- By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using