GraphsData structureaka digraph

Directed Graph

A set of vertices connected by one-way edges: an edge u→v does not imply v→u.

▶ VisualizePattern: Breadth-First SearchPractice (4)
Progress

Definition

A directed graph G = (V, E) has vertices V and a set of ordered pairs E ⊆ V × V. The edge (u, v) — written u → v — allows travel from u to v only. Each vertex has an in-degree (edges arriving) and an out-degree (edges leaving).

Direction changes almost everything: reachability is not symmetric, "connected" splits into weakly and strongly connected, a cycle must follow arrows, and a digraph without cycles is a DAG (Directed Acyclic Graph) that admits a Topological Sort. Algorithms such as Kahn's Algorithm, Tarjan's SCC Algorithm, and Kosaraju's Algorithm exist only for directed graphs.

Typical representations are the Adjacency List (adj[u] holds the out-neighbors of u), the Adjacency Matrix (M[u][v] = 1 iff u → v, not necessarily symmetric), and the Edge List. Reversing the graph (flip every edge) is a common preprocessing step to answer "who can reach v?" questions.

digraphone-way edgesreachabilitycyclesin-degreeout-degree

Intuition

A mental model before the formal terms.

Think of one-way streets. You may drive from A to B, but getting back may require a long detour — or be impossible. A neighborhood where every corner can reach every other corner by legal driving is a strongly connected component; the map of neighborhoods with the one-way roads between them never loops (it is a DAG).

Dependencies are the other mental model: "task B needs task A first" is the edge A → B. A cycle means an impossible schedule; no cycle means a valid ordering exists.

How it works

  1. Store vertices 0…V-1 and out-neighbor lists adj[u]. Adding u → v appends v to adj[u] only (unlike an undirected graph, which appends both ways).
  2. Track in-degrees in an array indeg[v] when needed for Kahn's Algorithm or source detection (in-degree 0 = source, out-degree 0 = sink).
  3. Traverse with Breadth-First Search (BFS) or Depth-First Search (DFS) following out-edges. A vertex v is reachable from u iff DFS from u visits v.
  4. Detect cycles with DFS three-colour marking: white (unvisited), grey (on the current recursion stack), black (finished). Meeting a grey vertex means a back edge → cycle.
  5. Build the reverse graph radj[v] containing u for every u → v to answer "which vertices can reach v?" or to run Kosaraju's Algorithm.
  6. Condense strongly connected components into single nodes; the result is always a DAG (Directed Acyclic Graph).

Why it works

DFS on a directed graph classifies every edge as tree, back, forward, or cross. A back edge (to a grey ancestor) exists iff the graph has a cycle, because a cycle's "last discovered" vertex must have an edge back to an ancestor still on the stack.

Strong connectivity is an equivalence relation (reflexive, symmetric, transitive), so the vertices partition into components. Any cycle between components would merge them, so the condensation is acyclic.

Operations

OperationDescriptionCost
addEdge(u, v)Append v to adj[u]; increment indeg[v].O(1)
removeEdge(u, v)Delete v from adj[u].O(deg⁺(u))
outNeighbors(u)Iterate adj[u].O(deg⁺(u))
inNeighbors(v)Requires the reverse graph, or a scan of all edges.O(deg⁻(v)) with reverse list, O(V + E) without
hasEdge(u, v)Scan adj[u] (or O(1) with a matrix / hash set).O(deg⁺(u))
reverse()Build radj with all edges flipped.O(V + E)
reachable(u, v)DFS/BFS from u.O(V + E)

Recognition

How to tell a problem wants this.

  • Words like "prerequisite", "depends on", "follows", "one-way", "links to", "flows to", "before/after".
  • The input is a list of pairs [a, b] meaning "a must come before b" or "a points to b".
  • Questions about ordering, deadlock, reachability from a source, or "can every page be reached from the home page".
  • Web pages and hyperlinks, function call graphs, state machines, import graphs.
“minimum steps” → Breadth-First Search“connected groups” → Depth-First Search“prerequisites” → Topological Sort

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Depth-First Search (DFS) visualization.

