Graphs: Adjacency List, Matrix, and Core Algorithms

Graphs model pairwise relationships between objects—a vertex (or node) represents an entity, and an edge represents a connection. Social networks, road maps, and dependency systems all decompose naturally into graphs. Understanding graph representations and traversal algorithms matters for pathfinding, network analysis, and scheduling problems.

Introduction

Graphs model pairwise relationships between entities—a vertex represents an object, and an edge represents a connection between two objects. This abstraction fits natural problems: social networks (people as vertices, friendships as edges), road systems (locations as vertices, roads as edges), dependency systems (tasks as vertices, prerequisites as edges). Understanding graph representations and traversal algorithms is essential for solving pathfinding, network analysis, and scheduling problems.

The two primary graph representations—adjacency list and adjacency matrix—make opposite trade-offs. Adjacency lists store each vertex’s neighbors in a list, using O(V + E) space and enabling O(degree) neighbor iteration. Adjacency matrices store a V×V grid where each cell indicates edge presence, using O(V²) space but enabling O(1) edge existence checks. Choosing the right representation depends on graph density, required operations, and size constraints.

In this guide, you’ll implement both representations in Python, master BFS and DFS traversals with their O(V + E) complexity, and understand when to use each traversal pattern. BFS finds shortest paths in unweighted graphs and explores level-by-level; DFS explores deeply before backtracking and enables cycle detection and topological sorting.

Graph Representations

from collections import defaultdict, deque

# Adjacency List: Dictionary of lists
# Best for: Sparse graphs, iterating neighbors
class GraphList:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, weight=None):
        if weight is not None:
            self.graph[u].append((v, weight))
        else:
            self.graph[u].append(v)
        if not self.directed:
            self.graph[v].append(u if weight is None else (u, weight))

    def neighbors(self, u):
        return self.graph[u]

    def vertices(self):
        return list(self.graph.keys())


# Adjacency Matrix: 2D array
# Best for: Dense graphs, O(1) edge lookup, small graphs
class GraphMatrix:
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.matrix = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            self.matrix[i][i] = 0  # Self-loops

    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        if not self.directed:
            self.matrix[v][u] = weight

    def has_edge(self, u, v):
        return self.matrix[u][v] != float('inf')

    def neighbors(self, u):
        return [i for i in range(self.n) if self.matrix[u][i] != float('inf')]


# Edge List: List of tuples
# Best for: Kruskal's MST, sorting edges by weight
class GraphEdges:
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.edges = []

    def add_edge(self, u, v, weight=1):
        self.edges.append((weight, u, v))
        if not self.directed:
            self.edges.append((weight, v, u))

    def get_edges(self, sorted_by_weight=False):
        if sorted_by_weight:
            return sorted(self.edges)
        return self.edges

BFS (Breadth-First Search)

def bfs(graph, start):
    """
    BFS traversal - explores level by level.
    O(V + E) time, O(V) space.

    Returns:
        visited order, distance from start, parent for path reconstruction
    """
    visited = set([start])
    queue = deque([start])
    parent = {start: None}
    distance = {start: 0}
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)

        for neighbor in graph.neighbors(vertex):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = vertex
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)

    return order, distance, parent


def bfs_shortest_path(graph, start, end):
    """BFS guarantees shortest path in unweighted graph."""
    if start == end:
        return [start]

    _, distance, parent = bfs(graph, start)

    if end not in parent:
        return None  # Not reachable

    # Reconstruct path
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parent[current]

    return path[::-1]


def is_bipartite(graph):
    """Check if graph is bipartite using BFS coloring."""
    color = {}
    for start in graph.vertices():
        if start in color:
            continue

        queue = deque([start])
        color[start] = 0

        while queue:
            u = queue.popleft()
            for v in graph.neighbors(u):
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False

    return True

DFS (Depth-First Search)

def dfs_recursive(graph, start, visited=None):
    """Recursive DFS - O(V + E) time, O(V) space for visited + call stack."""
    if visited is None:
        visited = set()

    visited.add(start)
    print(start)  # Process node

    for neighbor in graph.neighbors(start):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited


def dfs_iterative(graph, start):
    """Iterative DFS using explicit stack - avoids recursion depth limit."""
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()

        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)

            # Add neighbors in reverse order to maintain left-to-right processing
            neighbors = graph.neighbors(vertex)
            stack.extend(reversed(neighbors))

    return order


# DFS with entry/exit times for cycle detection and topological sort
def dfs_with_times(graph):
    """
    DFS that records discovery and finish times.
    Useful for cycle detection, topological sort, and articulation points.
    """
    visited = set()
    discovered = {}
    finished = {}
    time = [0]
    parent = {}

    def dfs(u):
        visited.add(u)
        discovered[u] = time[0]
        time[0] += 1

        for v in graph.neighbors(u):
            if v not in visited:
                parent[v] = u
                dfs(v)

        finished[u] = time[0]
        time[0] += 1

    for vertex in graph.vertices():
        if vertex not in visited:
            parent[vertex] = None
            dfs(vertex)

    return discovered, finished, parent


def has_cycle(graph):
    """Detect cycle using DFS (works for directed and undirected)."""
    visited = set()
    rec_stack = set()  # For directed cycle detection

    def dfs(u):
        visited.add(u)
        rec_stack.add(u)

        for v in graph.neighbors(u):
            if v not in visited:
                if dfs(v):
                    return True
            elif v in rec_stack:  # Back edge = cycle
                return True

        rec_stack.remove(u)
        return False

    for vertex in graph.vertices():
        if vertex not in visited:
            if dfs(vertex):
                return True

    return False

When to Use List vs Matrix

Aspect	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add edge	O(1)	O(1)
Check edge	O(degree)	O(1)
Iterate neighbors	O(degree)	O(V)
Dense graphs	Wasteful	Efficient
Sparse graphs	Efficient	Wasteful

BFS vs DFS Exploration Order

graph TD
    subgraph Graph["Sample Graph: A → B, A → C, B → D, B → E, C → F"]
        A["A"] --> B["B"]
        A --> C["C"]
        B --> D["D"]
        B --> E["E"]
        C --> F["F"]
    end

    subgraph BFS_Order["BFS Order (Queue-based)"]
        B1["Level 0: A"]
        B2["Level 1: B, C"]
        B3["Level 2: D, E, F"]
    end

    subgraph DFS_Order["DFS Order (Stack-based)"]
        D1["Path 1: A → B → D"]
        D2["Path 2: A → B → E"]
        D3["Path 3: A → C → F"]
    end

BFS visits nodes level by level: A, then B and C, then D, E, F. BFS finds shortest path in unweighted graphs. DFS explores as deep as possible before backtracking: A, B, D, backtrack to B, E, backtrack to A, C, F.

Graph Traversal Applications

Problem	Algorithm	Use Case
Shortest path (unweighted)	BFS	Social network degrees, maze
Connected components	BFS/DFS	Network analysis, island counting
Cycle detection	DFS	Dependency validation, deadlock detection
Topological sort	DFS	Build systems, course scheduling
Path existence	BFS/DFS	Reachability, firewall rules

Production Failure Scenarios and Mitigations

Graph implementations tend to break in specific, predictable ways once you put them under real production load. These are the failure modes I run into most often.

Infinite BFS/DFS from unvisited cycles in disconnected components

If your graph has multiple disconnected components and your traversal does not track visited nodes properly across them, you can loop forever. The problem is that a naive implementation clears the visited set when starting a new component. If that component has an edge pointing back into an already-visited component, your algorithm will chase that edge and revisit nodes indefinitely.

Keep one shared visited set across all components. Pass it through recursive calls or iterations instead of recreating it for each start node.

Memory exhaustion from dense adjacency matrix

An adjacency matrix allocates V squared cells regardless of how many edges you actually have. A 50,000-vertex graph needs 2.5 billion cells. At 8 bytes per weight, that is about 20 GB. Services running on instances with limited RAM will get killed by the OOM killer and restart in a loop until you fix the representation.

Switch to adjacency lists for graphs over a few thousand vertices unless you actually need O(1) edge lookups and your graph is genuinely dense.

Stack overflow from recursive DFS on deep graphs

