Graph Algorithms: Depth-First Search (DFS) in Java for Competitive Programming

Depth-First Search (DFS) is a fundamental graph traversal algorithm used extensively in competitive programming. It explores a graph by going as far as possible along each branch before backtracking. This document explains DFS in Java, its implementation, and its applications for graph traversal, topological sorting, and finding connected components.

Understanding Depth-First Search (DFS)

DFS works by starting at a chosen node (the root) and exploring each branch as far as possible before backtracking. It uses a stack (implicitly, through recursion) to keep track of the nodes to visit. The key idea is to visit a node, mark it as visited, and then recursively visit its unvisited neighbors.

Key Concepts

• Visited Array: A boolean array to keep track of nodes that have already been visited to prevent cycles and redundant processing.
• Recursion (or Stack): DFS is often implemented using recursion, which implicitly uses the call stack to keep track of the path being explored. Alternatively, an explicit stack data structure can be used.
• Backtracking: When a dead end is reached (a node with no unvisited neighbors), the algorithm backtracks to the previous node and explores other branches.

DFS Implementation in Java

Here's a Java implementation of DFS using recursion:

 import java.util.ArrayList;
import java.util.List;

public class DFS {

    private int V;   // Number of vertices
    private List<List<Integer>> adj; // Adjacency list representation
    private boolean[] visited;      // Visited array

    public DFS(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; ++i)
            adj.add(new ArrayList<&Integer>());
        visited = new boolean[v];
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w) {
        adj.get(v).add(w);
    }

    // DFS traversal starting from vertex v
    public void DFSUtil(int v) { // Mark the current node as visited visited[v] = true;
        System.out.print(v + " "); // Recur for all the vertices adjacent to this vertex for (int neighbor : adj.get(v)) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor);
            }
        }
    }

    // The main function that prints DFS traversal from a given source vertex
    public void DFS(int v) { // Reset visited array for a new DFS run visited = new boolean[V];
        DFSUtil(v);
    }

    public static void main(String[] args) {
        DFS g = new DFS(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("Following is Depth First Traversal " +
                           "(starting from vertex 2)");

        g.DFS(2); // Start DFS from vertex 2
        System.out.println();
    }
} 

Explanation:

• The `DFS` class represents the graph. `V` is the number of vertices, `adj` is the adjacency list, and `visited` is the array to track visited nodes.
• `addEdge(int v, int w)` adds an edge from vertex `v` to vertex `w`.
• `DFSUtil(int v)` is the recursive function that performs the actual DFS traversal starting from vertex `v`.
• `DFS(int v)` is the entry point, which initializes the `visited` array and calls `DFSUtil`.

Applications of DFS in Competitive Programming

1. Graph Traversal

The basic application of DFS is to visit all the nodes in a graph. It's useful for exploring the graph's structure.

2. Topological Sorting

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. DFS can be used to perform topological sorting. The idea is to perform DFS and add the vertices to a stack *after* their neighbors have been visited. The resulting stack, when popped, gives the topological order.

 import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TopologicalSort {

    private int V;   // Number of vertices
    private List<List<Integer>> adj; // Adjacency list representation
    private boolean[] visited;      // Visited array
    private Stack<Integer> stack;  // Stack for topological sort

    public TopologicalSort(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; ++i)
            adj.add(new ArrayList<&Integer>());
        visited = new boolean[v];
        stack = new Stack<>();
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w) {
        adj.get(v).add(w);
    }

    // Recursive function to perform topological sort
    public void topologicalSortUtil(int v) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex for (int neighbor : adj.get(v)) {
            if (!visited[neighbor]) {
                topologicalSortUtil(neighbor);
            }
        } // Push current vertex to stack which stores result stack.push(v);
    }

    // The main function to perform topological sort
    public void topologicalSort() { // Reset visited array visited = new boolean[V]; // Call the recursive helper function to store Topological Sort starting from all vertices one by one for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i);
            }
        } // Print contents of stack System.out.println("Topological Sort: ");
        while (!stack.empty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        TopologicalSort g = new TopologicalSort(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("Following is a Topological sort of the given graph");
        g.topologicalSort();
    }
} 

