NIELIT 2016 DEC Scientist B (IT) - Section B: 42

Question

In the ________ traversal we process all of a vertex's descendants before we move to an adjacent vertex.

• A. Depth First
• B. Breadth First
• C. Width First
• D. Depth Limited

Answer 1

A. Depth First Search

Since DFS uses stack, it pushes all the descendent nodes of a vertex and processes it before processing any adjacent node.

That is why the name DEPTH FIRST.

Answer 2

The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.