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




