Adjacency list

Each vertex stores its neighbours in a list.

Adjacency list

An adjacency list stores each node's neighbors in a list. graph = {'A': ['B', 'C'], 'B': ['A']}.

Memory is O(V + E): each node and edge stored once. Efficient for sparse graphs.

Implemented in Python with a dict + list. Adding a node is O(1), adding an edge is O(1).

Add edge function

When adding an edge, if either node is not in the graph it is first added with an empty list. Then each node is added as a neighbor of the other (in an undirected graph).

add_edge(graph, a, b): graph.setdefault(a, []).append(b) and graph.setdefault(b, []).append(a). Both sides get an append.

In a directed graph only one direction is added; that is, only one side gets an append, the other is skipped.

Exercise Add edge

Write add_edge(graph, a, b). Undirected: add to both. Print {'a': ['b'], 'b': ['a']} with g = create_graph(); add_edge(g, 'a', 'b'); print(g).

Show example solution

def create_graph():
    return {}
def add_edge(graph, a, b):
    # Add undirected edge
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
g = create_graph()
add_edge(g, 'a', 'b')
print(g)

Test yourself

Add edge
```
graph[a].append(____)
```
Show answer
```
graph[a].append(b)
```
Adjacency list: match the terms

Adjacency list

O(V+E)
Add edge

O(1)
Sparse graph

Efficient
Undirected

Both ways
What is the adjacency list memory?
- O(V^2)
- O(E)
- O(V + E)
- O(V)
Show answer

O(V + E) — O(V + E)

Next lesson: Adjacency matrix

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies