8.1 Graph Representation: Put Vertices and Edges in Memory

Chapter 8 · Graph Fundamentals | Prerequisites: Arrays, Lists, and Classes | Next: DFS and BFS. This section establishes a consistent contract for vertices, edges, self-loops, duplicate edges, and invalid vertex indices, then compares adjacency matrices and adjacency lists.

Start from "Paths" Rather than "Hierarchies"

The trees studied earlier have a parent-child hierarchy. General graphs also allow A to connect to B and C and return to A through other edges. A, B, and C are vertices; their connections are edges. Edges may have a direction: A → B does not imply a reverse connection.

Two common ways to represent these connections are:

• Adjacency Matrix: The entry at row u, column v indicates whether an edge exists between vertices u → v.
• Adjacency List: Each vertex maintains a list of its outgoing neighbors.

This lesson follows a clear teaching contract: vertices must be integers from 0..n-1; self-loops are allowed; adding the same edge twice does not create parallel edges; invalid indices throw IndexError. In real-world projects, parallel edges can be allowed, but they need multiple edge records or an edge multiplicity; one boolean cannot represent them. n must be a nonnegative integer and directed a boolean. Do not modify these fields after construction.

A Reproducible Implementation

class AdjacencyMatrixGraph:
    """Boolean adjacency matrix; fixed vertex count, multiple edges are naturally deduplicated."""

    def __init__(self, n, directed=False):
        if not isinstance(n, int):
            raise TypeError("n must be an integer")
        if not isinstance(directed, bool):
            raise TypeError("directed must be a boolean")
        if n < 0:
            raise ValueError("n must be non-negative")
        self.n = n
        self.directed = directed
        self._matrix = [[False] * n for _ in range(n)]

    def _check(self, vertex):
        if not isinstance(vertex, int) or not 0 <= vertex < self.n:
            raise IndexError(f"vertex out of range: {vertex!r}")

    def add_edge(self, source, target):
        self._check(source)
        self._check(target)
        self._matrix[source][target] = True
        if not self.directed:
            self._matrix[target][source] = True

    def remove_edge(self, source, target):
        self._check(source)
        self._check(target)
        self._matrix[source][target] = False
        if not self.directed:
            self._matrix[target][source] = False

    def has_edge(self, source, target):
        self._check(source)
        self._check(target)
        return self._matrix[source][target]

    def neighbors(self, vertex):
        self._check(vertex)
        return [other for other, linked in enumerate(self._matrix[vertex]) if linked]

class AdjacencyListGraph:
    """Ordered adjacency list; use a list to preserve insertion order, explicitly suppress duplicate edges."""

    def __init__(self, n, directed=False):
        if not isinstance(n, int):
            raise TypeError("n must be an integer")
        if not isinstance(directed, bool):
            raise TypeError("directed must be a boolean")
        if n < 0:
            raise ValueError("n must be non-negative")
        self.n = n
        self.directed = directed
        self._adjacency = [[] for _ in range(n)]

    def _check(self, vertex):
        if not isinstance(vertex, int) or not 0 <= vertex < self.n:
            raise IndexError(f"vertex out of range: {vertex!r}")

    def add_edge(self, source, target):
        self._check(source)
        self._check(target)
        if target not in self._adjacency[source]:
            self._adjacency[source].append(target)
        if not self.directed and source != target:
            if source not in self._adjacency[target]:
                self._adjacency[target].append(source)

    def remove_edge(self, source, target):
        self._check(source)
        self._check(target)
        if target in self._adjacency[source]:
            self._adjacency[source].remove(target)
        if not self.directed and source != target:
            if source in self._adjacency[target]:
                self._adjacency[target].remove(source)

    def has_edge(self, source, target):
        self._check(source)
        self._check(target)
        return target in self._adjacency[source]

    def neighbors(self, vertex):
        self._check(vertex)
        return list(self._adjacency[vertex])

