Suggest an edit

Improve this article

Refine the answer for “What is a directed graph?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A directed graph (digraph) is a structure made of a set of vertices and directed edges (arcs), where each edge has a direction: from one vertex to another, meaning the order of vertices matters.

## Detailed answer

### Definition and intuition

A directed graph G = (V, E) consists of:

- V, the set of vertices (nodes);
- E, the set of directed edges (arcs), each edge an ordered pair (u, v), meaning a connection from u to v.

The key feature: the presence of direction. Edge (u, v) is not equivalent to (v, u). This lets you model dependency, order, and flow: where a connection or data "flows" from and to.

### Key concepts

- Vertex: the basic element of a graph.
- Arc (directed edge): a connection with a direction from one vertex to another.
- Vertex degrees: out-degree(v), the number of outgoing arcs; in-degree(v), the number of incoming arcs.
- Path and reachability: a directed path from u to v exists if you can follow arcs in their direction from u to v.
- Cycle: a path of nonzero length that starts and ends at the same vertex, following the direction of the arcs.
- Directed acyclic graph (DAG): a directed graph with no cycles; important for scheduling and dependencies.
- Strongly connected component (SCC): a maximal subgraph in which every vertex is reachable from every other vertex following the direction of the arcs.
- Weighted directed graph: arcs are assigned weights/costs (for example, time, distance, priority).

### Where it is used in development

- A dependency graph for modules/packages, build order (topological sort in CI/CD).
- A graph of routes, navigation, and redirects.
- Workflows/pipelines (tasks that require prior steps).
- Microservices and interactions: calls A → B, event streams.
- State graphs (finite state machines) with transitions.

### Simple example

```
Vertices: A, B, C, D
Arcs: A→B, A→C, B→D, C→D

Diagram:
A → B → D
  ↘ C ↗
```

### In-memory representations

In practice, the adjacency list (economical) or the adjacency matrix (convenient for dense graphs) is most often used.

| Representation | Characteristics |
|---|---|
| Adjacency list | Memory ~ O(V+E), fast neighbor traversal, edge check in O(min(deg, ...)) |
| Adjacency matrix | Memory ~ O(V^2), instant edge check in O(1), convenient for dense graphs |

#### Adjacency list (JS example)

```
// The graph from the example: A→B, A→C, B→D, C→D
const adj = {
  A: ["B", "C"],
  B: ["D"],
  C: ["D"],
  D: []
};

// In-degree and out-degree
const outDegree = Object.fromEntries(Object.keys(adj).map(v => [v, adj[v].length]));
const inDegree = Object.fromEntries(Object.keys(adj).map(v => [v, 0]));
for (const u of Object.keys(adj)) for (const v of adj[u]) inDegree[v]++;

console.log({ inDegree, outDegree });
```

#### Adjacency matrix (for the same vertices A,B,C,D)

```
const V = ["A","B","C","D"];
//    A B C D
// A: 0 1 1 0
// B: 0 0 0 1
// C: 0 0 0 1
// D: 0 0 0 0
const matrix = [
  [0,1,1,0],
  [0,0,0,1],
  [0,0,0,1],
  [0,0,0,0]
];

function hasEdge(u, v) {
  const i = V.indexOf(u), j = V.indexOf(v);
  return matrix[i][j] === 1;
}

console.log(hasEdge("A", "C")); // true
```

### Basic algorithms for directed graphs

1. Traversals (DFS/BFS): reachability, path finding, direction-aware connectivity checks, O(V+E).
2. Topological sorting (for a DAG): finds a linear order for executing dependencies, O(V+E).
3. Shortest-path search: Dijkstra (no negative weights), Bellman-Ford (with negative weights), on a DAG in O(V+E).
4. Strongly connected components: Kosaraju/Tarjan, group vertices that are mutually reachable in both directions.

#### Implementation of topological sorting (Kahn) + cycle detection

```
function topoSort(adj) {
  // Count in-degree
  const inDeg = Object.fromEntries(Object.keys(adj).map(v => [v, 0]));
  for (const u in adj) for (const v of adj[u]) inDeg[v] = (inDeg[v] ?? 0) + 1;

// Queue of vertices with no incoming edges
  const q = [];
  for (const v in inDeg) if (inDeg[v] === 0) q.push(v);

const order = [];
  while (q.length) {
    const u = q.shift();
    order.push(u);
    for (const v of adj[u]) {
      inDeg[v]--;
      if (inDeg[v] === 0) q.push(v);
    }
  }

// If the order has fewer vertices than the graph, there is a cycle
  const hasCycle = order.length !== Object.keys(adj).length;
  return { order: hasCycle ? null : order, hasCycle };
}

const adj1 = { A:["B","C"], B:["D"], C:["D"], D:[] };
console.log(topoSort(adj1)); // { order: [ 'A', 'B', 'C', 'D' ] (or 'A','C','B','D'), hasCycle: false }

const adj2 = { A:["B"], B:["C"], C:["A"] }; // cycle A→B→C→A
console.log(topoSort(adj2)); // { order: null, hasCycle: true }
```

#### DFS with cycle detection in a directed graph

```
function hasDirectedCycle(adj) {
  const Color = { WHITE:0, GRAY:1, BLACK:2 };
  const color = Object.fromEntries(Object.keys(adj).map(v => [v, Color.WHITE]));
  let cycle = false;

function dfs(u) {
    color[u] = Color.GRAY;
    for (const v of adj[u]) {
      if (color[v] === Color.GRAY) cycle = true;          // back edge: cycle
      else if (color[v] === Color.WHITE) dfs(v);
    }
    color[u] = Color.BLACK;
  }

for (const v in adj) if (color[v] === Color.WHITE) dfs(v);
  return cycle;
}

console.log(hasDirectedCycle({ A:["B"], B:["C"], C:["A"] })); // true
console.log(hasDirectedCycle({ A:["B","C"], B:["D"], C:["D"], D:[] })); // false
```

### Complexity

- Memory: adjacency list, O(V+E); matrix, O(V^2).
- DFS/BFS/topological sort: O(V+E).
- Finding SCCs (Tarjan/Kosaraju): O(V+E).

### Frequent mistakes and nuances

- Confusing directed and undirected edges: in a digraph, direction is critical.
- Ignoring cycles in a dependency graph: topological sorting is impossible when cycles are present.
- Miscounting degrees: in-degree and out-degree are different values.
- Choosing an inefficient representation: an adjacency matrix for a sparse graph wastes memory.

### Summary

A directed graph is a fundamental structure for modeling directed dependencies and processes. Knowing the representations (list/matrix), the properties (in/out-degree, cycles, SCC), and the basic algorithms (DFS/BFS, topological sorting, shortest paths) is critical for designing and optimizing real systems.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts957 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.