Graph Representation — Represent graphs using adjacency...

SECTION 1

Historical Context & Motivation

Long before computers existed, mathematicians were already thinking about connections between things. In 1736, the Swiss mathematician Leonhard Euler tackled the famous Königsberg Bridge Problem: could a person walk through a city crossing each of its seven bridges exactly once? To solve it, Euler stripped away the map's details and focused only on the landmasses (nodes) and the bridges (edges) connecting them. This was the birth of graph theory — a branch of mathematics that studies how objects relate to one another.

Today, graphs are everywhere in computing. Social networks like Instagram model users as nodes and follow relationships as edges. Google Maps uses graphs to find the shortest driving route. Even the internet itself is a massive graph of interconnected web pages. The question that drives this lesson is: how do we represent a graph in code so that a computer can work with it efficiently?

1736

Euler & the Königsberg Bridges

Leonhard Euler models landmasses and bridges as nodes and edges, founding graph theory as a field of study.

1956

Dijkstra's Shortest Path

Edsger Dijkstra invents a famous algorithm for finding shortest paths in a graph, demonstrating the need for efficient graph storage in memory.

1970s

Adjacency Lists Gain Popularity

As computer memory was expensive and limited, adjacency lists became the preferred representation for sparse graphs because they use far less memory than matrices.

2004

Facebook's Social Graph

Facebook launches, eventually building one of the world's largest graphs — billions of users connected by friendships — stored internally using adjacency-list-like structures.

Throughout this history, one pattern remains constant: to do anything useful with a graph, you first need to choose a data structure that stores nodes and edges. The adjacency list, especially when built with Python dictionaries, is the most common and practical choice for most real-world applications. Let's learn why.

SECTION 2

Core Principles & Definitions

Before diving into code, you need a solid understanding of the vocabulary that surrounds graphs. A graph is a collection of vertices (also called nodes) connected by edges (also called links). An adjacency list is a way to store which nodes are connected to which other nodes. In Python, the most natural way to build one is with a dict where each key is a node and each value is a list or set of that node's neighbors.

Vertex (Node)

An individual entity in the graph — a person, a city, or a web page. Each vertex becomes a key in the dictionary.

Edge (Link)

A connection between two vertices. In the adjacency list, an edge from A to B means B appears in A's neighbor list (the dictionary value).

Undirected vs. Directed

In an undirected graph, edges go both ways (friendships). In a directed graph, edges have a direction (following someone on Twitter).

Adjacency List

A dictionary mapping every node to its collection of neighbors. Uses dict[node] = list/set of neighbors. Memory-efficient for graphs where most nodes are NOT connected to each other.

List vs. Set for Neighbors

Using a list allows duplicate edges and preserves insertion order. Using a set prevents duplicates and gives O(1) membership checking.

✦ KEY TAKEAWAY

Think of an adjacency list like a contact list on your phone. Each person (vertex) has their own entry, and under each entry you see a list of their close friends (edges). If Alice lists Bob as a friend, and Bob lists Alice, that's an undirected edge. If Alice follows Bob but Bob doesn't follow Alice back, that's a directed edge. The Python dictionary is the phone — each key is a name, and each value is that name's contact list.

SECTION 3

Visualizing an Adjacency List

The diagram below shows a small undirected graph on the left and its corresponding adjacency list representation on the right. Each node in the graph (A through E) appears as a key in the dictionary. The connections you see drawn between nodes are captured in each key's list of neighbors.

Left: an undirected graph with 5 nodes (A–E) and 6 edges. Right: the same graph stored as a Python dictionary where each key maps to a list of its direct neighbors. Notice that edge A–B appears in both A's list and B's list because the graph is undirected.

Notice in the diagram that node B has three neighbors (A, D, E), so its list contains three elements. Node A has only two neighbors (B, C). In an undirected graph, every edge is recorded twice — once for each endpoint. This is why "A" appears in B's list and "B" appears in A's list. If this were a directed graph, you would only add the neighbor in the direction the edge points.

SECTION 4

How It Works — Building the Dictionary

Building an adjacency list in Python comes down to three operations: creating the dictionary, adding nodes, and adding edges. Let's look at the patterns for both list-based and set-based representations.

Pattern 1 — Dict of Lists

CREATING AN UNDIRECTED GRAPH (LIST)

graph = {"A": [], "B": [], "C": []}

Start with an empty list for each node. Then to add an edge between A and B: graph["A"].append("B") and graph["B"].append("A"). For a directed edge A → B, you only append to A's list.

Pattern 2 — Dict of Sets

CREATING AN UNDIRECTED GRAPH (SET)

