Python graph representations and BFS

Why it matters

Maps, friend networks, web links, bus routes and course prerequisites are all graphs. Many interview problems that do not look like graphs are graphs in disguise: a grid of cells is a graph where each cell touches its four neighbours, and a word ladder is a graph where two words are joined when they differ by one letter. Once you can store a graph and walk through it, a large group of problems becomes the same problem wearing different clothes.

This lesson builds the foundation for the rest of the module. You will learn the vocabulary, two ways to store a graph in Python, and breadth-first search (BFS), the walk that finds the fewest hops from one place to every other place.

Start with a map

Picture a small country with towns and roads. Each town is a dot on the map. Each road is a line between two dots. In graph language, the dots are vertices (also called nodes) and the lines are edges. A graph is just a set of vertices and the edges between them.

A few words will come up again and again, so define them now:

• Neighbour: a vertex joined to another by one edge. If there is a road from Ashby to Brook, Brook is a neighbour of Ashby.
• Degree: the number of edges touching a vertex. A town with four roads has degree 4.
• Undirected: every edge works both ways. A two-way road is undirected. The edge 0 1 means you can go from 0 to 1 and from 1 to 0.
• Directed: every edge has a direction, like a one-way street. The edge 0 1 lets you go from 0 to 1 only.
• Weighted: every edge carries a number, such as a distance, a time or a cost. Lesson 4 of this module uses weights. This lesson does not.
• Path: a list of vertices where each vertex is joined to the next one by an edge. The number of edges in the path is its length, measured in hops.
• Connected: an undirected graph is connected when every vertex can reach every other vertex.

Here is a small undirected graph with five vertices and five edges. We will use it all the way through this lesson.

    0 ---- 1
    |      |
    2 ---- 3 ---- 4

Vertex 0 has two neighbours, 1 and 2, so its degree is 2. Vertex 3 has three neighbours, 1, 2 and 4, so its degree is 3. Vertex 3 is the busiest junction in this little map.

Vertices are numbered from 0 to n - 1, where n is the number of vertices. Numbering from 0 matches Python lists, which also start at index 0, so you can use a vertex number directly as a list index. Most graph problems you will meet on a judge or in an interview use this numbering. If a problem numbers its vertices from 1, subtract 1 when you read them.

The vocabulary in one table

Keep the word hop in mind. In this lesson, the shortest path means the path with the fewest hops, not the shortest physical distance. Lesson 4 changes that when the edges carry weights.

Two ways to store a graph

A computer cannot look at a picture of a graph. It needs the graph stored in memory as numbers. There are two common ways to do that. Both store the same graph, but they spend memory and time differently.

The adjacency list

An adjacency list gives every vertex its own list of neighbours. To find the roads out of town 3, you look at the list stored for 3 and read it. Nothing else.

In Python, the natural way to write this is a list of lists. The outer list has one slot per vertex. Each slot holds an inner list of neighbour numbers. Python does not need a wrapper type for numbers, because every number is already an object, so a list can hold plain ints. A type hint such as list[list[int]] tells a reader and tools what the value should hold. Python does not check type hints while the program runs.

Here is the adjacency list for the graph above, written out by hand:

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]

Each undirected edge appears twice: the edge 0-1 is listed under 0 and again under 1. This is the price of the undirected format. It is cheap in memory, and the list for each vertex contains exactly its neighbours.

The adjacency matrix

An adjacency matrix is a table with one row and one column per vertex. The cell at row i and column j holds 1 if there is an edge from i to j, and 0 if there is not. For an undirected graph the table is symmetric: the cell at i and j matches the cell at j and i.

Here is the matrix for the same graph. Read row 3 to see the links from vertex 3: it has 1s in columns 1, 2 and 4.

    0  1  2  3  4
0 [ 0  1  1  0  0 ]
1 [ 1  0  0  1  0 ]
2 [ 1  0  0  1  0 ]
3 [ 0  1  1  0  1 ]
4 [ 0  0  0  1  0 ]

In Python, the matrix is a list of lists of ints. Checking whether an edge exists is one lookup: matrix[1][3] == 1.

Comparing the two

The right choice depends on how many edges the graph has compared with the number of possible edges. A graph with few edges is sparse. A graph where most pairs of vertices are joined is dense.

Here V is the number of vertices and E is the number of edges. The notation O(...) is called Big O. It describes how the work grows as the input grows, and it ignores constant factors. The complexity section below explains where the BFS cost comes from.

