Directed vs Undirected Graph

Graphs can be either directed or undirected, and the choice has big implications for how you model problems and which algorithms you use.

Undirected Graphs

In an undirected graph:

  • Each edge (u, v) represents a two‑way relationship.
  • If u is connected to v, then v is connected to u.

Examples:

  • Friendship networks (if friendship is mutual).
  • Undirected road networks (bidirectional roads).
  • Physical connectivity (wires, pipes).

Properties:

  • Degree of a vertex is simply the number of neighbors.
  • Paths do not care about direction; you can traverse edges both ways.

Directed Graphs (Digraphs)

In a directed graph:

  • Each edge (u, v) has a direction: from u to v.
  • Relationship is not necessarily symmetric.

Examples:

  • Follow relationships on social media (A follows B does not imply B follows A).
  • One‑way roads or one‑way links.
  • Dependencies (task A depends on task B).

Additional notions:

  • In‑degree of a vertex:
    • Number of incoming edges.
  • Out‑degree of a vertex:
    • Number of outgoing edges.

These are important for algorithms like topological sort and PageRank.

Algorithmic Differences

Undirected graphs:

  • Connectivity is simpler:
    • If you can go from u to v, you can also go from v to u.
  • Many problems reduce to counting connected components, finding bridges, or MSTs.

Directed graphs:

  • You must respect edge directions:
    • Reachability is asymmetric (u can reach v but v might not reach u).
  • New concepts:
    • Strongly connected components (SCCs).
    • Topological order (only defined for DAGs).

Some algorithms differ or need adaptation:

  • BFS/DFS must follow edge direction in digraphs.
  • Shortest paths, cycle detection, and connectivity checks have directed variants.

Modeling Choice

When designing a solution:

  • Use an undirected graph if the relationship is naturally symmetric.
  • Use a directed graph if:
    • There is a clear “from” and “to” semantics.
    • Dependencies or flows have a direction.

Choosing the right model makes the algorithm much easier to design and reason about.