Graph – Depth First Traversal

Objective – Given a graph, do the depth first traversal(DFS).

What is depth-first traversal– Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. Source – Wiki



  • Use Stack.
  • First add the Starting Node to the Stack.
  • Pop out an element from Stack and add all of its connected nodes to stack.
  • Repeat the above two steps until the Stack is empty.
  • Below is a walk through of the graph above.

Complete Code:


source = 0 is connected to nodes:  2 1
source = 1 is connected to nodes:  3 2
source = 2 is connected to nodes:  3
source = 3 is connected to nodes:  4
source = 4 is connected to nodes:  5 1 0
Depth First Traversal: 0 1 3 4 5 2

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

  • Febi Kennedy

    will this work if you have a directed graph as

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(3, 4);
    graph.addEdge(2, 3);
    graph.addEdge(4, 0);
    graph.addEdge(4, 1);
    graph.addEdge(5, 4);

    I believe 5 wont be printed !

    • tutorialhorizon

      Thanks a lot for pointing it out. I have corrected the code. Earlier the code was doing DFS only from vertex 0.

%d bloggers like this: