Graph Representation¶

★★★★★ Intermediate

Graphs can be represented as edge lists, adjacency lists, or adjacency matrices. The choice depends on graph density and which operations matter most. Adjacency lists are the default for sparse graphs; matrices for dense graphs needing O(1) edge checks.

Key Facts¶

Edge list: Store (src, dest) tuples. Finding neighbors is O(|E|) - rarely used alone
Adjacency list: Map each vertex to its neighbors. Space O(|V| + |E|). Most common
Adjacency matrix: n x n matrix. Space O(|V|^2). O(1) edge check but O(|V|) to list neighbors
Graph with n vertices has at most n(n-1)/2 edges (undirected) or n(n-1) (directed)

Core Terminology¶

Term	Definition
Order	Number of vertices \|V\|
Size	Number of edges \|E\|
Degree	Number of edges at a vertex (in-degree + out-degree for directed)
Sparse	\|E\| << \|V\|^2
Dense	\|E\| close to \|V\|^2
DAG	Directed Acyclic Graph
Complete graph	Every pair connected. Size = \|V\|(\|V\|-1)/2
Bipartite	Vertices split into two sets, edges only between sets

Graph Types¶

Type	Definition
Simple graph	No self-loops, no multi-edges
Multigraph	Multiple edges between same pair allowed
Complete graph	Every pair connected
Bipartite	Two-set partition, edges between sets only
Regular graph	All vertices have same degree

Operation Complexity¶

Operation	Adjacency List	Adjacency Matrix
Space	O(\|V\| + \|E\|)	O(\|V\|^2)
Add vertex	O(1)	O(\|V\|^2) rebuild
Remove vertex	O(\|V\| + \|E\|)	O(\|V\|^2)
Add edge	O(1)	O(1)
Remove edge	O(degree(u))	O(1)
Check edge	O(degree(u))	O(1)
Get neighbors	O(degree(u))	O(\|V\|)

Patterns¶

Adjacency List Implementation¶

class Graph:
    def __init__(self):
        self.adj_list = {}  # vertex -> list of neighbors

    def add_vertex(self, u):
        if u not in self.adj_list:
            self.adj_list[u] = []

    def add_edge(self, u, v):  # directed
        if u in self.adj_list and v in self.adj_list:
            self.adj_list[u].append(v)

    def add_edge_undirected(self, u, v):
        if u in self.adj_list and v in self.adj_list:
            self.adj_list[u].append(v)
            self.adj_list[v].append(u)

    def add_edge_weighted(self, u, v, w):  # directed weighted
        if u in self.adj_list and v in self.adj_list:
            self.adj_list[u].append((v, w))

    def remove_vertex(self, u):
        if u in self.adj_list:
            del self.adj_list[u]
            for v in self.adj_list:
                if u in self.adj_list[v]:
                    self.adj_list[v].remove(u)

    def check_edge(self, u, v):
        return u in self.adj_list and v in self.adj_list[u]

    def build(self, vertices, edges):
        for u in vertices:
            self.add_vertex(u)
        for u, v in edges:
            self.add_edge(u, v)

Use set instead of list for O(1) edge existence check at the cost of extra memory.

Adjacency Matrix Implementation¶

class GraphMatrix:
    def __init__(self):
        self.adj_mat = []

    def add_vertex(self):
        for row in self.adj_mat:
            row.append(0)
        n = len(self.adj_mat) + 1
        self.adj_mat.append([0] * n)

    def add_edge(self, u, v):
        self.adj_mat[u][v] = 1  # undirected: also self.adj_mat[v][u] = 1

    def edge_exists(self, u, v):
        return self.adj_mat[u][v] == 1

    def get_neighbors(self, u):
        return [v for v in range(len(self.adj_mat[u])) if self.adj_mat[u][v] == 1]

Connectivity¶

Concept	Definition
Walk	Sequence of adjacent vertices, repeats allowed
Trail	Walk with no repeated edges
Path	Walk with no repeated vertices
Cycle	Closed path
Connected	Every pair reachable (undirected)
Strongly connected	Directed path between every ordered pair
Weakly connected	Connected when ignoring edge directions

Gotchas¶

Choose adjacency list for sparse graphs (most real-world graphs)
Choose adjacency matrix for dense graphs or when O(1) edge check is critical
For non-integer vertex labels, use hash map to map labels to indices
Removing a vertex from adjacency list requires scanning all lists: O(|V| + |E|)
Matrix delete vertex: swap with last row/column then pop to avoid rebuild