What is the difference between a directed and an undirected graph?

A directed graph (digraph) and an undirected graph differ in how they represent relationships between nodes. In a directed graph, edges have a specific direction, meaning the connection from node A to node B is distinct from a connection from B to A. This is often visualized with arrows. In contrast, an undirected graph’s edges lack direction, representing a bidirectional relationship where A connected to B is the same as B connected to A. For example, in a social network, an undirected graph might model mutual friendships, while a directed graph could represent one-way follows or subscriptions.

The data structures and algorithms used for each type reflect this distinction. Directed graphs are typically represented using adjacency lists or matrices where each entry explicitly notes the direction. For instance, an adjacency list for a directed graph might list outgoing edges separately for each node, while an undirected graph’s adjacency list would treat A→B and B→A as a single edge. Algorithms like breadth-first search (BFS) or depth-first search (DFS) work on both types, but their behavior changes. In directed graphs, traversal respects edge direction, which can lead to disconnected paths even if nodes are reachable in one direction. Undirected graphs simplify cycle detection and connectivity analysis because edges inherently allow two-way movement.

Practical applications also highlight their differences. Undirected graphs are ideal for modeling symmetric relationships, such as road networks (where roads are bidirectional) or collaborative networks (co-authors in a paper). Directed graphs suit scenarios requiring asymmetry, like task dependencies (A must finish before B starts) or web page links (Page A links to Page B, but not vice versa). When choosing between the two, developers must consider whether relationships are inherently one-way or mutual. For example, using an undirected graph for a Twitter-like follow system would incorrectly imply mutual follows, while using a directed graph for a mutual friendship model would overcomplicate the implementation. Understanding these distinctions ensures accurate modeling and efficient algorithm selection.