Directed vs Undirected Graphs
What You'll Learn
You'll understand the fundamental difference between graphs where edges have direction (like one-way streets) and those where connections work both ways (like handshakes).
The Core Distinction
When we connect vertices (nodes) with edges in a graph, the direction of those connections matters tremendously.
Undirected Graphs
In an undirected graph, edges represent bidirectional relationships. If vertex A connects to vertex B, then B automatically connects back to A. Think of it like a friendship on most social networks—if you're friends with someone, they're friends with you too.
Examples in the real world:
- Road networks where all streets are two-way
- Mutual friendships
- Network cables connecting computers (data flows both ways)
Directed Graphs
In a directed graph (also called a digraph), edges have a specific direction, shown with arrows. An edge from A to B does not imply an edge from B to A. Think of following someone on Twitter—you can follow them without them following you back.
Examples in the real world:
- One-way streets in a city
- Web page links (page A links to B, but B might not link back to A)
- Task dependencies (Task A must complete before Task B can start)
Why This Matters
The direction property fundamentally changes:
- How you traverse the graph
- What algorithms you can use
- What real-world problems you can model
- How you represent the graph in memory (you'll need to track direction!)
Key Takeaway: Undirected graphs represent symmetric, bidirectional relationships where connections work both ways, while directed graphs model asymmetric relationships where edges flow in one specific direction—choosing the right type depends entirely on the problem you're modeling.