Consider a city with 100,000 intersections and 300,000 roads. The list needs about 600,000 entries, since each road is stored twice. The matrix needs 100,000 times 100,000, which is 10 billion cells. A Python list stores one pointer per cell, and a pointer is 8 bytes on a 64-bit build, so the matrix alone needs about 80 gigabytes. That is far more than a normal computer has. This is why real systems almost always use adjacency lists. Use a matrix only when the graph is small or dense, or when the problem asks you many questions of the form "is there an edge between these two?"

What happens in memory

It helps to see where the data lives, because it explains the speed differences. A Python list does not store its items one after another as raw numbers. It stores a row of references, which are pointers to objects somewhere else in memory. The outer list of a matrix holds a reference to one inner list per row, and each inner list holds references to int objects.

Reading matrix[1][3] means: find the reference to row 1, then find the reference in position 3 of that row. Both steps jump straight to the right slot, so the cost does not depend on the graph's size.

Each Python int is a full object, not just four bytes of storage. On the machine used to test these samples, with Python 3.14, sys.getsizeof(1) returned 28 bytes. Other builds can return a different number. CPython, the standard Python implementation, keeps one shared object for small numbers such as 0 and 1, so a matrix full of 0s and 1s points at only two int objects. The memory used by the references themselves is still one pointer per cell. On the same machine, a 2,000 by 2,000 matrix of lists took about 32 MB.

An adjacency list is a list of lists too. The total size grows with the number of edges, so a large sparse graph still fits.

Building the list in Python

Building the list is a pattern you will write many times, so here is the pattern once in isolation:

n = 5
adj = [[] for _ in range(n)]
adj[0].append(1)  # edge 0 to 1 in the list of 0
adj[1].append(0)  # and the reverse, because the edge is undirected

The list comprehension [[] for _ in range(n)] creates one new empty list for each vertex. The underscore _ is a name for a value you do not use. Each inner list is separate, so adj[0] and adj[1] do not share anything. The two append calls at the bottom are the undirected pattern: one for each direction.

Do not write [[]] * n. It looks shorter, but it puts the same inner list into every slot, so adding to one adds to all of them. The mistakes section below shows the output.

Program 1: build and print the adjacency list

The programs in this lesson put the graph in the code, in a constant called EDGES. They do not read an Input box, so each one runs as it is. To try a different graph, change N and EDGES.

Expected output:

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]

Walk through the program once in your head. The constant EDGES holds five pairs. Each pair is a tuple, which is a fixed group of values written in round brackets. The function creates one empty list per vertex first. Then it reads each pair with for u, v in edges and adds the edge in both directions. The last loop prints each list. The neighbours appear in the order the edges were listed, so the list for 3 reads [1, 2, 4], because the edges 1 3, 2 3 and 3 4 came in that order.

The f"..." text is an f-string. Anything inside braces is replaced by its value, so {adj[v]} prints the list as [1, 3] and so on.

Program 2: the same graph as a matrix

The same edges can build a matrix. The matrix version is shorter to write, but it needs n times n cells even when there are only a few edges.

Expected output:

[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]
edge 1-3: True
edge 1-4: False

Each line of the matrix matches the table in the earlier section. The line [[0] * N for _ in range(N)] builds N separate rows, each with N zeros. Unlike the [[]] * n trap, this one is safe, because the comprehension makes a new row each time.

Each edge sets two cells, one for each direction, because the graph is undirected. For a directed graph you would set only matrix[u][v] = 1. The Python True and False are the boolean values, printed with a capital letter.

Notice how the question "is there an edge 1-3?" is answered with one lookup. With a list, you would scan the neighbours of 1. For five vertices the difference does not matter. For a million vertices with a few neighbours each, the list is the faster and much smaller choice.

Breadth-first search

Now the walk. A search on a graph visits vertices one at a time, so that you can find something or count something. There are two standard walks: breadth-first search (BFS) and depth-first search (DFS). This lesson covers BFS. Lesson 2 covers DFS.

BFS is like a ripple on a pond. A stone drops at the start vertex. The ripple first reaches the start's neighbours, then the neighbours of those, and so on. Every vertex that is one hop away is visited before any vertex that is two hops away. The walk expands in rings of equal distance.

