What Are Directed Graphs?

Directed graphs, also called digraphs, are mathematical structures consisting of a set of vertices connected by edges that have an assigned direction. Each directed edge, or arc, points from one vertex to another, encoding an asymmetric relationship: an edge from vertex A to vertex B does not imply an edge from B to A. This distinguishes directed graphs from undirected graphs, where edges carry no orientation. Formally, a digraph is an ordered pair G = (V, A), where V is a set of vertices and A is a set of ordered pairs of vertices.

Directed graphs draw their theoretical roots from combinatorics and discrete mathematics, and they appear throughout computer science, electrical engineering, and operations research wherever the direction of a relationship matters. The study of directed graphs is closely tied to graph theory as developed in the work of Leonhard Euler and later formalized for computational purposes in the twentieth century.

Structural Properties

A directed graph is characterized by the indegree and outdegree of each vertex: the indegree counts the number of edges pointing into the vertex, and the outdegree counts those pointing out. A vertex with outdegree zero is called a sink; one with indegree zero is called a source. Reachability is a central concept: vertex B is reachable from vertex A if there exists a directed path, a sequence of consecutive edges, leading from A to B. Two vertices are strongly connected if each is reachable from the other; the strongly connected components of a digraph partition its vertices into maximal subsets with this mutual-reachability property, and they can be computed in linear time using the Kosaraju-Sharir algorithm.

A directed acyclic graph (DAG) is a digraph containing no directed cycle, meaning no sequence of edges leads from a vertex back to itself. DAGs admit a topological ordering: a linear sequence of vertices such that every edge points forward. Topological sort underlies dependency resolution in compilers, build systems, and package managers.

Algorithms and Traversal

Depth-first search and breadth-first search both extend naturally to directed graphs. DFS on a digraph identifies reachable vertices, detects cycles, and computes topological order for DAGs. Breadth-first search computes shortest-path distances in terms of edge count. For weighted digraphs, Dijkstra's algorithm finds shortest paths with non-negative edge weights, while the Bellman-Ford algorithm handles graphs containing negative-weight edges and can detect negative cycles. These algorithms form the foundation for routing protocols, network flow analysis, and scheduling computations.

Representation and Computational Considerations

Digraphs are represented in software either as adjacency lists, which store for each vertex the list of vertices it points to, or as adjacency matrices, which use a binary matrix indicating edge presence. Adjacency lists are preferred for sparse graphs because they use O(V + E) space rather than O(V²). The MIT Mathematics for Computer Science course materials treat directed graphs as a central topic in discrete mathematics, reflecting how foundational the structure is to algorithm design and formal reasoning about computation.

Applications

Directed graphs have applications in a wide range of disciplines, including:

• Compiler design and build systems, where topological sort resolves instruction or dependency ordering
• Database query optimization, representing execution plans and join orderings
• Web link analysis and search engine page ranking, where hyperlinks form a large directed graph
• Deadlock detection in operating systems and concurrent programs
• Circuit design and signal flow modeling in electrical engineering
• Transportation and logistics network modeling, where roads and routes are inherently directional