Directed Graphs: Explained with Examples, Notes and FAQs

A directed graph (or digraph) is a graph where every edge has a direction — an arrow from one vertex to another. While an undirected edge {u, v} is a two-way street, a directed edge (u, v) is one-way: it goes from u to v but not back. One-way streets, web links, "follows" on social media and prerequisite chains are all naturally directed.

Direction matters because many real relationships are not symmetric. You may follow a celebrity who does not follow you back; a web page can link to another without a link back. Directed graphs capture this one-way reality.

Key Concepts

• Directed edge (arc): an ordered pair (u, v) — the tail u points to the head v.
• Indegree / outdegree: the number of edges pointing into / out of a vertex.
• Directed path: a path where every edge points in the direction of travel.
• Strongly connected: every vertex reaches every other by directed paths. Weakly connected: connected ignoring arrow directions.
• Directed cycle: a directed path returning to its start, following the arrows all the way round.
• DAG (directed acyclic graph): a digraph with no directed cycles — the shape of prerequisites and task dependencies.

How It Works

Reachability follows the arrows only — you cannot walk an edge backwards. A topological ordering of a DAG lists vertices so every edge points forward: repeatedly remove a vertex with indegree 0 (one must exist in a DAG) and append it to the order. If the process gets stuck with vertices remaining, a directed cycle exists and no topological order is possible.

Worked Example

Course prerequisites: vertices Calc, Algebra, Physics, Programming, AI; edges (prerequisite → course): Algebra → Calc, Calc → Physics, Algebra → Programming, Programming → AI, Calc → AI. Indegrees: Algebra 0, Calc 1, Physics 1, Programming 1, AI 2. Topological order by repeatedly taking indegree-0 vertices: Algebra first; then Calc and Programming reach indegree 0 — take Calc, then Programming; then Physics and AI reach 0 — take Physics, then AI. One valid order: Algebra, Calc, Programming, Physics, AI — every edge points forward in it. The graph is weakly connected but not strongly connected: AI cannot reach Algebra by following arrows.

Common Misconceptions

• A directed edge is not the same as two opposite directed edges. One arrow u → v is strictly weaker than the pair u → v and v → u. Confusing them breaks reachability analysis.
• Indegree and outdegree can differ wildly. A popular website has huge indegree (many links in) and small outdegree. The handshaking lemma adapts: the sum of all indegrees equals the sum of all outdegrees equals the number of edges.
• "Connected" needs a qualifier for digraphs. Always say strongly or weakly connected — an unqualified claim is ambiguous, since a digraph can be one but not the other.

Real-World Applications

• The web: pages are vertices and hyperlinks are directed edges — the basis of search ranking algorithms.
• Social media: "follows" are directed; influence flows along outgoing edges.
• Project scheduling: task dependencies form a DAG; topological order gives a valid work sequence.
• Version control: Git commit histories are DAGs — each commit points to its parents.

A directed graph adds arrows to edges, and arrows change everything: reachability becomes one-way, and cycles must follow the arrows. It is the right model whenever the relationship only goes one way.