graph = {"A": set(), "B": set(), "C": set()}

To add an edge between A and B: graph["A"].add("B") and graph["B"].add("A"). Using .add() on a set automatically prevents duplicate edges.

Time Complexity at a Glance

SPACE COMPLEXITY

Space = O(V + E)

V = number of vertices (dictionary keys). E = number of edges (total items across all neighbor lists). This is much better than an adjacency matrix which uses O(V²) space.

EDGE LOOKUP TIME

List → O(degree) | Set → O(1)

Checking if edge (A, B) exists requires searching A's neighbor collection. With a list you scan through each element — O(degree of A). With a set you get constant-time O(1) lookup.

💡 When to use list vs. set?

Use a list when you need to allow parallel edges (multiple edges between the same two nodes) or when insertion order matters. Use a set when you want fast edge-existence checks and automatic duplicate prevention. For most introductory problems, either works fine.

SECTION 5

Directed vs. Undirected Adjacency Lists

The difference between directed and undirected graphs directly affects how you build the adjacency list. The diagram below compares the same set of connections stored as an undirected graph (mutual friendships) and a directed graph (one-way follows). Pay close attention to which lists each node appears in.

Left: undirected graph — edge 1-2 appears in both node 1's and node 2's neighbor lists (total of 8 list entries for 4 edges). Right: directed graph — edge 1→2 only appears in node 1's list (total of 4 list entries for 4 edges). Node 4 has no outgoing edges, so its list is empty.

In the undirected graph, there are 4 edges, but the adjacency list stores 8 total entries (each edge counted twice). In the directed graph with the same 4 edges, only 4 entries are stored. This is an important distinction when you think about memory usage. For undirected graphs, the total number of items across all neighbor lists equals 2 × E, while for directed graphs it equals exactly E.

Key differences between undirected and directed adjacency list operations

Operation	Undirected	Directed
Add edge (u, v)	Append v to graph[u] AND u to graph[v]	Append v to graph[u] only
Remove edge (u, v)	Remove from both lists	Remove from graph[u] only
Total list entries	2 × E	E
Degree of node u	`len(graph[u])`	out-degree: `len(graph[u])`; in-degree requires scanning all lists

SECTION 6

Worked Example — Building a Social Network Graph

Let's walk through a complete example. Suppose you are building a simple social network where users can be friends with each other (an undirected graph). The users are Alice, Bob, Charlie, and Diana. The friendships are: Alice–Bob, Alice–Charlie, Bob–Diana, and Charlie–Diana.

Building an Undirected Social Network Graph

Step 1 — Initialize the dictionaryCreate a dictionary with each user as a key and an empty list as the value. This sets up the structure before any edges are added.

graph = {"Alice": [], "Bob": [], "Charlie": [], "Diana": []}

Step 2 — Add edge Alice–BobSince this is an undirected graph, you add Bob to Alice's list and Alice to Bob's list.

graph["Alice"].append("Bob")
graph["Bob"].append("Alice")

Step 3 — Add remaining edgesRepeat the same process for Alice–Charlie, Bob–Diana, and Charlie–Diana. Each edge requires two .append() calls.

graph["Alice"].append("Charlie")
graph["Charlie"].append("Alice")
graph["Bob"].append("Diana")
graph["Diana"].append("Bob")
graph["Charlie"].append("Diana")
graph["Diana"].append("Charlie")

Step 4 — Inspect the final adjacency listPrint the dictionary to verify it matches the friendships you intended.

{
  "Alice":   ["Bob", "Charlie"],
  "Bob":     ["Alice", "Diana"],
  "Charlie": ["Alice", "Diana"],
  "Diana":   ["Bob", "Charlie"]
}

Step 5 — Query the graphYou can now answer questions like 'Who are Alice's friends?' or 'Are Bob and Charlie friends?' using simple dictionary and list operations.

print(graph["Alice"])         # ['Bob', 'Charlie']
print("Charlie" in graph["Bob"])  # False — they are not directly connected

🛠️ Helper Function Tip

To avoid writing two lines every time you add an undirected edge, create a helper function: def add_edge(graph, u, v): graph[u].append(v); graph[v].append(u). This keeps your code clean and reduces the chance of forgetting one direction.

SECTION 7

Adjacency List vs. Adjacency Matrix

The adjacency list is not the only way to represent a graph. The other major approach is an adjacency matrix — a 2D grid (V × V) where cell [i][j] equals 1 if there's an edge from node i to node j, and 0 otherwise. Each representation has its strengths, and choosing between them depends on the properties of your graph.

Comparison of adjacency list and adjacency matrix representations