ABCDEFGH
Stack (top → bottom)
A
Discovery order
empty
1/18Start DFS from A. The explicit stack replaces the recursion: the node on top is explored next, so we dive deep before going wide.
Current nodeOn the stackVisited (label = discovery order)DFS tree edge
PseudocodeLearn Depth-First Search (DFS) →
1stack = [source]; visited = {}; order = []
2while stack not empty:
3  u = stack.pop()
4  if u in visited: continue
5  visited.add(u); order.append(u)
6  for v in reversed(neighbors(u)):
7    if v not in visited: stack.push(v)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1adj = [[] for _ in range(V)]; indeg = [0] * V
2add_edge(u, v): adj[u].append(v); indeg[v] += 1
3has_cycle(): color = WHITE * V
4  dfs(u): color[u] = GREY
5    for v in adj[u]: if color[v] == GREY: return True; if WHITE and dfs(v): return True
6    color[u] = BLACK; return False
7reverse(): for u: for v in adj[u]: radj[v].append(u)

Implementation

1class DirectedGraph:
2    """A digraph: edges have direction, so u -> v does not imply v -> u.
3    Out-degree and in-degree are different numbers, and reversal is
4    meaningful."""
5 
61 · State: out[u] holds successors; in-degrees are derived, not stored
7    def __init__(self, n: int) -> None:
8        self.out: list[list[int]] = [[] for _ in range(n)]
9 
10    def add_edge(self, u: int, v: int) -> None:
11        self.out[u].append(v)
12 
13    def __len__(self) -> int:
14        return len(self.out)
15 
16    def successors(self, u: int) -> list[int]:
17        return self.out[u]
18 
19    def out_degree(self, u: int) -> int:
20        return len(self.out[u])
21 
222 · In-degree needs a full pass: nothing points backwards by default
23    def in_degrees(self) -> list[int]:
24        deg = [0] * len(self.out)
25        for row in self.out:
26            for v in row:
27                deg[v] += 1
28        return deg
29 
303 · The reverse graph makes predecessors as cheap as successors
31    def reversed(self) -> "DirectedGraph":
32        r = DirectedGraph(len(self.out))
33        for u, row in enumerate(self.out):
34            for v in row:
35                r.out[v].append(u)
36        return r
37 
384 · Reachability follows edges forward only — asymmetric by nature
39    def reachable_from(self, start: int) -> list[bool]:
40        seen = [False] * len(self.out)
41        seen[start] = True
42        stack = [start]
43        while stack:
44            u = stack.pop()
45            for v in self.out[u]:
46                if not seen[v]:
47                    seen[v] = True
48                    stack.append(v)
49        return seen
50 
515 · A cycle exists iff a DFS finds a back edge into the active path
52    def has_cycle(self) -> bool:
53        state = [0] * len(self.out)  # 0 = new, 1 = on the path, 2 = done
54        for s in range(len(self.out)):
55            if state[s] != 0:
56                continue
57            stack = [[s, 0]]  # [vertex, next neighbour index]
58            state[s] = 1
59            while stack:
60                frame = stack[-1]
61                u, i = frame[0], frame[1]
62                if i < len(self.out[u]):
63                    frame[1] += 1
64                    v = self.out[u][i]
65                    if state[v] == 1:
66                        return True  # back edge
67                    if state[v] == 0:
68                        state[v] = 1
69                        stack.append([v, 0])
70                else:
71                    state[u] = 2
72                    stack.pop()
73        return False
Walkthrough
  1. [[] for _ in range(n)] creates distinct successor lists; [[]] * n would alias them.
  2. in_degrees() is the derived quantity — the pass that Kahns topological sort begins with.
  3. reachable_from marks seen[v] = True before appending, which bounds the stack at O(V).
  4. has_cycle stores frames as two-element *lists* rather than tuples, because frame[1] += 1 must mutate the stacked entry — a tuple would be immutable.
  5. while stack: uses list truthiness, the Pythonic empty test.
Complexity (this implementation)
time O(V + E) for in_degrees, reversed, reachable_from and has_cycle · space O(V) for the visited/state lists, O(V + E) for the reversed graph

The iterative form avoids RecursionError, which CPython raises at about 1000 frames — reachable on a graph of only a few thousand vertices in a path.

