Check if a Path Exists Between Two Vertices

Given a directed graph and two vertices src and dst, return true if there's a path from src to dst that follows the edges in their direction.

Example

graph LR
    0 --> 1
    0 --> 2
    1 --> 3
    2 --> 3
    3 --> 4

path(0, 4) = true    (0 -> 1 -> 3 -> 4)
path(4, 0) = false   (4 has no outgoing edges)
path(2, 1) = false   (edges only lead away from 1 and 2)

Brute force: explore every path

Search paths with backtracking. Mark a vertex while it's on the current path, to avoid walking in circles, and unmark it when you backtrack. That way, the vertex can be explored again as part of a different path.

import java.util.List;

public class Main {
    static boolean search(List<List<Integer>> adj, int v, int dst, boolean[] onPath) {
        if (v == dst) {
            return true;
        }
        onPath[v] = true;
        for (int w : adj.get(v)) {
            if (!onPath[w] && search(adj, w, dst, onPath)) {
                return true;
            }
        }
        onPath[v] = false; // backtrack: v may be used again on another path
        return false;
    }

    static boolean pathExists(List<List<Integer>> adj, int src, int dst) {
        return search(adj, src, dst, new boolean[adj.size()]);
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(3), List.of(3), List.of(4), List.of());
        System.out.println(pathExists(adj, 0, 4) + " " + pathExists(adj, 4, 0) + " " + pathExists(adj, 2, 1));
    }
}

true false false

Time: exponential in the worst case. Unmarking lets the same vertex be explored once for every path that reaches it, and a graph can have exponentially many paths. Picture a chain of "diamonds" like 0 → {1, 2} → 3, repeated: each diamond doubles the number of paths. Space: O(V), plus the recursion depth of up to V calls.

Optimal: BFS that never revisits a vertex

BFS keeps the vertices to explore in a queue (ArrayDeque used through the Queue interface: add at the back, poll from the front). Whether dst can be reached from a vertex w doesn't depend on how we got to w. So once w has been explored, exploring it again can't find anything new. Mark vertices as visited and never unmark them.

Walkthrough of path(0, 4):

import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

public class Main {
    static boolean pathExists(List<List<Integer>> adj, int src, int dst) {
        boolean[] visited = new boolean[adj.size()];
        visited[src] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(src);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            if (v == dst) {
                return true;
            }
            for (int w : adj.get(v)) {
                if (!visited[w]) {
                    visited[w] = true;
                    queue.add(w);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(3), List.of(3), List.of(4), List.of());
        System.out.println(pathExists(adj, 0, 4) + " " + pathExists(adj, 4, 0) + " " + pathExists(adj, 2, 1));
        System.out.println(pathExists(adj, 3, 3)); // a vertex reaches itself with an empty path
    }
}

true false false
true

Time: O(V + E): each vertex is queued at most once, and each edge is checked once. Space: O(V).

DFS with the same "never unmark" visited array is as fast. What makes this fast is that visited is never reset, not whether you use BFS or DFS. BFS has a small extra benefit: it finds the path with the fewest edges, which the shortest path lesson builds on.

Many queries

If you have to answer many "is there a path?" questions on the same undirected graph, run union-find (see Graph Valid Tree) over the edges once. After that, two vertices are connected exactly when find(a) == find(b), and each query is almost O(1). For directed graphs, reachability is harder: precompute the strongly connected components, or run one BFS per source.

Edge cases

• src == dst: true, with a path of length 0.
• src has no outgoing edges: only dst == src is reachable.
• Cycles: visited prevents infinite loops.