liveBook · Manning

Directed graph

As explained in The Coder Cafe

A directed graph is a graph whose edges have an orientation from one vertex to another.

A directed graph is a collection of vertices and edges whose connections have orientation: each edge goes from one vertex to another. An edge from A to B means that A points to B; the direction does not imply a reciprocal connection. section 1.3

Direction makes directed graphs useful for representing one-way relationships. For example, a social-network edge can represent Alice following Bob, while a dependency edge can represent one task depending on another. Directed graphs may also be cyclic or acyclic, weighted or unweighted, and connected or disconnected. section 1.3 section 1.4.1

Choose a memory representation according to the graph’s density and the operation that matters:

  • An adjacency matrix stores whether an edge from node i to node j exists in a two-dimensional array. Edge lookup takes O(1) time, but storage takes O(v²), which wastes space for sparse graphs. section 1.3
  • An adjacency list maps each vertex to the edges leaving it. It uses O(v + e) space, while searching a vertex’s outgoing edges takes O(d), where d is its degree; dense graphs can make lookup slower. section 1.3

Dependencies and topological ordering

Suppose A depends on B and C, while C depends on D. A topological sort of this directed acyclic graph produces an execution order in which prerequisites come first: D before C, C before B when that dependency exists, and all required tasks before A. The procedure tracks each vertex’s in-degree, queues vertices with zero incoming edges, removes them, and updates the remaining counters. A cycle prevents a complete dependency order. section 1.4.1

How The Coder Cafe covers it

How deep it goes
Defines graph characteristics, compares two memory representations with costs, and applies direction to topological sorting.
Examples
Uses social-network follows, machine networks, travel weights, and job dependencies as concrete graph examples.
What it assumes
Assumes basic familiarity with nodes, edges, arrays, maps, queues, and asymptotic costs while defining graph terminology.
What you can do after
Evaluate and represent directed relationships, then apply topological sorting to dependency-driven execution orders.
How it connects
Connects directed graphs with vertices, edges, adjacency matrices, adjacency lists, cycles, and topological sorting.

Also explained in

Compare how 5 books explain directed graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.