Directed vs Undirected Graphs: Properties and Operations

Key Insights

Directed graphs model asymmetric relationships (following, dependencies, web links) while undirected graphs model symmetric ones (friendships, physical connections, similarity); choosing wrong costs you correctness or unnecessary complexity.
The distinction fundamentally changes connectivity analysis: undirected graphs have simple connected components, but directed graphs require understanding strongly vs. weakly connected components—different algorithms, different semantics.
Edge direction affects every operation from traversal to path finding; a directed graph with n edges requires n entries in an adjacency list, while the equivalent undirected representation needs 2n entries (one per direction).

Introduction to Graph Types

Graphs are everywhere in software: social networks, dependency managers, routing systems, recommendation engines. Yet developers often treat graph type selection as an afterthought, defaulting to whatever their library provides. This is a mistake. The choice between directed and undirected graphs shapes your entire solution.

A directed graph (digraph) consists of vertices connected by edges with direction. Edge (A, B) means “A points to B” but says nothing about B pointing to A. Think Twitter follows, package dependencies, or web page links.

An undirected graph treats edges as bidirectional. Edge {A, B} means A and B are connected, period. Think Facebook friendships, road networks (ignoring one-way streets), or molecular bonds.

The distinction isn’t academic. Model Twitter’s follow graph as undirected, and your “followers” feature breaks. Model a friendship network as directed, and you’re storing redundant edges and complicating queries.

Structural Properties Comparison

The fundamental differences cascade through every aspect of graph behavior.

Edge Representation: In directed graphs, edge (u, v) is distinct from (v, u). In undirected graphs, {u, v} and {v, u} are the same edge. This affects storage: undirected edges in adjacency lists appear twice (once for each endpoint), while directed edges appear once.

Degree: Undirected graphs have a single degree per vertex—the count of incident edges. Directed graphs split this into in-degree (incoming edges) and out-degree (outgoing edges). A Twitter power user might have 10 million in-degree (followers) and 500 out-degree (following).

Symmetry: Undirected graphs have symmetric adjacency matrices. If A[i][j] = 1, then A[j][i] = 1. Directed graphs have no such constraint, which affects algorithm design and matrix-based computations.

Here’s how these differences manifest in code:

from collections import defaultdict
from typing import Set, Iterator

class DirectedGraph:
    def __init__(self):
        self._adj: dict[int, Set[int]] = defaultdict(set)
        self._reverse_adj: dict[int, Set[int]] = defaultdict(set)
    
    def add_edge(self, u: int, v: int) -> None:
        self._adj[u].add(v)
        self._reverse_adj[v].add(u)
    
    def remove_edge(self, u: int, v: int) -> None:
        self._adj[u].discard(v)
        self._reverse_adj[v].discard(u)
    
    def out_neighbors(self, v: int) -> Iterator[int]:
        return iter(self._adj[v])
    
    def in_neighbors(self, v: int) -> Iterator[int]:
        return iter(self._reverse_adj[v])
    
    def out_degree(self, v: int) -> int:
        return len(self._adj[v])
    
    def in_degree(self, v: int) -> int:
        return len(self._reverse_adj[v])


class UndirectedGraph:
    def __init__(self):
        self._adj: dict[int, Set[int]] = defaultdict(set)
    
    def add_edge(self, u: int, v: int) -> None:
        self._adj[u].add(v)
        self._adj[v].add(u)  # Symmetric storage
    
    def remove_edge(self, u: int, v: int) -> None:
        self._adj[u].discard(v)
        self._adj[v].discard(u)
    
    def neighbors(self, v: int) -> Iterator[int]:
        return iter(self._adj[v])
    
    def degree(self, v: int) -> int:
        return len(self._adj[v])

Notice the directed graph maintains a reverse adjacency list. Without it, finding in-neighbors requires O(V + E) traversal. This doubles memory but enables O(1) in-neighbor lookup—a common trade-off.

Traversal Operations

BFS and DFS work on both graph types, but direction fundamentally changes what “reachable” means.

In an undirected graph, if you can reach B from A, you can reach A from B. Traversal from any vertex in a connected component visits the entire component.

