CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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).

Starter code

solution.py
def add_edge(graph, a, b):
    # Add undirected edge

Sample solution

solution.py
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)

Expected output

{'a': ['b'], 'b': ['a']}

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Add edge

Question 
graph[a].append(____)
Answer 
graph[a].append(b)

Explanation: b is right.

2 Adjacency list: match the terms

Term Meaning
Adjacency list O(V+E)
Add edge O(1)
Sparse graph Efficient
Undirected Both ways

3 What is the adjacency list memory?

  • O(V^2)
  • O(E)
  • O(V + E) Correct answer
  • O(V)

Explanation: O(V + E)

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4