The walk needs a queue, a line where the first item to join is the first item to leave. Python gives you a fast queue in collections.deque. The name is short for double-ended queue, and it is pronounced "deck". A deque adds and removes items at both ends quickly. Calling append puts an item at the back of the line. Calling popleft removes and returns the item at the front.

A plain list also has append, but list.pop(0) removes the front item by shifting every other item one place left. On a long queue that gets slow, so use a deque for queues. If you know Java, deque plays the role of ArrayDeque.

The steps are:

1. Mark the start vertex as seen and put it in the queue.
2. Take the vertex at the front of the queue. Call it u.
3. For each neighbour v of u, if v has not been seen, mark it as seen, record its distance as one more than u, and add it to the back of the queue.
4. Repeat from step 2 until the queue is empty.

Two details matter. First, you mark a vertex as seen when you add it to the queue, not when you take it out. If you wait, two different vertices can each add the same neighbour before it is taken out, and it gets queued twice. Second, the seen marks stop the walk from going in circles. Without them, an undirected edge would send the walk back and forth forever.

The queue explains why BFS gives shortest paths. Vertices enter the queue in order of their distance. Start with distance 0. All distance-1 vertices enter before any distance-2 vertex, because they were added while distance-0 vertices were being processed. So the first time BFS reaches a vertex, it has used the fewest hops possible. Nothing can beat it, because any shorter route would have reached the vertex earlier.

The stepping animation below runs BFS on a small graph. Step through it, and watch two things: which vertex leaves the front of the queue, and which neighbours join the back of the queue at each step. Notice that every vertex in the queue has a distance equal to or one more than the vertex ahead of it. That pattern is what keeps the rings in order.

Here is the same walk on our graph, traced by hand. Start at vertex 0.

The visit order is 0, 1, 2, 3, 4. The distances are 0 for vertex 0, 1 for vertices 1 and 2, 2 for vertex 3 and 3 for vertex 4. Think of the table as the rings: distance 0 is vertex 0, distance 1 is vertices 1 and 2, distance 2 is vertex 3, and distance 3 is vertex 4.

Program 3: BFS distances and visit order

Here is the BFS walk as a complete program. It prints the order in which vertices left the queue, and the distance from vertex 0 to every vertex.

Expected output:

visit order: [0, 1, 2, 3, 4]
distance: [0, 1, 1, 2, 3]

Look at the line dist = [-1] * len(adj). The value -1 means "not seen yet". Distances are never negative, so -1 can never be confused with a real distance. This is a common trick: use a value that cannot be a real answer as the marker. Python also has None for "no value", which many programmers prefer. The -1 marker is used here because it matches the usual graph code you will read in other sources. The check dist[v] == -1 does two jobs at once. It asks "have I seen v?" and, when false, it records the distance in the same step.

The line while queue: is the check for an empty queue. A deque with items is true in a condition, and an empty one is false. The loop never calls popleft on an empty deque, which would raise an error. The mistakes section shows that error.

The order line shows that vertex 3 is visited after both 1 and 2. Both are at distance 1, so both enter the queue before 3, which is at distance 2. Vertex 4 comes last at distance 3.

Tracing the queue step by step

Each step of the program's loop does exactly one thing, so the trace is short. Here is what the program does on the first three pops, written out in full. This is how to check a BFS you are unsure about: write down the queue after each pop.

• The queue starts as deque([0]) and dist[0] is 0.
• Pop 0. Its list is [1, 2]. Vertex 1 has dist -1, so set dist[1] to 1 and add 1. Vertex 2 likewise: dist[2] becomes 1 and 2 is added. The queue is [1, 2]. The visit order so far is 0.
• Pop 1. Its list is [0, 3]. Vertex 0 has a distance already, so skip it. Vertex 3 has dist -1, so set dist[3] to 2 and add 3. The queue is [2, 3]. The visit order is 0 1.
• Pop 2. Its list is [0, 3]. Both are already set, so nothing is added. The queue is [3]. The visit order is 0 1 2.

Three pops in, the program has already fixed the distance of four vertices. Notice that vertex 3 got distance 2 through vertex 1, not through vertex 2. Both routes have the same length, so the first one to reach it wins. When two shortest paths exist, BFS returns one of them, and which one depends on the order of the neighbour lists. A problem that asks for "any shortest path" accepts either.

Recovering the path, not just the distance

Often you need the route itself, not only the number of hops. The standard trick is a parent array. When BFS first reaches a vertex v from a vertex u, store parent[v] = u. Once BFS finishes, start at the goal and follow parents back to the start. Then reverse the list.

