What is a directed graph?

AlgorithmsJunior~3 min read

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

Traversals (DFS/BFS): reachability, path finding, direction-aware connectivity checks, O(V+E).
Topological sorting (for a DAG): finds a linear order for executing dependencies, O(V+E).
Shortest-path search: Dijkstra (no negative weights), Bellman-Ford (with negative weights), on a DAG in O(V+E).
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.

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.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.