Depth-First Search - Data Structures and Algorithms (DSA) Guide

Table of Contents 📚

Introduction to Depth-First Search
DFS on Trees
DFS on Graphs
Time and Space Complexity
Conclusion

Introduction to Depth-First Search 🌱

Depth-First Search (DFS) is an algorithm for traversing trees and graphs. The idea is to start from the root (in case of a tree) or any arbitrary node (in case of a graph), mark the node, and move to an adjacent unmarked node and continue this loop until there are no unmarked adjacent nodes. Then backtrack and check for other unmarked nodes and traverse them.

DFS on Trees 🌳

In a tree, DFS can start from the root node and explore as far as possible along each branch before backtracking. Here’s how DFS would work on a simple binary tree:

DFS traversal order: 1, 2, 4, 5, 3

Java Implementation for DFS on Trees 🌳

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
        left = right = null;
    }
}

public class DFSTree {
    Node root;

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

        // Process current node
        System.out.print(node.value + " ");

        // Recursive DFS on left subtree
        DFS(node.left);

        // Recursive DFS on right subtree
        DFS(node.right);
    }

    public static void main(String[] args) {
        DFSTree tree = new DFSTree();
        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);

        System.out.println("DFS Traversal:");
        tree.DFS(tree.root);  // Output will be 1 2 4 5 3
    }
}

DFS on Graphs 🕸

DFS on graphs is similar to DFS on trees. The only catch is to keep track of visited nodes to avoid cycles. Consider the following graph:

1---2
|   |
4---3

DFS traversal (starting from 1): 1, 2, 3, 4

Java Implementation for DFS on Graphs 🕸

import java.util.*;

public class DFSGraph {
    private int V;  // number of vertices
    private LinkedList<Integer> adj[];  // adjacency list

    DFSGraph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        for (Integer neighbour : adj[v]) {
            if (!visited[neighbour])
                DFSUtil(neighbour, visited);
        }
    }

    void DFS(int startVertex) {
        boolean visited[] = new boolean[V];
        DFSUtil(startVertex, visited);
    }

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

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

        System.out.println("DFS traversal starting from vertex 1:");

        g.DFS(1);  // Output will be 1 2 3 0 or 1 0 3 2 depending on implementation
    }
}

Time and Space Complexity 🕒📦

Time Complexity: O(V+E) where V is the number of vertices and E is the number of edges.
Space Complexity: O(V) for storing visited nodes and stack space during recursion.

Conclusion 🌟

DFS is a powerful technique with a lot of applications, from topological sorts to path finding in mazes. Understanding its underlying principles is crucial for mastering more advanced algorithms and techniques.

If you find this guide useful, please share with others, and spread the knowledge!