Depth First Search (DFS) is a graph traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking. This method is used to explore all the vertices and edges of a graph.

Graph Representation

Graphs can be represented using adjacency lists or adjacency matrices. In DFS, we usually use a stack data structure to keep track of the nodes to be explored.


import java.util.*;

class Graph {
    private LinkedList adjLists[];
    private boolean visited[];

    Graph(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    void DFS(int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        Iterator ite = adjLists[vertex].listIterator();
        while (ite.hasNext()) {
            int adj = ite.next();
            if (!visited[adj])
                DFS(adj);
        }
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Depth First Traversal starting from vertex 2:");

        g.DFS(2);
    }
}

DFS Example 1: Simple Graph

In this example, we demonstrate DFS on a simple directed graph with 4 vertices. The traversal starts from vertex 2 and visits nodes in depth-first order.

DFS Example 2: Undirected Graph

For an undirected graph, the DFS traversal will visit all nodes connected to the starting node, ensuring all paths are explored before backtracking.

Console Output:

2 0 1 3

DFS on Trees

DFS in Tree Structures

DFS is particularly useful in tree structures to explore all nodes. It can be used to implement algorithms like tree traversal (inorder, preorder, postorder).


class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    void printPostorder(Node node) {
        if (node == null)
            return;

        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.data + " ");
    }

    void printInorder(Node node) {
        if (node == null)
            return;

        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }

    void printPreorder(Node node) {
        if (node == null)
            return;

        System.out.print(node.data + " ");
        printPreorder(node.left);
        printPreorder(node.right);
    }

    void printOrder() {
        System.out.println("Preorder traversal:");
        printPreorder(root);

        System.out.println("\nInorder traversal:");
        printInorder(root);

        System.out.println("\nPostorder traversal:");
        printPostorder(root);
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        tree.printOrder();
    }
}

DFS Example 3: Tree Traversal

This example demonstrates DFS for tree traversal in different orders: preorder, inorder, and postorder. Each traversal visits nodes in a specific sequence.

Console Output:

Preorder traversal: 1 2 4 5 3

Inorder traversal: 4 2 5 1 3

Postorder traversal: 4 5 2 3 1

DFS for Cycle Detection

Cycle Detection in Graphs

DFS can be used to detect cycles in graphs. By keeping track of visited nodes, we can determine if a back edge exists, indicating a cycle.


import java.util.*;

class Graph {
    private LinkedList adjLists[];
    private boolean visited[];

    Graph(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    boolean isCyclicUtil(int v, boolean[] visited, boolean[] recStack) {
        if (recStack[v])
            return true;

        if (visited[v])
            return false;

        visited[v] = true;
        recStack[v] = true;

        List children = adjLists[v];

        for (Integer c: children)
            if (isCyclicUtil(c, visited, recStack))
                return true;

        recStack[v] = false;

        return false;
    }

    boolean isCyclic() {
        boolean[] recStack = new boolean[adjLists.length];
        for (int i = 0; i < adjLists.length; i++)
            if (isCyclicUtil(i, visited, recStack))
                return true;

        return false;
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        if (g.isCyclic())
            System.out.println("Graph contains cycle");
        else
            System.out.println("Graph doesn't contain cycle");
    }
}

DFS Example 4: Cycle Detection

This example uses DFS to detect cycles in a directed graph. The algorithm checks for back edges to determine if a cycle is present.

Console Output:

Graph contains cycle

DFS for Path Finding

Path Finding Using DFS

DFS can be used to find paths between two nodes in a graph. By exploring each path fully before backtracking, DFS can identify all possible paths.


import java.util.*;

class Graph {
    private LinkedList adjLists[];
    private boolean visited[];

    Graph(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    void printAllPathsUtil(Integer u, Integer d, boolean[] visited, List localPathList) {
        visited[u] = true;

        if (u.equals(d)) {
            System.out.println(localPathList);
        } else {
            for (Integer i : adjLists[u]) {
                if (!visited[i]) {
                    localPathList.add(i);
                    printAllPathsUtil(i, d, visited, localPathList);
                    localPathList.remove(i);
                }
            }
        }

        visited[u] = false;
    }

    void printAllPaths(Integer s, Integer d) {
        boolean[] visited = new boolean[adjLists.length];
        ArrayList pathList = new ArrayList<>();
        pathList.add(s);
        printAllPathsUtil(s, d, visited, pathList);
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(2, 0);
        g.addEdge(2, 1);
        g.addEdge(1, 3);

        System.out.println("All Paths from 2 to 3:");
        g.printAllPaths(2, 3);
    }
}

DFS Example 5: Path Finding

In this example, DFS is used to find all paths from node 2 to node 3. By exploring each path recursively, DFS lists all possible routes.

Console Output:

[2, 0, 1, 3]
[2, 0, 3]
[2, 1, 3]