Register

depth first traversal

1,953 views
0 0 votes

1 Answer

3 3 votes

If there are  n leave nodes ===> you should  at least (n-1) back tracks.. .

Here there are 2 leave nodes ===> you should need atleast 1 back track. but with 1 backtracks you can't  cover all nodes. With 2 backtracks  we can cover all nodes. .. Therefore  we need two backtracks. 

A-B-E-C-F-D-backtrack-F-I-backtrack-G-H

• edited by
Voting & Accepting an answer helps improve the community
← Previous · Introduction to algo...Next → · algorithm
← Previous in category · data structureNext in category → · algorithm
Position:
Show:

Related questions

0 0 votes
1 1 answer
1.5k
1.5k views
Sanjay Sharma asked Jul 2, 2016
1,548 views
The Depth First and Breadth First Traversal algorithms visit the nodes
The Depth First and Breadth First Traversal algorithms visit the nodes in exactly the same order in which the following types of graphsBinary treeLinear chainComplete gra...
3 3 votes
2 answers 2 answers
2.7k
2.7k views
suchismith roy asked May 27, 2016
2,674 views
Difference between Depth first traversal and Depth first search
DFS is done for a graph.So we need a visited array to keep track of cycles.Do we need visited array for DFT of a tree?What is the basic difference between traversal and s...
1 1 vote
0 0 answers
571
571 views
pradeepchaudhary asked Dec 8, 2018
571 views
Depth First Search: Finding if The graph is connected
Better Explanation??
3 3 votes
0 0 answers
2.0k
2.0k views
Na462 asked Aug 21, 2018
1,988 views
Depth first search
The maximum number of edges possible with UDG of n nodes,when DFS call on any random node in the graph result in stack size of 5. i.e. 5 function calls present in stack s...