In a directed graph, reachability is asymmetric. You might reach B from A but not A from B. This creates the distinction between strongly connected (mutual reachability) and weakly connected (reachability if you ignore direction).

def dfs_reachable(graph, start: int) -> Set[int]:
    """Returns all vertices reachable from start."""
    visited = set()
    stack = [start]
    
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        
        # For directed: only follows outgoing edges
        # For undirected: follows all incident edges
        if isinstance(graph, DirectedGraph):
            neighbors = graph.out_neighbors(v)
        else:
            neighbors = graph.neighbors(v)
        
        for neighbor in neighbors:
            if neighbor not in visited:
                stack.append(neighbor)
    
    return visited


# Demonstration of different behavior
directed = DirectedGraph()
directed.add_edge(0, 1)
directed.add_edge(1, 2)
directed.add_edge(2, 0)  # Cycle back
directed.add_edge(2, 3)  # 3 is reachable from 0, but 0 not from 3

undirected = UndirectedGraph()
undirected.add_edge(0, 1)
undirected.add_edge(1, 2)
undirected.add_edge(2, 0)
undirected.add_edge(2, 3)

print(f"Directed from 0: {dfs_reachable(directed, 0)}")    # {0, 1, 2, 3}
print(f"Directed from 3: {dfs_reachable(directed, 3)}")    # {3}
print(f"Undirected from 0: {dfs_reachable(undirected, 0)}")  # {0, 1, 2, 3}
print(f"Undirected from 3: {dfs_reachable(undirected, 3)}")  # {0, 1, 2, 3}

Same edges, completely different reachability semantics. This is why modeling matters.

Path and Connectivity Analysis

Connectivity analysis diverges sharply between graph types.

Undirected graphs have connected components: maximal sets of vertices where any vertex can reach any other. Finding them is straightforward—run DFS from an unvisited vertex, mark everything reachable, repeat.

Directed graphs have two notions of connectivity:

Weakly connected: Connected if you ignore edge direction
Strongly connected: Every vertex can reach every other vertex following edge directions

Finding strongly connected components (SCCs) requires algorithms like Kosaraju’s or Tarjan’s. Here’s Kosaraju’s algorithm:

def find_strongly_connected_components(graph: DirectedGraph) -> list[Set[int]]:
    """Kosaraju's algorithm for finding SCCs."""
    vertices = set(graph._adj.keys()) | set(graph._reverse_adj.keys())
    
    # First DFS: compute finish order
    visited = set()
    finish_order = []
    
    def dfs_forward(v: int) -> None:
        visited.add(v)
        for neighbor in graph.out_neighbors(v):
            if neighbor not in visited:
                dfs_forward(neighbor)
        finish_order.append(v)
    
    for v in vertices:
        if v not in visited:
            dfs_forward(v)
    
    # Second DFS: process in reverse finish order on reversed graph
    visited.clear()
    sccs = []
    
    def dfs_backward(v: int, component: Set[int]) -> None:
        visited.add(v)
        component.add(v)
        for neighbor in graph.in_neighbors(v):  # Reversed edges
            if neighbor not in visited:
                dfs_backward(neighbor, component)
    
    for v in reversed(finish_order):
        if v not in visited:
            component: Set[int] = set()
            dfs_backward(v, component)
            sccs.append(component)
    
    return sccs


def find_connected_components(graph: UndirectedGraph) -> list[Set[int]]:
    """Simple connected components for undirected graphs."""
    vertices = set(graph._adj.keys())
    visited = set()
    components = []
    
    def dfs(v: int, component: Set[int]) -> None:
        visited.add(v)
        component.add(v)
        for neighbor in graph.neighbors(v):
            if neighbor not in visited:
                dfs(neighbor, component)
    
    for v in vertices:
        if v not in visited:
            component: Set[int] = set()
            dfs(v, component)
            components.append(component)
    
    return components

Cycle detection also differs. In undirected graphs, any back edge (edge to an already-visited vertex that isn’t the parent) indicates a cycle. In directed graphs, you need to track vertices currently in the recursion stack—a back edge to an ancestor indicates a cycle, but an edge to a previously-finished vertex does not.

