Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Graph representation

Graph representation: adjacency matrix, adjacency list, incidence matrix, edge list; directed/undirected, weighted, multigraphs, self-loops, memory and time trade-offs, conversions and implementation in Python.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Graph representation is how we store a graph in memory so that operations like adding edges, checking connections, or running algorithms (like BFS/DFS, MST, Dijkstra) are fast and correct. Software engineers pick the right representation for performance and memory: routing, social networks, compilers, and circuit analysis all depend on efficient graph storage.

Key ideas

  • Undirected graph: A graph where edges have no direction; {u, v} = {v, u}.

  • Directed graph (digraph): A graph where edges have direction; (u, v) ≠ (v, u) in general.

  • Weighted graph: A graph where each edge e ∈ E has a weight w(e) (cost, length, capacity). If not given, assume unit weight 1.

  • Simple graph: A graph with no parallel edges and no self-loops.

  • Multigraph: A graph that may have parallel edges between the same pair of vertices.

  • Self-loop: An edge from a vertex to itself; {u, u} in undirected or (u, u) in directed.

  • Degree (deg(u)): In undirected graphs, the number of incident edges on u; a self-loop contributes 2 to degree. In directed graphs, in-degree is the number of incoming edges to u; out-degree is the number of outgoing edges from u; a self-loop contributes 1 to both in-degree and out-degree.

  • Sparse vs dense graphs: A graph with E ≪ V² (e.g., E = O(V)) is sparse; a graph with E close to V² (e.g., Θ(V²)) is dense.

  • Graph representation: A method to store vertices and edges in memory. The main representations are:

    1. Edge list: List of all edges, typically as pairs (u, v) or triples (u, v, w). Memory: Θ(E) for edges alone; Θ(V + E) if storing the vertex set explicitly. Edge lookup is linear in E; good for input/output and algorithms that sort/process edges once (e.g., Kruskal’s algorithm for MST).
    2. Adjacency matrix: A V×V matrix A where A[i][j] is 1 (or weight w) if edge i→j exists, else 0 (or ∞/None). For undirected simple graphs, the matrix is symmetric (A[i][j] = A[j][i]). Memory: Θ(V²). Pros: O(1) edge existence check; easy to represent dense graphs and do matrix-based algorithms (e.g., Warshall’s algorithm for transitive closure). Cons: space-inefficient for sparse graphs; enumerating neighbors of a vertex is O(V).
    3. Adjacency list: An array or dictionary mapping each vertex to a list (or set/dictionary) of its neighbors (and optional weights). Memory: Θ(V + E). Pros: space-efficient for sparse graphs; enumerating neighbors of a vertex u is O(deg(u)). Cons: checking if an edge exists is O(deg(u)) if using a list; average O(1) if using a hash-set per vertex.
    4. Incidence matrix: A V×E matrix B where each column represents an edge. For undirected simple graphs: for edge e = {u, v}, B[u][e] = 1, B[v][e] = 1, others 0. For directed graphs, common conventions: B[u][e] = −1 for tail u, B[v][e] = +1 for head v, others 0 (weights may replace 1 in weighted cases). Memory: Θ(V·E). Pros: convenient in some linear-algebraic formulations and for multigraphs (parallel edges get their own columns). Cons: usually larger than lists/matrices for typical V, E.
  • Exact statements commonly examined:

    • “For a graph with V vertices and E edges, an adjacency matrix uses Θ(V²) memory, supports O(1) time for edge existence checks, and O(V) time to enumerate all neighbors of a vertex.” Assumptions: vertices are indexed 0…V−1; unit-cost RAM model.
    • “For a graph with V vertices and E edges, an adjacency list uses Θ(V + E) memory, supports O(deg(u)) time to test edge (u, v) with list per vertex, and enumerates neighbors of u in Θ(deg(u)) time.” Assumptions: linked list or dynamic array per vertex; no per-vertex hashing unless stated.
    • “For an incidence matrix with V vertices and E edges, the space is Θ(V·E). Edge existence between u and v is O(E) in general.” Assumption: columns are edges; need to scan columns unless auxiliary index provided.
  • Handling special cases in representations:

    • Self-loops in adjacency matrix: set A[u][u] = 1 (or weight w). In adjacency lists: include u in its own neighbor list.
    • Parallel edges in adjacency matrix: store counts (integers) or weights aggregated; otherwise needs multigraph-specific structure. In adjacency lists: allow duplicates in the list or store list of edge objects.
    • Weights: adjacency matrix cells store numeric weights; use a sentinel (None, ∞) for “no edge”. In adjacency lists: store (neighbor, weight) pairs.
  • Time–space trade-offs summary:

    • Edge existence check: matrix O(1), list O(deg(u)), incidence O(E).
    • Insert/delete edge: matrix O(1), list average O(1) amortized for insert; delete O(deg(u)) unless using additional indexing.
    • Iterate all edges: matrix O(V²) scan; list Θ(V + E); incidence Θ(V·E) to scan the matrix; Θ(E) only if each column also stores its endpoints separately (outside the matrix).
  • How to draw typical diagrams in an exam:

    • Adjacency matrix diagram: Draw a square grid with rows and columns labeled by vertex names (e.g., v1…vV). Shade or write 1 (or w) in cell (i, j) if edge exists. For undirected graphs, mention symmetry along the main diagonal. Label the diagonal cells (i, i) and indicate self-loops if any.
    • Adjacency list diagram: Draw each vertex as a box on the left in a vertical column. From each box, draw a horizontal linked list of neighbor nodes (boxes) to the right, in ascending vertex order. For weighted graphs, include weight in each neighbor box as (v, w). For directed graphs, arrows from u to its neighbor nodes emphasize direction. Mark null at list ends.
    • Incidence matrix diagram: Draw V rows for vertices, E columns for edges e1…eE. Fill with 0 except mark either two 1’s per undirected edge (at the incident vertex rows) or −1/+1 for directed edges (tail/head). Label each column with the corresponding edge pair for clarity.
  • Choosing a representation (guidelines):

    • Use adjacency list for sparse graphs, dynamic graphs, and algorithms that need to iterate neighbors frequently (DFS, BFS, Dijkstra with binary heap, Prim with adjacency lists).
    • Use adjacency matrix for dense graphs, fast edge checks, simple constant-time updates, or matrix-based algorithms (Warshall’s algorithm for path matrices, Floyd–Warshall for all-pairs shortest paths).
    • Use edge list for input/output and algorithms that sort/process edges (Kruskal’s algorithm). Use incidence matrix when a column-per-edge structure is algebraically convenient or when representing multigraphs cleanly. Note: BFS/DFS run in Θ(V + E) with adjacency lists; with adjacency matrices they take Θ(V²).