Program 4 does this. It finds the shortest path from vertex 0 to vertex 4. The function returns None when no path exists. None is Python's word for "no value", and the type hint list[int] | None says the function returns either a list or None.

Expected output:

path: [0, 1, 3, 4]
steps: 3

The walk back is the part to study. The loop starts at goal, adds it to the list, then moves to parent[goal], and so on. The start has parent -1 because nothing was set for it, so the loop stops there. The list is built from the goal backwards, so path.reverse() flips it into the order you walk: start first, goal last. The method changes the list in place and returns nothing. Writing path = path[::-1] also reverses the list, and it makes a new one. The [::-1] form is called slicing with a step of -1.

The number of steps is the number of edges, which is one less than the number of vertices on the path. The path 0, 1, 3, 4 has four vertices and three edges, so the answer is 3.

Two edge cases are worth checking. If the start and the goal are the same vertex, the path is just that vertex and the steps are 0. If the goal is in a different connected group, seen[goal] stays false and the function returns None. Run these two calls to see both branches:

print(shortest_path(adj, 0, 0))
g2 = build_adjacency_list(5, [(0, 1), (0, 2), (1, 3), (2, 3)])
print(shortest_path(g2, 0, 4))

Expected output, with adj and shortest_path from Program 4 above it:

[0]
None

The second graph has no edge 3-4, so vertex 4 has no neighbours and cannot be reached.

The parent array is the key to most graph problems that ask "how" and not only "how many". You will meet it again in the Dijkstra lesson, where the same idea recovers the cheapest route.

Grids are graphs

Many problems give you a grid instead of a list of edges. A map of a building, a chessboard, a game board or a maze is a grid. You do not need a separate algorithm for grids. Each cell is a vertex, and its neighbours are the cells directly above, below, to the left and to the right, as long as they are inside the grid and are not walls.

With this view, the maze problem becomes plain BFS. The start cell is the start vertex, the exit is the goal, and walls are simply vertices you never add. Program 5 does exactly that. It holds a maze of . (open), # (wall), S (start) and E (exit), and prints the fewest moves. The maze is a list of strings, one string per row.

Expected output:

shortest: 5

The new idea here is the list MOVES. It holds the row and column change for the four moves. The first pair (1, 0) is down, meaning row plus 1. The second (-1, 0) is up, the third (0, 1) is right and the last (0, -1) is left. The loop for dr, dc in MOVES visits each of the four neighbours in turn. Instead of writing four nearly identical blocks, you write one block and change the offsets.

The queue holds tuples such as (1, 2), which is row 1 and column 2. A cell is identified by its row and column together, so the queue stores both as one tuple. This is the same BFS as before, with the grid's geometry supplying the neighbours.

The check 0 <= nr < rows is a chained comparison. It means 0 <= nr and nr < rows, both at once. It is the bounds check: the new row must be inside the grid. It is the most common source of bugs in grid code, and Python needs it more than most languages, as the mistakes section explains. Check every bound before you read from the grid.

The program stops at the first time it pops the exit cell. Because BFS pops cells in order of distance, that first pop gives the shortest distance. The answer is 5 because the exit is 2 rows down and 3 columns across, and no route can do that in fewer moves. To try your own maze, edit MAZE. Every row must have the same length.

Complexity: why BFS costs what it costs

A complexity claim should be checked, not memorised. Here is the reasoning for BFS on an adjacency list.

Each vertex enters the queue at most once, because it is marked as seen when it is added. So the loop while queue: runs at most V times. Inside the loop, the program scans the neighbour list of the vertex it just took out. Across the whole run, each vertex's list is scanned exactly once. Each undirected edge appears in two lists, so the total number of list entries scanned is 2E. Adding the V pops and the 2E scans gives O(V + E) time.

The memory has three parts: the adjacency list itself (O(V + E)), the dist list (O(V)) and the queue, which holds at most V vertices at once (O(V)). The total is O(V + E).

The queue choice affects the time too. deque.popleft takes the same short time no matter how long the queue is. list.pop(0) must shift every remaining item, so its cost grows with the queue length. Using it inside BFS can push the total time toward O(V^2) on a large graph. This is why the code uses a deque.

