Graph Representation

Jr Codex DSA Notes

Level: Advanced Prerequisites: Module 8, Chapter 4 Time to complete: ~25 minutes

Table of Contents

1. What Is a Graph?
2. Directed vs. Undirected
3. Weighted vs. Unweighted
4. Adjacency List
5. Adjacency Matrix
6. Choosing a Representation
7. Summary & Next Steps

1. What Is a Graph?

A graph is a set of nodes (also called vertices) connected by edges. It's the most general data structure you'll meet in this curriculum — a tree (Module 7) is a graph with no cycles and exactly one path between any two nodes; a linked list (Module 6) is a graph where every node connects to at most one other.

    A --- B
    |     |
    C --- D --- E

Nodes: {A, B, C, D, E} Edges: {(A,B), (A,C), (B,D), (C,D), (D,E)}

2. Directed vs. Undirected

• Undirected — an edge (A, B) means you can travel both A → B and B → A (the diagram above is undirected — a friendship graph is a typical example).
• Directed — an edge A → B only lets you travel from A to B, not the reverse (a "follows" relationship on social media, or a prerequisite chain, are typical examples — the latter is exactly what Chapter 4's topological sort operates on).

3. Weighted vs. Unweighted

• Unweighted — every edge is equally "costly" to traverse. BFS (Chapter 2) finds shortest paths here by counting edges.
• Weighted — each edge has a cost (distance, time, price). Finding shortest paths in a weighted graph needs an algorithm like Dijkstra's, which builds on the priority queue from Module 7 Chapter 4 — out of scope for this introductory module, but worth knowing the term exists.

This module focuses on unweighted graphs, both directed and undirected, since they cover the large majority of interview-level graph questions.

4. Adjacency List

The dominant representation in interview code: a dict mapping each node to a list of its neighbors — this is a direct, natural application of Module 8's hash maps.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
 
print(graph["D"])     # ['B', 'C', 'E'] — O(1) average to find D's neighbor list

Space complexity: O(V + E) — one entry per node (V = number of vertices) plus one entry per edge (E), since each edge appears in exactly one (directed) or two (undirected) neighbor lists.

Building it from a raw edge list:

def build_adjacency_list(edges, directed=False):
    graph = {}
    for a, b in edges:
        graph.setdefault(a, []).append(b)
        if not directed:
            graph.setdefault(b, []).append(a)
    return graph
 
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
print(build_adjacency_list(edges))

5. Adjacency Matrix

A 2D array where matrix[i][j] = 1 (or the edge weight) if an edge exists from node i to node j, else 0.

#      A  B  C  D  E
# A  [ 0, 1, 1, 0, 0 ]
# B  [ 1, 0, 0, 1, 0 ]
# C  [ 1, 0, 0, 1, 0 ]
# D  [ 0, 1, 1, 0, 1 ]
# E  [ 0, 0, 0, 1, 0 ]
 
matrix = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [0, 0, 0, 1, 0],
]
 
# Checking whether an edge exists between node 0 and node 1:
print(matrix[0][1])     # O(1) — direct index

Space complexity: O(V²) — a full grid regardless of how many edges actually exist. Checking whether a specific edge exists is O(1), but finding all neighbors of a node requires scanning an entire row — O(V), even if that node has only one neighbor.

6. Choosing a Representation

Default choice: use an adjacency list (a dict of lists) unless you have a specific reason to need O(1) edge-existence checks on a dense graph — it's what every algorithm in the rest of this module assumes.

7. Summary & Next Steps

Key Takeaways

• A graph is nodes (vertices) plus edges connecting them; trees and linked lists are both special-case graphs.
• Directed edges are one-way; weighted edges carry a cost — this module focuses on unweighted directed/undirected graphs.
• Adjacency list (O(V + E) space) is the standard choice for sparse graphs and is what BFS/DFS in this module are built on; adjacency matrix (O(V²) space) trades memory for O(1) edge-existence checks.

Concept Check

1. Why is a tree considered a special case of a graph?
2. What's the space complexity difference between an adjacency list and an adjacency matrix, and when does that difference matter?
3. Given an adjacency list dict, what's the complexity of finding all neighbors of a given node?

Next Chapter

→ Chapter 2: Breadth-First Search

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index