Formulas

  • A = [[0]*V for _ in range(V)] — adjacency matrix A of size V×V; indices i, j are integers (unitless), valid when vertices are 0…V−1.

  • adj = {u: [] for u in vertices} — adjacency list as dict from vertex to list of neighbors; works for arbitrary hashable vertex labels.

  • adj_w = {u: [(v, w)]} — weighted adjacency list: store (neighbor, weight) pairs; weights w are numbers (unit depends on problem domain; in CS usually unitless cost).

  • edges = [(u, v)] or edges_w = [(u, v, w)] — edge list for un/weighted graphs.

  • has_edge = (A[u][v] != 0) — edge existence in matrix; assumes 0 means no edge; valid only when edge weights are strictly positive (no 0-weight edges). Otherwise use a sentinel like None or +∞.

  • for v in adj[u]: ... — neighbor iteration in adjacency list; Θ(deg(u)).

  • B = [[0]*E for _ in range(V)] — incidence matrix with V rows and E columns.

  • Complexity statements (remember):

    • Space(matrix) = Θ(V²) — V is number of vertices.
    • Space(list) = Θ(V + E) — E is number of edges.
    • EdgeCheck(matrix) = O(1); EdgeCheck(list) = O(deg(u)).
    • IterateNeighbors(u, list) = Θ(deg(u)); IterateNeighbors(u, matrix) = Θ(V).

Worked examples

Example 1 — Build and print an adjacency matrix (undirected, weighted) Problem: Read number of vertices V (0…V−1), number of edges E, then E lines of edges u v w. Build the V×V matrix with weights; if multiple edges appear between same pair, keep the minimum weight. Print the matrix as space-separated rows. Assume w > 0; 0 denotes no edge.

Python program:

# Adjacency matrix for undirected weighted graph
# Input:
# V E
# then E lines: u v w
# Output: V lines, each with V integers (0 for no edge)

def build_adj_matrix(V, edges):
    A = [[0 for _ in range(V)] for _ in range(V)]
    for u, v, w in edges:
        if A[u][v] == 0 or w < A[u][v]:
            A[u][v] = w
            A[v][u] = w  # undirected: symmetric
    return A

def main():
    import sys
    data = sys.stdin.read().strip().split()
    it = iter(data)
    V = int(next(it))
    E = int(next(it))
    edges = []
    for _ in range(E):
        u = int(next(it))
        v = int(next(it))
        w = int(next(it))
        edges.append((u, v, w))
    A = build_adj_matrix(V, edges)
    for i in range(V):
        print(' '.join(str(A[i][j]) for j in range(V)))

if __name__ == '__main__':
    main()

Sample input:

5 6
0 1 3
1 2 2
2 3 4
3 4 5
4 0 1
1 4 7

Exact output:

0 3 0 0 1
3 0 2 0 7
0 2 0 4 0
0 0 4 0 5
1 7 0 5 0

Explanation: Matrix is symmetric. No edge shown as 0. If there were parallel edges, the code keeps the smaller weight.

Example 2 — Build and print a weighted adjacency list (directed) Problem: Read vertices labeled by strings, number of edges E, then E lines: src dst weight. Print adjacency list with neighbors sorted lexicographically by label.

Python program:

# Adjacency list for directed weighted graph with string labels
# Input:
# N (number of vertices)
# N vertex labels (strings without spaces)
# E (number of edges)
# E lines: src dst w
# Output: lines "u: (v1,w1) (v2,w2) ..." with neighbors sorted by v