For the grid, V is the number of cells, which is rows times columns. Each cell has at most four neighbours, so the neighbour checks total at most 4 times V. The grid BFS therefore runs in O(R * C) time, which is one visit per cell. A 500 by 500 maze has 250,000 cells, and the BFS handles it easily.

Common mistakes and the messages they produce

Graph code fails in a few predictable ways. Each one prints a message, and learning to read the message saves time. The messages below are the real ones from Python 3.14. The file paths in them are shortened to ... here, and your path will differ.

Mistake 1: vertex numbers outside the range. Suppose the edge list contains (0, 5), but there are only five vertices, numbered 0 to 4. Vertex 5 does not exist. The program fails when it reaches the list:

Traceback (most recent call last):
  File ".../bad_edge.py", line 13, in <module>
    adj = build_adjacency_list(N, EDGES)
  File ".../bad_edge.py", line 9, in build_adjacency_list
    adj[v].append(u)
    ~~~^^^
IndexError: list index out of range

Read the last line first. IndexError names the kind of problem, and list index out of range says the index was too big for the list. The lines above it show the path through the code, and the last of them names the line that failed. The small ~~~^^^ marks under the code point at the index that failed. The fix is to check the input. Often the problem numbers its vertices from 1, and you forgot to subtract 1.

Mistake 2: popping an empty queue. This is the BFS crash. If you remove the while queue: check, the loop eventually calls popleft on an empty deque:

Traceback (most recent call last):
  File ".../empty.py", line 3, in <module>
    queue.popleft()
    ~~~~~~~~~~~~~^^
IndexError: pop from an empty deque

The message says exactly what happened. The cure is the while queue: loop, which you should never remove.

Mistake 3: [[]] * n shares one list. This one does not raise an error, which makes it harder to find:

adj = [[]] * 5
adj[0].append(1)
print(adj)

Expected output:

[[1], [1], [1], [1], [1]]

The line adj[0].append(1) added 1 to the one list that all five slots point to. The fix is the list comprehension [[] for _ in range(5)], which builds five separate lists.

Mistake 4: marking seen when you pop. Here is the wrong version of the inner loop:

u = queue.popleft()
if seen[u]:
    continue
seen[u] = True
for v in adj[u]:
    queue.append(v)

This does not crash. It is just slower, because the same vertex can enter the queue many times. Run both versions on the five-vertex graph and count the pushes. The wrong version pushes 11 items for 5 vertices, because each vertex is pushed once for every edge into it, plus the start. The correct version, which marks each vertex the moment it is added, pushes 5 items.

Mistake 5: forgetting the reverse edge. In an undirected graph, the edge u v must be stored twice: once as adj[u] gets v, and once as adj[v] gets u. If you store only one, the walk can reach v from u but never go from v back to u. Storing only adj[0].append(1) gives this result:

adj = [[] for _ in range(3)]
adj[0].append(1)
print(adj)

Expected output:

[[1], [], []]

Vertex 1 has an empty list, so BFS from 1 never reaches 0. Check the add calls in pairs.

Mistake 6: a negative index does not crash in Python. Many languages raise an error for index -1. Python does not. A negative index counts from the end of the list. Run this:

row = [10, 20, 30]
print("row[-1] =", row[-1])
c = 0
print("neighbour at column c - 1 =", row[c - 1])

Expected output:

row[-1] = 30
neighbour at column c - 1 = 30

On the first column, c - 1 is -1, so the code reads the last column instead of stopping. The program keeps running and gives a wrong answer with no message. The inside check in the maze program is what stops this. Keep it, and check every bound before you use an index.

Mistake 7: the seen test flipped. If the check reads dist[v] != -1 where it should read dist[v] == -1, the walk never adds anything, because it skips every unvisited vertex and only follows visited ones. Flipping one symbol turns a working search into one that stops after the start.

Debugging walkthrough

Suppose you wrote a BFS that prints -1 for every goal, even ones you can see are reachable. Here is how to find the cause without guessing.

First, check the input. Print the adjacency list, as in Program 1, and compare it with the edges you meant. If the lists are short or wrong, the bug is in the building, not in BFS.

Second, check the start. Is dist[start] set to 0 and is the start added to the queue? A common slip is to set the distance but forget queue.append, so the queue is empty from the beginning and nothing is visited.

Third, print the queue. Put a print at the top of the loop and run again on a tiny input:

from collections import deque
 
