Data StructuresIntermediate14 min readUpdated March 2025

Graph Representation

Graphs model relationships between entities. The choice of representation — adjacency list or adjacency matrix — significantly impacts the time and space complexity of graph algorithms. Understanding both is essential for solving graph problems efficiently.

Graph Terminology

A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices.

Key properties: - Directed (Digraph) — Edges have direction (A -> B does not imply B -> A). Models: web links, dependencies, social media following. - Undirected — Edges have no direction (A -- B implies B -- A). Models: friendships, roads, networks. - Weighted — Edges have associated weights/costs. Models: distances, latencies, capacities. - Degree — Number of edges connected to a vertex. In directed graphs: in-degree and out-degree. - Path — A sequence of vertices connected by edges. - Cycle — A path that starts and ends at the same vertex. - Connected — Every vertex is reachable from every other vertex (undirected). - DAG — Directed Acyclic Graph. No cycles. Used for dependency resolution, topological sort.

Adjacency List vs Adjacency Matrix

Two primary ways to represent a graph:

Adjacency List — Array/dict of lists. Each vertex stores a list of its neighbors. Space: O(V + E). Edge lookup: O(degree). Best for sparse graphs (few edges).
Adjacency Matrix — V x V 2D array. matrix[i][j] = 1 (or weight) if edge exists. Space: O(V^2). Edge lookup: O(1). Best for dense graphs (many edges).
Most real-world graphs are sparse (social networks, road maps) — use adjacency lists.
Use adjacency matrix when you need O(1) edge existence checks or the graph is dense.

Graph Representation in Python

Implementing both representations with weighted and unweighted graphs:

python

from collections import defaultdict

# ---- Adjacency List (most common) ----
class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(list)
        self.directed = directed

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

    def neighbors(self, v):
        return self.adj[v]

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

    def __repr__(self):
        return '
'.join(f"{v}: {neighbors}" for v, neighbors in self.adj.items())

# Undirected weighted graph
g = Graph(directed=False)
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 8)
print(g)

# ---- Adjacency Matrix ----
class GraphMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0] * n for _ in range(n)]

    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight   # Undirected

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

    def print_matrix(self):
        for row in self.matrix:
            print(row)

gm = GraphMatrix(4)
gm.add_edge(0, 1, 4)
gm.add_edge(0, 2, 2)
gm.add_edge(1, 3, 5)
gm.print_matrix()

# ---- Edge List (simple, for algorithms like Kruskal's) ----
edges = [
    (4, 'A', 'B'),   # (weight, u, v)
    (2, 'A', 'C'),
    (1, 'B', 'C'),
    (5, 'B', 'D'),
]
edges.sort()   # Sort by weight for Kruskal's MST

Building Graphs from Input

Common patterns for constructing graphs from problem input:

python

# ---- From edge list ----
def build_graph(n, edges):
    """n vertices, edges as list of [u, v] pairs"""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

# ---- From grid (2D matrix) ----
def grid_to_graph(grid):
    """Convert a 2D grid to adjacency list"""
    rows, cols = len(grid), len(grid[0])
    adj = defaultdict(list)
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '#':   # Not a wall
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
                        adj[(r,c)].append((nr,nc))
    return adj

# ---- Detect if graph is bipartite (2-colorable) ----
def is_bipartite(adj, n):
    color = {}
    for start in range(n):
        if start in color:
            continue
        queue = [start]
        color[start] = 0
        while queue:
            node = queue.pop(0)
            for neighbor in adj[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True

Key Takeaways

Adjacency lists use O(V+E) space and are best for sparse graphs; matrices use O(V^2) for dense graphs.
Directed graphs model one-way relationships; undirected model bidirectional connections.
Most real-world graphs (social networks, maps) are sparse — use adjacency lists by default.
Edge lists are useful for algorithms that process all edges (Kruskal's MST, Bellman-Ford).
Grid problems are graph problems — convert the 2D grid to an adjacency list with 4-directional neighbors.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com