Language notes
  • CPython caps recursion at sys.getrecursionlimit() (1000 by default); raising it risks a genuine C-stack segfault, so an explicit stack is the safe answer.
  • Mutable list frames are needed for the in-place cursor increment; a tuple frame would require popping and re-pushing a replacement.
  • networkx.is_directed_acyclic_graph(G) and networkx.reverse(G) cover both of these directly for real work.
  • graphlib.TopologicalSorter in the standard library raises CycleError, which makes it an off-the-shelf cycle detector for DAG-shaped input.
Common mistakes in this language
  • Writing the DFS recursively and hitting RecursionError on a long path.
  • Using a tuple for the DFS frame and then trying frame[1] += 1, which raises TypeError.
  • Reporting a cycle whenever a visited vertex is seen, which flags every DAG containing two paths to the same vertex.
Language differences that matter here
  • Mutating a DFS frame in place needs different mechanics per language: a C++ structured binding to a reference, a JavaScript/TypeScript object (references by nature), and a Python *list* rather than a tuple.
  • Recursion depth is the practical reason all four use an explicit stack, but the limits differ sharply — CPython raises RecursionError near 1000 frames, JavaScript engines throw near 10000, and C++ simply overflows the stack with no diagnostic.
  • Library escape hatches exist only in Python (graphlib.TopologicalSorter, networkx) and, for some algorithms, C++ (Boost.Graph); JS/TS have neither in the standard library.
  • Dense flag arrays: C++ std::vector<bool> bit-packs automatically, JS/TS can opt into Int8Array, and Python list[bool] stores pointers to the two singleton bool objects — cheap in time, not in memory.

Complexity

OperationAverageWorstNote
AccessO(1)O(1)Vertex by id.
SearchO(deg(u))O(V)Edge (u, v) lookup by scanning u's list.
InsertO(1)O(1)Append an edge.
DeleteO(deg(u))O(V)Remove an edge from u's list.
UpdateO(deg(u))O(V)Find the edge, then change its weight.
ReverseO(V + E)O(V + E)
Cycle checkO(V + E)O(V + E)
ReachabilityO(V + E)O(V + E)
SpaceO(V + E)Adjacency-list representation; a matrix costs O(V²).

Advantages & disadvantages

Advantages
  • Models asymmetric relationships exactly: dependencies, links, flows, transitions.
  • Enables ordering algorithms (topological sort) and dependency analysis.
  • Storage is half that of the equivalent undirected adjacency list because each edge is stored once.
Disadvantages
  • Reachability is one-way, so "connected" is ambiguous and many problems require SCC decomposition first.
  • In-neighbors are not directly available from an out-adjacency list — a second, reversed structure is needed.
  • Cycles are easy to introduce accidentally in dependency data and must be checked explicitly.

Use cases

  • Build systems and package managers: Topological Sort of the dependency graph.
  • Course prerequisites (Course Schedule I/II).
  • Web graph / PageRank, citation networks, social "follows".
  • Compilers: control-flow graphs, call graphs, SSA dominator trees.
  • State machines and game boards where moves are irreversible.
Use it when
  • The relationship is inherently one-way: prerequisites, links, flows, transitions.
  • You need an ordering (topological sort) or dependency/deadlock analysis.
  • Reachability questions are asymmetric ("can A reach B" differs from "can B reach A").
Avoid it when

Alternatives

Undirected GraphDAG (Directed Acyclic Graph)Adjacency MatrixEdge List

Common mistakes

  • Adding the edge in both directions out of habit, silently turning the digraph undirected.
  • Using the undirected cycle check (visited + parent) on a digraph — it reports false cycles on cross edges; use three colours.
  • Running Union-Find (Disjoint Set Union) on a directed graph to test connectivity — DSU ignores direction.
  • Forgetting that in-degree information must be maintained separately from out-adjacency.
  • Assuming DFS from one source visits every vertex; a digraph may need multiple starts.

Interview patterns

  • Course Schedule: detect a cycle, or produce an order with Kahn's Algorithm.
  • Find the "celebrity" / a vertex with in-degree n-1 and out-degree 0.
  • Reconstruct Itinerary: Eulerian path in a directed multigraph (Hierholzer).
  • Alien Dictionary: build a digraph of character orderings, then topologically sort.
  • Count SCCs, or find the minimum edges to make the graph strongly connected.
Interview questions on this
Mock interviews

Interview problems

Clone GraphmediumReconstruct ItineraryhardCourse SchedulemediumAlien Dictionaryhard