Mastering Graph Algorithms: BFS, DFS, Dijkstra, Floyd-Warshall, and Bellman-Ford in Java

Chapter 2: Depth-First Search (DFS) in Java

Depth-First Search (DFS) is another fundamental algorithm used to traverse or search through graphs and trees. Unlike Breadth-First Search (BFS), which explores level by level, DFS dives deeper into a graph, exploring as far down a branch as possible before backtracking. DFS can be implemented using either a stack (iterative approach) or recursion.

DFS is particularly useful for problems where you need to explore a graph fully, such as in scenarios involving pathfinding, cycle detection, topological sorting, and connected components in a graph. The algorithm starts at the root node (or any arbitrary node in the graph), marks it as visited, and then explores each adjacent node before backtracking.

The DFS algorithm works by:

1. Starting at a selected node (often the root in trees).
2. Visiting an unvisited node, marking it as visited.
3. Recursively or iteratively visiting the adjacent nodes (depth-first).
4. Backtracking to the most recent node and continuing the process until all nodes have been visited.

One of the main advantages of DFS is that it can be easily implemented using recursion, simplifying the code. It can also be adapted to find solutions like topological sorting in Directed Acyclic Graphs (DAGs), strongly connected components in directed graphs, and detecting cycles in graphs.

DFS Algorithm in Java

DFS can be implemented using recursion or with an explicit stack. Below is an example of DFS implemented using recursion:

import java.util.*;

class Graph {

    private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

    // Add edge to the graph

    public void addEdge(int v, int w) {

        adjacencyList.putIfAbsent(v, new ArrayList<>());

        adjacencyList.get(v).add(w);

    }

    // DFS Recursive method

    public void DFS(int start) {

        Set<Integer> visited = new HashSet<>();

        DFSUtil(start, visited);

    }

    private void DFSUtil(int node, Set<Integer> visited) {

        // Mark the current node as visited and print it

        visited.add(node);

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

        // Recur for all the vertices adjacent to this node

        if (adjacencyList.containsKey(node)) {

            for (Integer neighbor : adjacencyList.get(node)) {

                if (!visited.contains(neighbor)) {

                    DFSUtil(neighbor, visited);

                }

            }

        }

    }

}

public class Main {

    public static void main(String[] args) {

        Graph graph = new Graph();

        graph.addEdge(1, 2);

        graph.addEdge(1, 3);

        graph.addEdge(2, 4);

        graph.addEdge(3, 5);

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

        graph.DFS(1);  // Output: 1 2 4 3 5

    }

}

Time Complexity of DFS:

• The time complexity of DFS is O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because DFS visits each vertex and edge once.

Space Complexity of DFS:

• The space complexity of DFS is O(V) due to the stack (or recursion call stack) used to keep track of visited nodes.