def build_adj_list(vertices, edges):
    adj = {u: [] for u in vertices}
    for u, v, w in edges:
        adj[u].append((v, w))
    # sort neighbors by vertex label for deterministic output
    for u in vertices:
        adj[u].sort(key=lambda x: x[0])
    return adj

def main():
    import sys
    data = sys.stdin.read().strip().split()
    it = iter(data)
    N = int(next(it))
    vertices = [next(it) for _ in range(N)]
    E = int(next(it))
    edges = []
    for _ in range(E):
        u = next(it)
        v = next(it)
        w = int(next(it))
        edges.append((u, v, w))
    adj = build_adj_list(vertices, edges)
    for u in vertices:
        nbrs = ' '.join(f'({v},{w})' for v, w in adj[u])
        print(f"{u}: {nbrs}")

if __name__ == '__main__':
    main()

Sample input:

4
A B C D
5
A B 5
A D 1
B C 2
C A 3
D C 4

Exact output:

A: (B,5) (D,1)
B: (C,2)
C: (A,3)
D: (C,4)

Explanation: Directed edges; no symmetry. Sorting ensures stable exam outputs.

Example 3 — Convert adjacency matrix to edge list (directed, unweighted) Problem: Read V, then V×V binary matrix. Produce E and then E lines of edges u v (0-based) where A[u][v] = 1. Self-loops are allowed. For deterministic output, list edges in row-major order.

Python program:

# Convert adjacency matrix (0/1) to edge list for a directed graph
# Input:
# V
# V lines each with V integers (0 or 1)
# Output:
# E (number of edges)
# followed by E lines: u v

def matrix_to_edges(A):
    V = len(A)
    edges = []
    for u in range(V):
        for v in range(V):
            if A[u][v] == 1:
                edges.append((u, v))
    return edges

def main():
    import sys
    lines = [line.strip() for line in sys.stdin.read().strip().splitlines() if line.strip()]
    V = int(lines[0])
    A = []
    for i in range(1, V+1):
        row = [int(x) for x in lines[i].split()]
        A.append(row)
    edges = matrix_to_edges(A)
    print(len(edges))
    for u, v in edges:
        print(u, v)

if __name__ == '__main__':
    main()

Sample input:

4
0 1 0 0
0 0 1 0
1 0 1 1
0 0 0 0

Exact output:

5
0 1
1 2
2 0
2 2
2 3

Explanation: Row-major scan lists edges in increasing (u, v). Self-loop at (2,2) is included.

Common mistakes

  • Off-by-one indexing: treating vertices labeled 1…V as 0…V−1 in arrays; always map labels explicitly.
  • Assuming adjacency lists guarantee O(1) edge checks: it is O(deg(u)) with plain lists; O(1) average only if a hash-set/dictionary is used per vertex.
  • Memory underestimation: writing “adjacency matrix uses O(E)” — incorrect; it uses Θ(V²) regardless of E.
  • Mishandling parallel edges: adjacency matrix overwriting an earlier weight without a defined rule; in an exam, state your convention (e.g., keep minimum weight).
  • Not representing self-loops correctly: forgetting A[u][u] or omitting u in its own list.
  • Printing unpredictable order: unsorted adjacency lists cause mismatched outputs; sort neighbors for deterministic answers.
  • Using infinity as a number without defining it: if you use a sentinel like ∞ or None for “no edge,” state it clearly.

For your exam

  • Short notes: compare adjacency matrix vs adjacency list (space complexity, edge check time, neighbor iteration time); incidence matrix definition and use-cases.
  • Derivations/justifications: prove space is Θ(V²) for matrix (count cells), Θ(V + E) for list (sum of list lengths equals E for directed, 2E for undirected counted across both ends). Show neighbor iteration complexities using degree.
  • Programs: build/print adjacency matrix or list; convert between matrix and edge list; handle directed/undirected and weighted cases; include input format, clear output, and comments.
  • Diagrams: draw a small graph (4–6 vertices) and its adjacency matrix/list; label axes, show symmetry for undirected, and show weights.
  • What full-marks answers include: clear assumptions (indexing, directedness, sentinel values), correct complexities with Θ/O notation, correct handling of self-loops/parallel edges if mentioned, neat and labeled diagrams, and deterministic program outputs.

Quick check

  1. For a graph with V vertices and E edges, which representation is most space-efficient when E = O(V)? Why?
  2. In an undirected simple graph stored as an adjacency matrix, how many entries are necessarily zero on the diagonal? What does a non-zero diagonal entry mean?
  3. What is the time to check if edge (u, v) exists in (a) adjacency matrix, (b) adjacency list with lists per vertex?

Answers: 1) Adjacency list, because it uses Θ(V + E) space which is Θ(V) when E = O(V), unlike matrix Θ(V²). 2) All V diagonal entries are zero; a non-zero diagonal entry indicates a self-loop at that vertex. 3) (a) O(1), (b) O(deg(u)).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?