Recursive DFS is just recursion, which means it uses the call stack. Chain-like structures or very deep graphs will exhaust stack memory. A 100,000-node linked list will crash a recursive DFS on most systems.

Use the iterative version with an explicit stack. If you genuinely prefer the recursive style for readability, at least switch to iterative before deploying to production.

Race conditions in concurrent graph updates

When two threads add edges between the same vertices simultaneously, both can read the graph as empty, both write their edge, and you end up with duplicates or overwrites. This depends on your data structure, but the underlying problem is the same: non-atomic read-modify-write operations on shared state.

Use thread-safe data structures or add locks around mutations. For read-heavy workloads, immutable snapshots let readers work without contention.

Trade-Off Table

Aspect	Adjacency List	Adjacency Matrix	Edge List
Space complexity	O(V + E)	O(V squared)	O(E)
Add vertex	O(1)	O(V squared)	O(1)
Add edge	O(1)	O(1)	O(1)
Remove vertex	O(V + E)	O(V squared)	O(E)
Remove edge	O(degree)	O(1)	O(E)
Check edge exists	O(degree)	O(1)	O(E)
Iterate neighbors	O(degree)	O(V)	O(E)
Find all edges by weight	O(E)	O(V squared)	O(E log E)
Dense graph performance	Wasteful	Efficient	Wasteful
Sparse graph performance	Efficient	Wasteful	Efficient
Typical use cases	Route planning, social networks, dependency graphs	Dense network analysis, adjacency queries, small dense graphs	MST algorithms, Kruskal, sorting edges by weight

Adjacency lists work well for sparse graphs where you iterate neighbors often. The matrix is better when you need fast edge lookups or your graph has many edges relative to vertices. Edge lists show up in algorithms like Kruskal where you need edges sorted by weight and random access is not important.

Observability Checklist

When running graph-based services in production, you need visibility into the health of your graph structure and traversal operations. This checklist covers the key signals to monitor.

Reference: Cycle detection and structural integrity

Reference: Connected component tracking

Cycle detection and structural integrity

Monitor the ratio of edges to vertices in your graph. A sudden spike in this ratio can indicate data corruption or ingestion bugs inserting duplicate edges. If your graph is supposed to be acyclic (like a dependency graph), alerting on cycle detection failures catches issues before they cascade into application errors.

Memory usage tracking by graph density

For adjacency matrix implementations, graph size directly drives memory consumption. Track your vertex count and alert when you approach your memory budget. For adjacency lists, watch for unexpected growth in the total edge count. If your graph is supposed to stabilize at a certain size and keeps growing, you likely have an ingestion bug creating duplicate or erroneous edges.

Traversal depth monitoring

Track the maximum and average traversal depth for your BFS and DFS operations. Deep traversals consume more memory and CPU. Sudden increases in maximum depth can indicate structural changes in your graph data, such as the introduction of long chains or unexpected connectivity.

Connected component tracking

Monitor the number of connected components and their size distribution. A service that expects a single connected component will behave unexpectedly when given disconnected data. Component count trending upward over time can indicate partial data ingestion failures or upstream data source issues.

Traversal latency percentiles

Graph traversal time scales with the size of the reachable subgraph from your start node. Monitor p50, p95, and p99 latencies for your traversal operations. If p99 is significantly higher than p50, you likely have outliers from traversals hitting large components or pathological structures.

Queue and stack depth for iterative traversals

When using iterative BFS or DFS, track the maximum size of your queue or stack during traversal. Spikes in these depths can precede memory pressure issues, especially for wide or deep graph structures.

Security Notes

Graph structures present unique security concerns that do not map cleanly to traditional application security categories.

Graph traversal denial of service via maliciously connected graphs

A malicious actor can craft input data that produces a graph structure designed to maximize traversal time. For example, a graph with high out-degree nodes concentrated in a small area will cause BFS to explore an enormous frontier before discovering that the target is unreachable. An attacker who can control input data can submit graphs that cause your traversal to consume excessive CPU and memory.

Mitigate this by imposing limits on graph size, vertex degree, and traversal budget before processing. If your service accepts graph data from external sources, validate structural properties before running expensive traversals.

