Directed vs Undirected Graph: Key Differences and When to Use Each

A directed graph has edges with a direction, showing a one-way relationship from one node to another. An undirected graph has edges without direction, representing a two-way or mutual connection between nodes.

Quick Comparison

This table summarizes the main differences between directed and undirected graphs.

Aspect	Directed Graph	Undirected Graph
Edge Direction	Edges have a direction (from one node to another)	Edges have no direction (connection is mutual)
Representation	Arrows show direction between nodes	Lines connect nodes without arrows
Relationship Type	One-way or asymmetric relationships	Two-way or symmetric relationships
Common Use Cases	Modeling workflows, web links, social media followers	Modeling friendships, networks, undirected connections
Edge Count	Maximum edges = n*(n-1) for n nodes	Maximum edges = n*(n-1)/2 for n nodes
Traversal Complexity	Requires direction-aware traversal	Traversal is simpler without direction

Key Differences

A directed graph (or digraph) consists of nodes connected by edges that have a specific direction. This means each edge points from one node to another, indicating a one-way relationship. For example, in a social media network, a directed edge can represent "user A follows user B" but not necessarily the reverse.

In contrast, an undirected graph has edges without direction. The connection between two nodes is mutual, meaning if node A is connected to node B, then node B is also connected to node A. This is common in scenarios like modeling friendships where the relationship is naturally two-way.

These structural differences affect how algorithms work on these graphs. Directed graphs require algorithms that respect edge direction, such as finding paths that follow arrows. Undirected graphs allow simpler traversal since edges can be followed in both directions. Also, the maximum number of edges differs because directed graphs can have twice as many edges as undirected graphs for the same number of nodes.

Code Comparison

Here is a simple Python example showing how to represent a directed graph using an adjacency list and print its edges.

python

directed_graph = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['A'],
    'D': []
}

for node, edges in directed_graph.items():
    for edge in edges:
        print(f"{node} -> {edge}")

Output

A -> B
A -> C
B -> C
C -> A

Undirected Graph Equivalent

Here is the equivalent undirected graph representation and printing of edges. Each connection is shown once without direction.

python

undirected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B'],
    'D': []
}

seen = set()
for node, edges in undirected_graph.items():
    for edge in edges:
        if (edge, node) not in seen:
            print(f"{node} -- {edge}")
            seen.add((node, edge))

Output

A -- B
A -- C
B -- C

When to Use Which

Choose a directed graph when your data or problem involves one-way relationships or flows, such as web page links, task dependencies, or social media followers. Directed graphs help model direction-sensitive processes clearly.

Choose an undirected graph when relationships are naturally mutual or symmetric, like friendships, network connections, or collaboration links. Undirected graphs simplify analysis when direction does not matter.

In summary, use directed graphs to capture direction and flow, and undirected graphs to represent mutual connections.

Key Takeaways

Directed graphs have edges with direction showing one-way relationships.

Undirected graphs have edges without direction representing mutual connections.

Directed graphs are used for workflows and asymmetric relations.

Undirected graphs are best for symmetric relationships like friendships.

Graph algorithms differ based on edge direction and graph type.