adj = [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
dist = [-1] * 5
dist[0] = 0
queue = deque([0])
while queue:
    print("queue before pop", queue)
    u = queue.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            queue.append(v)
print("dist", dist)

Expected output:

queue before pop deque([0])
queue before pop deque([1, 2])
queue before pop deque([2, 3])
queue before pop deque([3])
queue before pop deque([4])
dist [0, 1, 1, 2, 3]

This is the same trace you did by hand earlier, produced by the program. It shows each pop and what is waiting behind it. Remove the print when you are done.

Fourth, check the seen test. Work through these four checks in order, and most graph bugs show up within a few minutes. The order matters: input, start, queue, the seen test.

Variations and edge cases

BFS adapts to many problems with small changes.

Multi-source BFS. Sometimes many starting points exist at once, such as every rotten orange in a crate, or every fire in a forest. Set the distance to 0 for every source and put all of them in the queue with deque(sources) before the loop starts. The rings then grow from every source together, and the first time a cell is reached gives the distance to its nearest source. Exercise 10 uses this.

Level-by-level BFS. Sometimes you need the rings themselves, for example to count how many people are at each distance from a town. Store len(queue) at the start of each round, and process exactly that many vertices before counting the next round. Each round is one ring.

Directed graphs. BFS works without change on a directed graph. Store only adj[u].append(v) for an edge from u to v. The walk follows arrows and cannot go backwards along them.

Disconnected graphs. BFS from one start only reaches its own connected group. If the problem asks about every vertex, loop over all vertices and start a BFS from each one that is not yet seen. Lesson 2 covers this loop for components.

Edge cases to test. Try a start equal to the goal (answer 0), a goal in another group (answer None or -1, depending on how the function reports it), a graph with a single vertex and no edges, a graph with a self-loop (an edge from a vertex to itself, which the seen check handles), and a graph with two parallel edges between the same pair (duplicates do no harm to BFS, but they inflate degree counts).

Interview questions this lesson answers

Interviewers often ask these, and the answers are the lesson in short form.

"How do you find the shortest path in an unweighted graph?" Use BFS from the start. The first time you reach the goal, its distance is the shortest. Store parents to recover the path.

"Why does BFS find shortest paths when DFS does not?" BFS expands in rings, so it reaches each vertex by the fewest hops first. DFS follows one route to its end before trying others, so its first arrival at a vertex may be by a long route.

"What is the complexity of BFS?" O(V + E) time and O(V) extra space, for an adjacency list. You can justify it in one sentence: each vertex is queued once and each edge is scanned once or twice.

"A graph has a million vertices. Which representation do you pick?" The adjacency list, unless the graph is dense. A matrix needs a trillion cells, which does not fit in memory.

"How would you solve the word ladder problem?" Treat each word as a vertex and join two words when they differ in exactly one letter. Then BFS from the start word to the target word gives the fewest changes. The graph is never built in full. Neighbours are generated on demand by trying each letter position.

Real-world uses

BFS shows up in more places than you might expect. A social app that suggests "people you may know" looks at friends of friends, which is a ring of distance 2 around you. A network tool that finds the fewest routers between two machines runs BFS over the connection graph. A game AI that moves a character toward the player, when every move costs the same, uses BFS on the grid of tiles. A crawler that visits web pages level by level uses a queue of URLs, which is BFS in disguise.

Practice

Exercise 1 (easy). Write the adjacency list for the undirected edges 0-1, 1-2 and 2-0. Hint: every vertex in a triangle has exactly two neighbours.

Show the answer

0: [1, 2]
1: [0, 2]
2: [1, 0]

The neighbours appear in the order the edges were listed. Vertex 2 gets 1 from the edge 1-2 and 0 from the edge 2-0.

Exercise 2 (easy). How many cells does an adjacency matrix need for 2,000 vertices? Give the number and say why it is too many for many graphs.

Show the answer

The matrix has 2,000 rows and 2,000 columns, so 4,000,000 cells. In Python each cell is a pointer of 8 bytes on a 64-bit build, so the pointers alone take about 32 MB. That is fine for one graph, but the cost grows with the square of the vertex count. A graph with 200,000 vertices needs 40 billion cells, which is far too much.

Exercise 3 (easy). In the five-vertex example, run BFS by hand from vertex 3. Write the visit order and the distance to every vertex. Hint: vertex 3 has neighbours 1, 2 and 4 in that list order.

Show the answer

Visit order: 3, 1, 2, 4, 0. Distances: vertex 0 is 2, vertex 1 is 1, vertex 2 is 1, vertex 3 is 0, vertex 4 is 1. Vertex 0 is reached from 1 (first in the queue), so its distance is 1 plus the distance of 1, which is 2.

Exercise 4 (medium). Explain in your own words why marking a vertex as seen when it is added to the queue is correct, and what goes wrong if you wait until it is removed.

Show the answer

Marking on add means a vertex enters the queue exactly once, so the queue never holds more than V vertices. Marking on removal lets several vertices add the same neighbour before any of them is removed. That neighbour then sits in the queue several times, wasting work, and on large graphs the queue can grow far beyond V.

Exercise 5 (medium). Change Program 3 so it prints the number of vertices at each distance, for example level 0: 1, level 1: 2. Hint: after the BFS, find the largest distance, then count how many entries have each value.

Show the answer

Add these lines to the end of Program 3:

max_dist = max(dist)
for level in range(max_dist + 1):
    print(f"level {level}: {dist.count(level)}")

The output after the two lines from Program 3 is:

level 0: 1
level 1: 2
level 2: 1
level 3: 1

The method dist.count(level) counts how many entries in dist equal level.

Exercise 6 (medium). Modify Program 4 so that it prints unreachable when the goal is not reachable, and check it with an input where vertex 4 is in its own group (remove the edge (3, 4) from EDGES).

Show the answer

Remove (3, 4) from EDGES, and change the message in the if path is None block from no path to unreachable. Then vertex 4 has no neighbours, seen[4] stays false, and the function returns None, so the message unreachable is printed.

Exercise 7 (medium). A directed graph has the edges 0 to 1, 1 to 2 and 2 to 0. Is it possible to go from 0 to 2? Explain your answer using the edges, and say what changes if you store the edges as undirected.

Show the answer

Yes. From 0 you can go to 1 along 0 to 1, and from 1 to 2 along 1 to 2. Storing the edges as undirected would not change that answer. It would change the other direction: in the directed graph you cannot go from 1 back to 0, because only the edge 0 to 1 exists. An undirected version would let you walk from 1 to 0 as well.

Exercise 8 (medium). On a 3 by 3 grid with no walls, how many cells are at distance 2 from the top-left corner? List them.

Show the answer

Three cells: row 0 column 2, row 1 column 1 and row 2 column 0. Each one is two moves away (right twice, down then right, or down twice). The corner itself is at distance 0, and the other cells are at distance 1, 3 or 4.

Exercise 9 (hard). Explain why BFS on an unweighted graph finds a shortest path, using the queue. Your explanation must say why the distances in the queue never decrease as you move toward its back.

Show the answer

Every vertex added to the queue has a distance equal to the distance of the vertex that was popped to add it, plus one. The queue starts with the start at distance 0. When a vertex at distance d is popped, it adds vertices at distance d plus 1 to the back. Because the queue is first in, first out, the vertices at distance d are all popped before any at distance d plus 1. So the distances in the queue are never out of order: the front holds the smallest remaining distance, and the back holds at most one more than the front. Therefore the first time a vertex is added, it is added with its smallest possible distance.

Exercise 10 (hard). Write a multi-source BFS that starts from every cell marked R in a grid, where each move spreads one step to an open cell ., and prints the number of minutes until every open cell is reached, or -1 if some cell is unreachable. Hint: put every R in the queue before the loop starts.

Show the answer

Expected output:

minutes: 4

Every R goes into the queue with distance 0, then the usual loop spreads over open cells. The blocked cell # is never entered. After the loop, if any open cell still has distance -1, the answer is -1. Otherwise the answer is the largest distance. The cell at row 2, column 2 is the farthest open cell, at distance 4.

What you now know

• A graph is vertices and edges. Undirected edges work both ways, directed edges work one way, and weights put a number on each edge.
• An adjacency list stores neighbours per vertex and costs O(V + E) space. An adjacency matrix costs O(V^2) and gives one-step edge checks.
• In Python, build adjacency lists with [[] for _ in range(n)], never with [[]] * n.
• BFS uses a deque, marks vertices when it adds them, and finds the fewest hops from a start.
• A parent list recovers the path after BFS.
• A grid is a graph: each cell has up to four neighbours. Python's negative indexes do not raise errors, so the bounds check matters more here than in some other languages.
• BFS runs in O(V + E) time and O(V) space on an adjacency list.