Directed and Undirected Graphs

A directed graph has edges with direction. An undirected graph has edges that can be used both ways.

This distinction changes reachability, traversal, cycle detection, and ordering.

Core Idea

In a directed graph, an edge from A to B does not automatically mean there is an edge from B to A. In an undirected graph, the connection works both ways.

Direction usually comes from the problem meaning. A one-way road, dependency, or web link is directed. A mutual friendship or two-way road is often undirected.

Representation Contract

For a directed edge a -> b, add only b to graph[a].

For an undirected edge between a and b, add both directions: b to graph[a] and a to graph[b]. Traversal code will believe exactly what the representation says, so a missing reverse edge changes the graph.

Python Example

directed = {
    "A": ["B"],
    "B": [],
}
 
undirected = {
    "A": ["B"],
    "B": ["A"],
}

The undirected version stores the connection in both adjacency lists.

How Direction Changes Reachability

In this directed graph:

graph = {
    "A": ["B"],
    "B": [],
}

A can reach B, but B cannot reach A. If the graph were undirected, both directions would be possible.

This affects BFS, DFS, connected components, cycle detection, shortest paths, and topological sort.

Building an Undirected Graph

For an undirected edge between a and b, add both directions:

graph[a].append(b)
graph[b].append(a)

For a directed edge, add only the direction the problem allows.

Algorithm Consequences

Topological sort is a directed-graph idea. Connected components are simpler in undirected graphs. Cycle detection has different details in directed and undirected graphs because a reverse edge to the parent is normal in an undirected traversal.

Common Confusions

Do not add the reverse edge in a directed graph unless the problem says movement is allowed both ways.

Do not forget the reverse edge in an undirected graph when building an adjacency list. Missing one direction changes the graph.

Another common confusion is assuming “relationship” means undirected. Some relationships are one-way, such as “links to”, “depends on”, or “can move to”.

When To Use It

Use directed edges for one-way relationships and prerequisite-like structure. Use undirected edges for symmetric relationships where either endpoint can reach the other through the same edge.

When reading a problem, ask whether moving from A to B automatically allows moving from B to A.

The Main Point

Direction is part of the problem meaning. Adding or omitting the reverse edge changes reachability and can change the correct algorithm.