1. Concept library
  2. Data Structures & Algorithms
  3. Module 11: Graphs

Concept

Graph representations

A graph is nodes and edges. An adjacency list stores each node's neighbours and is the usual choice; an adjacency matrix stores every pair and suits dense graphs or constant-time edge checks.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain adjacency lists and matrices and the cost of each operation on them
  2. Build an adjacency list from an edge list, with both directions for an undirected graph
  3. Spot an undirected graph built with one direction

In practice

A few lines that show Graph representations doing its job.

Python
from collections import defaultdict

edges = [("a", "b"), ("a", "c"), ("b", "d")]

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)            # undirected: both directions

graph["a"]                        # ['b', 'c']
# matrix: m[i][j] = 1 if edge, O(V^2) memory

The common mistake

Watch for

Building an undirected graph with one direction only. Traversal from a node then cannot reach nodes that listed it as a neighbour, and components look disconnected.

What to know first

Your roadmap puts these before Graph representations, unless you already know them.

How it stays learned

Once a session shows you understand Graph representations, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Graph representations.

Next in the moduleBreadth-first search →