Directed vs Undirected Graphs Explained
Compare directed (digraphs) and undirected graphs. Learn the differences in edge representation, use cases, degree definitions, and how algorithms behave differently on each type.
Detailed Explanation
Directed vs Undirected Graphs
The distinction between directed and undirected graphs is one of the most fundamental concepts in graph theory. It determines how edges are interpreted and profoundly affects which algorithms can be applied.
Undirected Graphs
In an undirected graph, every edge is bidirectional. If there is an edge between A and B, you can travel from A to B and from B to A. Edges are represented as unordered pairs {A, B}.
A --- B (A connects to B, B connects to A)
| /
| /
C
Degree of a node = total number of edges connected to it.
Directed Graphs (Digraphs)
In a directed graph, edges have a direction. An edge from A to B (A → B) does not imply an edge from B to A. Edges are represented as ordered pairs (A, B).
A → B (A connects to B, but not B to A)
↑ ↗
| /
C
In-degree = number of incoming edges. Out-degree = number of outgoing edges.
How Algorithms Differ
| Feature | Undirected | Directed |
|---|---|---|
| Connectivity | Connected / Disconnected | Strongly / Weakly connected |
| Cycle detection | Back edge to non-parent | Back edge in DFS tree |
| Topological sort | Not applicable | Only for DAGs |
| Shortest path | BFS (unweighted) | BFS or Dijkstra |
Choosing the Right Type
Use undirected for mutual relationships: friendships, physical roads (two-way), similarity networks. Use directed for one-way relationships: web links, dependencies, follower graphs, workflow DAGs.
Use Case
Social networks like Facebook model friendships as undirected edges (mutual), while Twitter/X models follows as directed edges (one-way). Dependency graphs in package managers (npm, pip) are directed — package A depends on B, but not vice versa. Road networks may use either type: two-way streets are undirected; one-way streets require directed edges.