Introduction

Finding the reachable vertices for every vertex in a directed graph means computing the transitive closure of the graph. For each start vertex u, you want the set of vertices v such that there is a directed path from u to v.

The simplest correct solution is to run a graph traversal from every vertex. Whether that is good enough depends on graph size and whether the graph has structure you can exploit.

Baseline Approach: DFS or BFS from Every Vertex

If the graph is stored as adjacency lists, run DFS or BFS starting from each vertex.

1from collections import deque
2
3
4def reachable_sets(graph):
5    n = len(graph)
6    result = []
7
8    for start in range(n):
9        seen = [False] * n
10        queue = deque([start])
11        seen[start] = True
12
13        while queue:
14            u = queue.popleft()
15            for v in graph[u]:
16                if not seen[v]:
17                    seen[v] = True
18                    queue.append(v)
19
20        result.append([i for i, ok in enumerate(seen) if ok])
21
22    return result
23
24
25graph = [[1, 2], [2], [3], []]
26print(reachable_sets(graph))

This runs in O(V * (V + E)) time with adjacency lists.

When the Baseline Is Good Enough

For moderate graphs, repeated DFS or BFS is often the right answer because it is easy to implement and hard to get wrong. If you only need the result once and the graph is not huge, simplicity wins.

That is especially true in interview problems and one-off analysis scripts.

Strongly Connected Components Can Reduce Work

If the graph has many cycles, first compress strongly connected components into a DAG. Inside one SCC, every vertex reaches every other vertex, so you can solve reachability on the condensed graph and map the result back.

This helps when the original graph contains large mutually reachable regions. Instead of solving the same reachability problem repeatedly inside a cycle, you solve it once per component.

Bitset Optimization for Dense Graphs

When V is not too large but you want faster set operations, represent each reachable set as a bitset. Then combine child reachability with bitwise OR operations.

This is especially effective on DAGs processed in reverse topological order because:

• each node starts with its own bit set
• each outgoing neighbor contributes its reachable set
• unions become machine-word operations instead of repeated Python-level loops

The idea is more advanced, but it can be much faster for dense reachability computation.

Matrix-Based Thinking

Another way to view the problem is repeated transitive closure over the adjacency matrix. Classical algorithms such as Floyd-Warshall can solve reachability too, though they are usually more attractive when you are already working with dense matrices or want a well-known dynamic-programming formulation.

For sparse graphs, repeated DFS or SCC-based approaches are usually more practical.

Choose Based on Graph Shape

A good rule of thumb:

• sparse graph, one-off computation: repeated DFS or BFS
• many cycles: compress SCCs first
• dense graph or bitset-friendly implementation: use bitset-style transitive closure

There is no single best method for every graph.

Common Pitfalls

• Recomputing reachability naively without noticing that SCC compression could remove massive repeated work.
• Choosing adjacency matrices for very sparse graphs and paying unnecessary memory and time costs.
• Forgetting to mark the start vertex as reachable from itself when that is part of the definition you need.
• Mixing up “can reach” with “is directly adjacent to,” which confuses path reachability with one-edge neighbors.
• Overengineering the solution when repeated DFS is already fast enough for the actual input size.

Summary

• Reachability for every vertex is the transitive closure problem on a directed graph.
• The simplest solution is DFS or BFS from each vertex.
• SCC compression helps when the graph contains many cycles.
• Bitset or matrix-style methods become attractive for dense or highly optimized scenarios.
• Pick the algorithm based on graph size, sparsity, and whether the computation is one-off or performance-critical.