if __name__ == "__main__":
    names = ["A", "B", "C", "D", "E"]
    graph = AdjacencyListGraph(len(names))
    for source, target in [(0, 1), (0, 2), (1, 3), (2, 4)]:
        graph.add_edge(source, target)
    for vertex, name in enumerate(names):
        print(name, "->", [names[n] for n in graph.neighbors(vertex)])

Execution steps:

1. Save as graph_representation.py.
2. Run python3 graph_representation.py.
3. Expect to see A connected to B and C, B connected to A and D; undirected edges should be accessible from both ends.

Work through the matrix manually

For undirected edges {A,B}, {A,C}, {B,D}, and {C,E}, the matrix is:

    A B C D E
A   0 1 1 0 0
B   1 0 0 1 0
C   1 0 0 0 1
D   0 1 0 0 0
E   0 0 1 0 0

It is symmetric across the main diagonal because every path can be traversed in both directions. If A→B is a one-way path, only write matrix[A][B], and the matrix need not be symmetric.

How to Choose

Let V count vertices, E count edges, and d(u) be the length of u's neighbor list in this implementation. An undirected non-loop edge appears twice; a self-loop appears once. Total storage remains O(V + E). The matrix enumerates neighbors by vertex number, while the list uses insertion order. The same graph can therefore produce different traversal orders.

Operation or Scenario	Adjacency Matrix	Ordered Adjacency List in This Text
Space	O(V²)	O(V + E)
Query u → v	O(1)	O(d(u)+1)
Enumerate neighbors of u	O(V)	O(d(u)+1)
Add/remove a directed edge	O(1)	O(d(u)+1)
Add/remove an undirected edge	O(1)	O(d(u)+d(v)+1)

These classes fix the vertex set and provide no method to add vertices. An extended adjacency-list design could append an empty list; a matrix would need storage for a new row and column. Removing an edge from a fixed-size matrix only changes cells to False. Initializing an empty matrix takes Θ(V²) and empty adjacency lists Θ(V). Building the list graph edge by edge also pays for list-based duplicate checks; this construction is not automatically O(V+E). Don't rely on benchmark runs from a single machine to substitute for complexity analysis; data scale, density, language implementation, and cache behavior all influence outcomes.

In practice, if you need both neighbor traversal and fast duplicate detection, you can replace each adjacency container with set. The cost is that the default traversal order is no longer suitable as a contract for algorithmic outputs. This text uses lists to ensure that the results of DFS and BFS are reproducible.

Boundary Check List

• Isolated node: Even without edges, a blank adjacency list must be retained.
• Self-loop: In an undirected graph, u → u is stored once and makes bipartite testing return false. By the standard graph-theory convention, an undirected self-loop contributes 2 to degree, so len(neighbors(u)) is not the standard degree when a self-loop exists.
• Duplicate Edge: This implementation removes duplicates; if your business requires parallel edges such as flights or departures, retain multiple edge records or their multiplicity.
• Directionality: u → v does not automatically imply v → u.
• Return a copy: neighbors() does not expose the internal list, so clearing the returned value won't damage the graph.

Small Exercise

Build a separate directed graph with vertices A through E and only edges A→B, A→C, and C→A. Then answer:

1. Why is has_edge(B, A) false?
2. Do the edges C→A and A→C form a cycle of length 2?
3. If we remove the edge A→C, can C still reach A directly?

Start by drawing five or six points on paper, then compare with the program output. The most time-consuming part of this chapter isn't writing code; it's internalizing the concept that "a node can return to itself via multiple paths."

The Map Is Drawn

Representation alters operational cost without changing the structure of the graph itself. A matrix trades O(V²) space for constant-time edge lookup; adjacency lists use O(V+E) space and take O(V+E) to enumerate all neighbors across the graph, with edge lookup cost depending on out-degree and the adjacency container's performance. Undirected edges, self-loops, duplicate edges, and returned copies must all be explicitly defined in the contract.

The example has loaded the vertices and edges into memory. Next, traverse the same structure with DFS, BFS, and structural graph algorithms.