Feature	Adjacency List	Adjacency Matrix
Space complexity	O(V + E) — efficient for sparse graphs	O(V²) — wastes space when few edges exist
Check if edge exists	O(degree) with list, O(1) with set	O(1) — just look up matrix[i][j]
List all neighbors of a node	O(degree) — iterate through the list	O(V) — must scan entire row
Add an edge	O(1) — append/add to the list/set	O(1) — set matrix[i][j] = 1
Best for	Sparse graphs (social networks, road maps)	Dense graphs or when frequent edge-existence checks are needed

✦ KEY TAKEAWAY

Think of it this way: an adjacency list is like keeping a notebook where you only write down the people each person actually knows. An adjacency matrix is like creating a giant spreadsheet with every person's name on both the rows and columns, then filling in yes/no for every possible pair. If your school has 2,000 students and each student knows about 20 others, the notebook approach saves you from filling in millions of empty cells.

SECTION 8

Connection to Advanced Topics

Once you can represent a graph with an adjacency list, you unlock a whole family of powerful algorithms. These algorithms solve real-world problems like finding the shortest route on a map, detecting cycles in dependencies, and determining if a network is fully connected.

How today's foundational concepts connect to more advanced graph algorithms

This Lesson (Intro)	Next Steps (Advanced)
Store neighbors in a list or set	Store edge weights as tuples: graph[u] = [(v, weight)]
Manually add edges one at a time	Build graphs from files, APIs, or edge lists automatically
Check who a node's neighbors are	Traverse the entire graph with BFS (breadth-first search) or DFS (depth-first search)
Simple undirected/directed graphs	Weighted graphs, DAGs (directed acyclic graphs), multigraphs
Count neighbors with len(graph[u])	Find shortest paths (Dijkstra), detect cycles, topological sort

The adjacency list you learn today is the exact same data structure used inside graph libraries like networkx in Python. Mastering this foundation means you'll be ready to implement BFS, DFS, Dijkstra's algorithm, and more — all of which expect the graph to be provided as an adjacency list. Think of this lesson as building the stage that every future graph algorithm will perform on.

🚀 Using defaultdict for cleaner code

In advanced usage, you'll often see from collections import defaultdict followed by graph = defaultdict(list). This eliminates the need to manually initialize each key — if a key doesn't exist, it's automatically created with an empty list. This is a common Python pattern you'll encounter in coding interviews and competitive programming.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

In an undirected graph with 5 nodes and 7 edges, how many total entries will be stored across all neighbor lists in the adjacency list? Explain your reasoning.

PROBLEM 2 — BASIC CALCULATION

Write Python code to create an adjacency list (using a dict of lists) for a directed graph with nodes 1, 2, 3, and 4, and edges 1→2, 1→3, 2→4, and 3→4. Then write an expression that returns the out-degree of node 1.

PROBLEM 3 — INTERMEDIATE

You are given an edge list: edges = [("X","Y"), ("Y","Z"), ("X","Z"), ("Z","W")]. Write a Python function build_undirected_graph(edges) that takes this list and returns a dict-of-sets adjacency list. What does the resulting dictionary look like?

PROBLEM 4 — APPLIED

A school has 6 classrooms and the hallways connecting them form the following undirected edges: (Room1, Room2), (Room1, Room3), (Room2, Room4), (Room3, Room4), (Room4, Room5), (Room5, Room6). Build the adjacency list and then write code to find which room has the most hallway connections (highest degree). What room is it, and what is its degree?

PROBLEM 5 — CRITICAL THINKING

Suppose you need to frequently check whether two specific users are friends in a social network with 10,000 users, where each user has about 150 friends on average. Would you use a dict of lists or a dict of sets for the adjacency list? Now suppose the graph is dense — each user is friends with 8,000 of the 10,000 users. Would your answer change to an adjacency matrix instead? Justify both answers in terms of time and space complexity.

SUMMARY

Lesson Summary

A graph is a data structure made of vertices (nodes) connected by edges. The most practical way to represent a graph in Python is with an adjacency list — a dictionary where each key is a node and each value is a list or set of that node's neighbors. For undirected graphs, each edge is stored in both endpoints' lists. For directed graphs, each edge is stored only in the source node's list.

The adjacency list uses O(V + E) space, making it far more memory-efficient than an adjacency matrix for sparse graphs. Using a dict of sets gives O(1) edge-existence checks and prevents duplicate edges, while a dict of lists preserves insertion order and allows parallel edges. This foundational representation is the starting point for powerful algorithms like BFS, DFS, and Dijkstra's algorithm.