3. Finding Connected Components

A connected component in an undirected graph is a subgraph in which any two vertices are connected to each other by a path. DFS can be used to find all the connected components in a graph. Perform a DFS from each unvisited node. Each DFS traversal will explore one connected component.

 import java.util.ArrayList;
import java.util.List;

public class ConnectedComponents {

    private int V;   // Number of vertices
    private List<List<Integer>> adj; // Adjacency list representation
    private boolean[] visited;      // Visited array

    public ConnectedComponents(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; ++i)
            adj.add(new ArrayList<&Integer>());
        visited = new boolean[v];
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v); // For undirected graph
    }

    // DFS traversal starting from vertex v
    public void DFSUtil(int v) { // Mark the current node as visited visited[v] = true;
        System.out.print(v + " "); // Recur for all the vertices adjacent to this vertex for (int neighbor : adj.get(v)) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor);
            }
        }
    }

    // Function to find and print connected components
    public void findConnectedComponents() { // Reset visited array visited = new boolean[V];
        int count = 0;

        for (int v = 0; v < V; ++v) {
            if (!visited[v]) {
                System.out.print("Connected Component " + (++count) + ": ");
                DFSUtil(v);
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        ConnectedComponents g = new ConnectedComponents(5);
        g.addEdge(1, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 4);

        System.out.println("Following are connected components");
        g.findConnectedComponents();
    }
} 

Example Problems and Solutions

Problem 1: Counting Islands

Given a 2D grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solution: Use DFS to explore each island. For each '1' encountered, increment the island count and then use DFS to "sink" the entire island (by changing all connected '1's to '0's) to avoid recounting it.

 class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numRows = grid.length;
        int numCols = grid[0].length;
        int numIslands = 0;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    dfs(grid, i, j);
                }
            }
        }

        return numIslands;
    }

    private void dfs(char[][] grid, int row, int col) {
        int numRows = grid.length;
        int numCols = grid[0].length;

        if (row < 0 || row >= numRows || col < 0 || col >= numCols || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0'; // Sink the island

        dfs(grid, row + 1, col); // Down
        dfs(grid, row - 1, col); // Up
        dfs(grid, row, col + 1); // Right
        dfs(grid, row, col - 1); // Left
    }
} 

Problem 2: Cycle Detection in a Directed Graph

Given a directed graph, determine if the graph contains a cycle.

Solution: Use DFS with two states for each node: unvisited, visiting, and visited. If we encounter a node that is currently visiting during the DFS traversal, it means we've found a cycle.

 import java.util.*;

public class CycleDetection {

    private int V; // Number of vertices
    private List<List<Integer>> adj; // Adjacency list representation
    private int[] state; // 0: unvisited, 1: visiting, 2: visited

    public CycleDetection(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; ++i)
            adj.add(new ArrayList<&Integer>());
        state = new int[v];
    }

    public void addEdge(int v, int w) {
        adj.get(v).add(w);
    }

    public boolean isCyclicUtil(int v) {
        state[v] = 1; // Mark current node as visiting

        for (Integer neighbor : adj.get(v)) {
            if (state[neighbor] == 1) {
                return true; // Cycle detected
            }
            if (state[neighbor] == 0 && isCyclicUtil(neighbor)) {
                return true;
            }
        }

        state[v] = 2; // Mark current node as visited
        return false;
    }

    public boolean isCyclic() {
        for (int i = 0; i < V; i++) {
            if (state[i] == 0 && isCyclicUtil(i)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        CycleDetection graph = new CycleDetection(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

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

Conclusion

DFS is a powerful and versatile graph traversal algorithm with numerous applications in competitive programming. Understanding its implementation and variations allows you to solve a wide range of graph-related problems effectively. Remember to consider the nuances of each problem and adapt the basic DFS algorithm accordingly. Practice is key to mastering DFS and applying it efficiently in competitive coding challenges.