Depth-First Search (DFS) on an Adjacency List

Recursive DFS to find a path between two vertices using an adjacency list representation.

Context

An Adjacency List represents a graph as:

• One list per vertex
• Each list contains the outgoing edges of that vertex

Compared to an adjacency matrix:

• Space complexity:
  • Matrix → O(V²)
  • List → O(V + E)

Adjacency lists are preferred for sparse graphs

Core idea

DFS explores as deep as possible before backtracking. To find a path from source to target:

• Maintain a visited[] array (prevents infinite recursion in cyclic graphs).
• Maintain a path list (represents the current traversal branch).
• Use recursion to:
  • Mark the current vertex as visited
  • Add it to the current path
  • Recursively explore each neighbour
  • If a recursive call finds the target → propagate true upward
  • If no neighbour leads to target → remove current from path (backtrack)

Implementation

import java.util.*;

public class GraphSearch {
    public static List<Integer> dfsOnAdjacencyList(GraphEdge[][] graph, int source, int target) {
        var n = graph.length;
        var visited = new boolean[n];
        List<Integer> path = new LinkedList<>();
        
        var found = walk(graph, source, target, visited, path);
        
        return found ? path : List.of();
    }
    
    private static boolean walk(GraphEdge[][] graph, int current, int target, boolean[] visited, List<Integer> path) {
        if (visited[current]) return false;
        
        visited[current] = true;
        path.add(current);
        
        if (current == target) return true;
                
        for (var edge : graph[current]) {
            if (walk(graph, edge.to(), target, visited, path)) return true;
        }
        
        path.removeLast();        
        return false;
    }
    
    public record GraphEdge(int to, int weight) {} 
}