Directed vs Undirected Graphs
What you'll learn: The fundamental difference between graphs where edges have a direction versus graphs where connections work both ways.
The Core Distinction
In graph theory, the direction of edges determines how relationships work between vertices.
An undirected graph has edges that work like two-way streets. If vertex A connects to vertex B, you can automatically travel from B back to A. Think of friendships on social media: if Alice is friends with Bob, then Bob is friends with Alice—the relationship goes both ways.
A directed graph (or "digraph") has edges that work like one-way streets. An edge from vertex A to vertex B doesn't guarantee a path back from B to A. Think of following someone on Twitter: you might follow a celebrity, but they don't automatically follow you back. The edge has an arrow pointing in a specific direction.
Real-World Analogies
- Undirected: Hallways in a building (walk either direction), friendships, physical roads between cities
- Directed: Email ("from" → "to"), web page links (one page links to another), prerequisites (Calculus I → Calculus II)
Impact on Representation and Operations
This distinction affects everything about how you work with graphs:
- Storage: Undirected edges can be stored once (edge between A and B), while directed edges must specify source and destination
- Degree: Undirected vertices have one degree; directed vertices have in-degree (incoming edges) and out-degree (outgoing edges)
- Traversal: Following edges respects direction in directed graphs
- Connectivity: Harder to define in directed graphs (requires "strong" vs "weak" connectivity concepts)
Key Takeaway: Directed graphs model one-way relationships with arrows on edges, while undirected graphs model bidirectional connections—this choice fundamentally shapes your entire graph representation and algorithm design.