Memory exhaustion from sparse graph flooding

An attacker can submit a graph with a very high number of vertices but few edges. With an adjacency matrix representation, this forces allocation of O(V squared) space even though almost all cells are empty. With an adjacency list, the overhead per vertex can still be significant if you initialize data structures for each vertex.

Validate that incoming graphs meet reasonable bounds on the ratio of edges to vertices, and choose representation based on your expected density rather than trusting user-provided vertex counts.

Timing attacks on shortest path algorithms

If your shortest path implementation runs in time proportional to the number of edges explored, an attacker who can infer timing variations may be able to infer graph structure. For example, if path queries with longer execution times indicate the presence of additional intermediate nodes, an attacker can probe your graph to learn about its topology.

This is a concern primarily for sensitive applications where the existence of connections itself is confidential. Constant-time pathfinding algorithms or noise injection can mitigate this, but the performance cost is significant.

Integer overflow in graph size calculations

When allocating buffers based on vertex count, be careful about integer overflow in size calculations. Computing n * n for matrix allocation with a large vertex count can overflow a 32-bit integer, resulting in a buffer far smaller than intended. Validate vertex counts against maximum allocation sizes before computing buffer dimensions.

Quick Recap Checklist

• Adjacency list: O(V + E) space, good for sparse graphs
• Adjacency matrix: O(V²) space, good for dense graphs, O(1) edge lookup
• BFS: explores level by level, finds shortest path in unweighted graphs
• DFS: explores deep first, used for topological sort, cycle detection
• Both BFS and DFS are O(V + E) for adjacency list representation

Interview Questions

Further Reading

Graph Theory Foundations

• “Introduction to Algorithms” (CLRS), Chapters 22–26 — The definitive textbook covering graph representations, BFS, DFS, topological sort, MSTs, and shortest paths. The pseudocode translates directly into any language.
• “Algorithms” by Robert Sedgewick and Kevin Wayne — Excellent visual approach to graph algorithms with practical Java implementations. Part of the Coursera Algorithms course.

Traversal and Pathfinding Deep Dives

• BFS and DFS visualizer — VisuAlgo: Graph Traversal — Interactive step-through of BFS and DFS on customizable graphs. Helps build intuition for exploration order and visited state.
• Dijkstra’s algorithm interactive — Visualgo: SSSP — Watch Dijkstra relax edges in real time on weighted graphs. Useful for understanding why it fails with negative edges.
• A* search algorithm — Extends Dijkstra with heuristics for faster pathfinding in games and robotics. Start with “Artificial Intelligence: A Modern Approach” (Russell & Norvig), Chapter 3.

Representations and Applications

• Adjacency list vs matrix benchmarks — Stanford CS166: Graph Data Structures — Detailed time/space analysis with concrete benchmarks across graph densities.
• NetworkX library documentation — Python’s premier graph library. The NetworkX tutorial shows real-world usage patterns for adjacency representations.
• Graph databases — Neo4j and Amazon Neptune use adjacency-list-like representations internally. “Graph Databases” by Ian Robinson, Jim Webber, and Emil Eifrém covers the theory behind property graph models.

Advanced Topics

• Tarjan’s algorithm — Find strongly connected components, articulation points, and bridges in O(V + E). CLRS Chapter 22 covers this in depth.
• Bellman-Ford algorithm — Handles negative edge weights and detects negative cycles. Essential when Dijkstra is insufficient.
• Floyd-Warshall algorithm — All-pairs shortest path on dense graphs using dynamic programming. O(V³) but elegant and cache-friendly for small graphs (<1000 vertices).

Conclusion

Adjacency lists store neighbors per vertex (O(V + E) space, efficient for sparse graphs) while adjacency matrices use a 2D grid (O(V²) space, O(1) edge lookup, efficient for dense graphs). BFS explores level-by-level using a queue for shortest paths in unweighted graphs; DFS explores deeply first using a stack or recursion, used for topological sort and cycle detection. Both run in O(V + E) for adjacency list. Handle disconnected graphs by running search from each unvisited vertex with a shared visited set.