Depth First Search (DFS) – Graph Traversal

Table of contents

  • Definition
  • Conceptual Implementation
  • Java Code & Explanation
  • Applications of DFS



Depth First Search (DFS) is an algorithm for traversing Graph Data Structure. The algorithm starts at some arbitrary node in the graph and explores as far as possible along each branch before backtracking.

Stack Data structure is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking the graph.


Conceptual Implementation


Java Code & Explanation


import java.util.*;


class Main{

    public static class Graph{

        int vertices; // Number of vertices

        LinkedList<Integer> adj[]; // Array of linked list to store the Edges of the graph


        // Constructor of the Graph

        Graph(int v){

            vertices = v;

            adj  = new LinkedList[v]; // Initialization of the array with size of vertices

            for(int i=0; i<vertices; i++){

                adj[i] = new LinkedList<>(); // Initialize linked list object on every index of the array




        // Make Edge between u and v vertices

        void addEdge(int u, int v){





        First mark the sourceNode as visited

        Print the Node

        Iterate through all its neighbor until all the node marked as visited


        void DFS(int sourceNode, boolean[] visited){

            visited[sourceNode] = true;

            System.out.print(sourceNode + " ");

            Iterator<Integer> iterator = adj[sourceNode].listIterator();


                int neighbourToSourceNode =;

                DFS(neighbourToSourceNode, visited);





        // Util Method

        void DFSUtil(int sourceNode){

            boolean visited[] = new boolean[vertices]; // Array to store marked visited vertices

            DFS(sourceNode, visited); // Call DFS Method




    public static void main(String[] args) {

        Graph graph = new Graph(7);


        graph.addEdge(0, 1);

        graph.addEdge(0, 2);

        graph.addEdge(1, 3);

        graph.addEdge(1, 4);

        graph.addEdge(1, 5);

        graph.addEdge(2, 6);





    private static void extracted(Graph graph) {








  • Topological Sorting
  • Scheduling Problem
  • Cycle detection in graph
  • Maze Problem
  • Sudoku Puzzle

Leave a Reply