Common Operations and Their Complexity

Operation	Directed (Adj. List)	Undirected (Adj. List)	Notes
Add edge	O(1)	O(1)	Both amortized with hash sets
Remove edge	O(1)	O(1)	With hash sets
Check adjacency	O(1)	O(1)	With hash sets
Get out-neighbors	O(out-degree)	O(degree)	Direct iteration
Get in-neighbors	O(in-degree)*	O(degree)	*Requires reverse adjacency list
Space complexity	O(V + E) or O(V + 2E)**	O(V + 2E)	**If storing reverse adjacency

def add_edge_directed(graph: DirectedGraph, u: int, v: int) -> None:
    """O(1) amortized - single direction storage."""
    graph._adj[u].add(v)
    graph._reverse_adj[v].add(u)  # Optional, for O(1) in-neighbor lookup

def add_edge_undirected(graph: UndirectedGraph, u: int, v: int) -> None:
    """O(1) amortized - but stores edge twice."""
    graph._adj[u].add(v)
    graph._adj[v].add(u)

def has_edge_directed(graph: DirectedGraph, u: int, v: int) -> bool:
    """O(1) - checks specific direction."""
    return v in graph._adj[u]

def has_edge_undirected(graph: UndirectedGraph, u: int, v: int) -> bool:
    """O(1) - direction doesn't matter, but we check one."""
    return v in graph._adj[u]

Conversion Between Types

Sometimes you need to convert between representations. Converting directed to undirected is lossy—you discard direction information. Converting undirected to directed requires choosing a convention.

def directed_to_undirected(digraph: DirectedGraph) -> UndirectedGraph:
    """
    Convert directed graph to undirected by treating all edges as bidirectional.
    Information loss: edge direction is discarded.
    """
    undirected = UndirectedGraph()
    
    for u in digraph._adj:
        for v in digraph.out_neighbors(u):
            undirected.add_edge(u, v)  # Handles symmetry internally
    
    return undirected


def undirected_to_directed(graph: UndirectedGraph, 
                           bidirectional: bool = True) -> DirectedGraph:
    """
    Convert undirected to directed.
    If bidirectional=True: each undirected edge becomes two directed edges.
    If bidirectional=False: arbitrary direction chosen (smaller to larger vertex).
    """
    directed = DirectedGraph()
    seen_edges: Set[tuple[int, int]] = set()
    
    for u in graph._adj:
        for v in graph.neighbors(u):
            edge = (min(u, v), max(u, v))
            if edge not in seen_edges:
                seen_edges.add(edge)
                if bidirectional:
                    directed.add_edge(u, v)
                    directed.add_edge(v, u)
                else:
                    directed.add_edge(edge[0], edge[1])
    
    return directed

Use cases for conversion:

Directed → Undirected: Analyzing weak connectivity, finding communities in social networks ignoring follow direction
Undirected → Directed (bidirectional): Using directed graph algorithms on undirected data
Undirected → Directed (arbitrary): Creating DAGs for topological processing

Choosing the Right Graph Type

Use this decision framework:

Choose directed graphs when:

Relationships are inherently asymmetric (follows, dependencies, citations)
You need to distinguish between incoming and outgoing connections
Order or flow matters (task scheduling, data pipelines)
You’re modeling state machines or control flow

Choose undirected graphs when:

Relationships are symmetric (friendships, physical connections)
You only care about connectivity, not direction
The domain has no natural directionality (similarity networks, molecular structures)

Property	Directed	Undirected
Edge semantics	Asymmetric	Symmetric
Degree type	In-degree + out-degree	Single degree
Connectivity	Strong/weak components	Connected components
Cycle detection	Recursion stack needed	Parent tracking sufficient
Storage overhead	Lower (single direction)	Higher (both directions)
Typical use cases	Dependencies, web graphs, workflows	Social networks, road maps, similarity

The right choice depends on your domain. When in doubt, ask: “If A relates to B, does B necessarily relate to A in the same way?” If yes, undirected. If no, directed. Get this wrong, and you’ll fight your data structure instead of solving your problem.