Why it matters
"How many separate groups are there?" and "does this graph have a loop?" are two of the most common questions in graph interviews. In real systems they show up as "which accounts belong to the same person?" and "does this build depend on itself?". Both questions are answered with depth-first search. This lesson teaches that search, shows the two ways to write it in Python, and then uses it to solve the two questions.
Lesson 1 used breadth-first search, which spreads in rings. Depth-first search does something different, and the difference decides which problems each one solves well.
Depth first: following one corridor to its end
Picture yourself in a hedge maze. You want to see every corner of it. You pick a corridor and follow it. At each junction you take the first unexplored branch and keep going. When you reach a dead end, you walk back to the last junction where you still had a choice, and try the next branch. You repeat this until every corridor is explored.
That is depth-first search (DFS). Where breadth-first search checks every neighbour before going further, DFS goes as deep as it can along one path before it looks at any other path. The word depth means distance from the start along the path you are currently following.
The walk keeps track of two things. The first is a seen list, with one True or False entry per vertex, which records which vertices you have already visited. The second is the path you are currently on. You do not store that path in a separate list. Python keeps it for you, in the form of the call stack, which we explain in a moment.
A DFS on an adjacency list runs in O(V + E) time. Like BFS, each vertex is entered once and each edge is scanned once or twice. The memory is O(V): the seen list plus the call stack, which can hold up to V frames when the walk is a long chain.
Adjacency lists in Python
A graph with n vertices is stored as a list of n lists. The list at index u holds the neighbours of vertex u. Here is how to build one:
n = 3
adj = [[] for _ in range(n)]
adj[0].append(1)
adj[1].append(0)
print(adj)The output is:
[[1], [0], []]The line [[] for _ in range(n)] builds n separate empty lists. A list comprehension is a short loop inside square brackets that makes a new list for each step. Writing [[]] * n looks shorter, but it makes n references to one single list. Every vertex would then share the same neighbours. Mistake 6 below shows what that does.
The recursive version
The simplest DFS is a function that calls itself. It is a direct copy of the maze rule: mark where you are, then try each unexplored neighbour by walking into it.
def dfs(adj, seen, u):
seen[u] = True
for v in adj[u]:
if not seen[v]:
dfs(adj, seen, v)Read the function slowly. seen[u] = True is the first line, so the vertex is marked before anything else happens. The loop looks at each neighbour. If a neighbour is unseen, the function calls itself on it. The call does not return until that neighbour's whole part of the graph has been explored. Only then does the loop continue with the next neighbour of u. This is the backtracking: after the recursive call returns, you are back at u, ready to try the next branch.
Recursion is a function calling itself on a smaller or different input. Each call gets its own copy of its local variables, here u and the loop position. The copies live on the call stack, and this is where the memory of the walk sits.
The function receives the graph and the seen list as arguments. A list passed to a function is not copied. The function gets a reference to the same list. When the function sets seen[v] = True, the caller sees that change too. This is how every call in the walk shares one seen list.
What happens inside: the call stack
The call stack is the place where Python keeps one frame for each active function call. A frame holds that call's arguments and local variables. When a function calls another function, a new frame is pushed on top. When the inner function returns, its frame is removed and the caller carries on from where it stopped.
Take the graph from Program 1 below, and start at vertex 0. Each line shows the call stack at one moment, from the oldest call on the left to the newest on the right:
dfs(0)
dfs(0), dfs(1)
dfs(0), dfs(1), dfs(3)
dfs(0), dfs(1), dfs(3), dfs(5)
dfs(0), dfs(1), dfs(3), dfs(5), dfs(4)
dfs(0), dfs(1), dfs(3), dfs(5), dfs(4), dfs(2)At the start, dfs(0) is the only frame. It visits neighbour 1, so dfs(1) is pushed on top. From 1 it goes to 3, pushing dfs(3). From 3 it goes to 5, pushing dfs(5). At 5, the neighbour 3 is already seen and the neighbour 4 is not, so dfs(4) is pushed. Vertex 4 then reaches 2, and that makes the deepest point: six frames. When 2 has no unseen neighbours, its frame is removed, and so on back down. The order in which vertices were marked is the order DFS visited them.
The recursion limit
Python limits how deep the call stack may grow. The limit is stored in the sys module. Read it with sys.getrecursionlimit(). In the Python 3.14 install used to check this lesson, it returns 1000. A walk along a chain of 5000 vertices needs 5000 frames, which is far past that limit:
import sys
def walk(adj, seen, u):
seen[u] = True
for v in adj[u]:
if not seen[v]:
walk(adj, seen, v)
print("limit:", sys.getrecursionlimit())
n = 5000
adj = [[] for _ in range(n)]
for i in range(n - 1):
adj[i].append(i + 1)
adj[i + 1].append(i)
seen = [False] * n
walk(adj, seen, 0)
print("done")Output (the file path and the file name in the first lines depend on where the file is saved, so they are shortened here):
limit: 1000
Traceback (most recent call last):
File "...", line 18, in <module>
walk(adj, seen, 0)
...
File "...", line 8, in walk
walk(adj, seen, v)
~~~~^^^^^^^^^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededPython stops the program with RecursionError. Java has the same idea under the name StackOverflowError. The line [Previous line repeated 996 more times] tells you that the same line of code ran again and again, which is the cue that the recursion has no end or goes too deep. The number of repeats can differ on another machine.
sys.setrecursionlimit() can raise the limit, but a very high value can crash Python itself when the underlying machine stack runs out. For a deep graph, the better fix is the explicit stack shown in the next section. A list lives in heap memory (the pool of memory a program uses for its data, which grows as needed) and grows with the data, so it does not hit this limit.
Program 1: recursive DFS
Here is the complete recursive walk. It reads a graph from the Input box and prints the order in which vertices are first visited, starting at vertex 0. The graph has six vertices and six undirected edges. It has two branches out of 0 that join again at 5.
The first lines read the numbers from the Input box. sys.stdin.read() returns all the text, split() cuts it into words, and map(int, ...) turns each word into a number. The variable nums is an iterator: each next(nums) returns the next number.
Type this into the Input box:
6 6
0 1
0 2
1 3
2 4
3 5
4 5Expected output:
order: 0 1 3 5 4 2Compare this with the breadth-first order from lesson 1 for the same graph, which was 0 1 2 3 4 5. BFS took all of distance 1 before any of distance 2. DFS took the first neighbour of 0, namely 1, and followed it as far as possible: 1, then 3, then 5. Only when 5 led nowhere new did it try 4, and from 4 it reached 2. Vertex 2 is also a neighbour of 0, but DFS reached it later, by the road from 4.
This version passes order as an argument, so it does not need any global variable. Python has global variables, but a function that depends on them is harder to test. Passing the data in makes each call easy to read.
A filled node is the one being handled. An outlined node is in the stack. A dark border means visited. The thick dashed edge is the one being looked at. Neighbours are tried in alphabetical order.
Start at A. Go as deep as possible before backing up.
Step through the animation above and watch the walk go down a branch until it cannot go further. Then watch it come back up. The moment it returns to a vertex is the moment it tries the next neighbour in that vertex's list. The order of the list decides the order of the walk, so the same graph can give different orders depending on how the edges were typed.
Program 2: the same walk with an explicit stack
Recursion is short and readable, but the call stack has a limit. The alternative is to keep your own stack. In Python a plain list works well as a stack: append pushes an item on the top, and pop removes the item from the top. Because the list lives in heap memory, it can grow until the computer runs out of memory, not until Python's recursion limit is reached. You push a vertex when you want to visit it, and pop when you are ready to. The shape of the walk is the same.
Type the same six-vertex input as before, then press Run:
Expected output:
order: 0 2 4 5 3 1The order is different from Program 1, and that is normal. Both are valid depth-first walks. The explicit stack pushes all unseen neighbours at once, so the last one pushed is the first one explored. Vertex 2 is pushed after 1, so 2 is popped first.
Trace the first few pops. The stack starts as [0]. Pop 0 and mark it. Its neighbours 1 and 2 are pushed, so the top of the stack is 2. Pop 2 and mark it. Its neighbour 0 is seen, but 4 is not, so 4 is pushed. Pop 4, mark it, and push 5. Pop 5, mark it, and push 3. Pop 3, mark it, and push 1, which is still unseen at this point. The stack now holds two copies of 1. Pop the first copy and mark it. Pop the second copy, see that it is seen, and skip it. That is why the if seen[u]: continue check is there: a vertex can be pushed more than once, and the check makes sure it is only processed once.
The stack version and the recursive version both explore deep first. They differ only in the order of the neighbours pushed. If you wanted the exact recursive order from the stack, you would push the neighbours in reverse, which is a common interview follow-up.
Use the explicit stack when the graph might be deep. It has no fixed limit except memory. The stack holds up to one entry per pushed neighbour, which can be more than V in a dense graph, but it never fails because a chain was long.
Connected components
In an undirected graph, a connected component is a group of vertices that can all reach each other, and cannot reach any vertex outside the group. Think of friend circles at school. Within one circle, everybody is linked through a chain of friendships. Two circles have no link between them.
Counting components is simple once you have DFS. Loop over every vertex. When you meet a vertex that is not yet seen, it belongs to a component nobody has explored yet. Start a walk from it, which marks every vertex in its circle, and add one to the count. The next time you meet a seen vertex, skip it, because its circle is already counted.
The loop over all vertices matters. A DFS from vertex 0 only reaches the group that contains 0. A graph with several groups needs one walk per group.
Program 3 counts components and also prints the size of each one. It uses the explicit stack, so a big group cannot hit the recursion limit. The input is seven vertices and three edges, which makes two groups plus two lonely vertices.
Type this into the Input box:
7 3
0 1
2 3
3 4Expected output:
components: 4
sizes: [2, 3, 1, 1]Read the output. There are four groups: {0, 1}, {2, 3, 4}, {5} and {6}. The lonely vertices 5 and 6 count as groups of size 1. The most common mistake with components is to forget them, which gives 2 instead of 4 here. A vertex with no edges is still a component.
The program marks a vertex as seen at the moment it pushes it, the same rule as BFS. The size += 1 counts vertices as they are popped. Each vertex is pushed once, so each is counted once. The outer loop starts a new group only when it meets an unseen vertex, which happens exactly once per group.
Cycles in undirected graphs
A cycle is a path that starts and ends at the same vertex, without reusing an edge. A triangle is a cycle of length 3. In a graph of friendships, a cycle means that A knows B, B knows C and C knows A. In a road network, a cycle is a loop of roads that brings you back to where you started.
Why do cycles matter? A graph with no cycles is a forest, and each connected piece of one is a tree (a connected graph with no cycle). Trees are simple to work with. A build system or a dependency graph that contains a cycle often cannot finish, because each step waits for another. Many algorithms need the graph to be a tree or to have no cycle, so detecting one is a basic check.
For undirected graphs, DFS detects a cycle with one extra idea: the parent. When the walk moves from u to a neighbour v, remember that u is the parent of v in the walk. Later, if the walk at some vertex sees a neighbour that is already seen, and that neighbour is not its parent, there are two different routes into the same vertex. Those two routes form a cycle.
The parent is excluded for a reason. An undirected edge u v appears in both lists, so when the walk is at v, it always sees u as an already-seen neighbour, namely its parent. That is not a new route, it is the edge the walk just came along. Without the parent check, every edge would look like a cycle of length 2.
Program 4 checks for a cycle in an undirected graph. It walks each component with recursion and passes the parent along. The function returns True or False. Python writes these two values with a capital letter, so the output says True, not true.
Type this into the Input box. The graph is a triangle 0-1-2 plus a tail to vertex 3, so it has a cycle:
4 4
0 1
1 2
2 0
2 3Expected output:
has cycle: TrueTrace the triangle. Start at 0 with parent -1. Its neighbours are 1 and 2, both unseen, so the walk goes to 1 with parent 0. Vertex 1 has neighbours 0 and 2. Vertex 0 is seen and it is the parent, so the program ignores it. Vertex 2 is unseen, so the walk goes to 2 with parent 1. Vertex 2 has neighbours 1, 0 and 3. Vertex 1 is seen and it is the parent, so ignored. Vertex 0 is seen and it is not the parent of 2 (the parent is 1), so the function returns True. The cycle is 0, 1, 2, 0.
Change the input to remove the edge 1 2 and change the first line to 4 3. The answer then becomes has cycle: False. Check it yourself: the graph becomes a path 1-0-2-3, which has no cycle.
The break in the loop over starting vertices stops the search once a cycle is found, because there is no need to look at other groups. Also notice that the program starts a walk from every unseen vertex, not just from vertex 0. A graph with two groups, one with a cycle and one without, would be missed if you started only at 0.
Cycles in directed graphs
Directed graphs need a different rule, and the common mistake here is to use the undirected rule by accident. In a directed graph, the edge u to v goes one way only, so there is no parent to exclude. But seeing a vertex that is already seen is no longer proof of a cycle.
Consider a directed graph with edges 0 to 1, 0 to 2 and 1 to 2. From 0, the walk goes to 1, and from 1 it reaches 2. Later the walk returns to 0 and tries the edge 0 to 2. Vertex 2 is already seen. But there is no cycle: 2 was reached by two different paths, and neither path loops back. The "seen before" rule would wrongly say there is a cycle.
A cycle in a directed graph means that you can follow the arrows and come back to a vertex you are still in the middle of visiting. In other words, the vertex is on the current path of the walk. Vertices that finished already are not on the path, and seeing them is harmless.
To track this, give each vertex one of three states:
- 0, unseen: the walk has not reached it yet.
- 1, on the current path: the walk entered this vertex and has not finished it. Its recursive call is still running.
- 2, finished: every neighbour of this vertex has been explored, and its call has returned.
A cycle exists exactly when the walk reaches a neighbour whose state is 1. That neighbour is still on the path, which means the path goes from it to the current vertex and back.
Imagine the walk on a directed cycle 1 to 2 to 3 to 1. When the walk is at 3, vertex 1 is still on the path (state 1), so the edge from 3 back to 1 closes a loop. In the earlier example with 0 to 2, when the walk looks at 2 from 0, vertex 2 is finished (state 2), so the edge is safe.
Program 5 implements this rule. The state list replaces the seen list. The check state[v] == 1 is the only way to return True.
Type this into the Input box. The graph has a directed cycle 1 to 2 to 3 back to 1:
4 4
0 1
1 2
2 3
3 1Expected output:
has cycle: TrueTwo details are worth noting. First, the program adds each edge only once, to adj[u]. A directed edge does not have a reverse copy, and adding one would create fake cycles. Second, the state becomes 2 only after the loop over neighbours finishes. If you set it to 2 too early, a real cycle could be hidden.
Now test the DAG (a directed graph with no cycle) from earlier. Type this input, which has edges 0 to 1, 0 to 2 and 1 to 2, and check that the output is has cycle: False:
3 3
0 1
0 2
1 2Trace it: from 0 (state 1), the walk goes to 1 (state 1), then to 2 (state 1). Vertex 2 has no outgoing edges, so it becomes state 2 and the call returns. Back at 1, the loop ends, so 1 becomes state 2. Back at 0, the next neighbour is 2, which is state 2, not 1. The check state[v] == 1 is false, and 2 is not unseen, so nothing happens. Vertex 0 becomes state 2. No cycle. This is the rule working as designed.
Islands in a grid
Grids are graphs, as lesson 1 showed. DFS is a natural fit for one common grid question: how many islands are there? In a grid of land (1) and water (0), an island is a group of land cells joined up, down, left or right. Counting islands is counting connected components, with the grid as the graph.
The method is the same as for components. Scan every cell. When you find land that has not been used, count an island and sink it. Sinking means overwriting every connected land cell with water, so later scans skip it. The recursion goes in four directions, and a check at the top of the function handles the edges of the grid.
Python strings cannot be changed in place, so each row is turned into a list of single characters with list(row). Then grid[r][c] = "0" can overwrite one cell.
Program 6 counts islands. The input gives 4 rows and 5 columns, and each row is a string of 0s and 1s.
Type this into the Input box:
4 5
11000
11011
00100
00011Expected output:
islands: 4The four islands are the top-left block of four land cells, the pair in row 1 at columns 3 and 4, the single cell in row 2 at column 2, and the pair in row 3 at columns 3 and 4. Each one is found by the outer loop exactly once, because the first land cell of each island triggers a sink, and that call turns the whole island to water.
This grid version uses recursion, so it inherits the recursion limit from the previous section. A 500 by 500 grid of land could make 250,000 nested calls. For a big grid, replace the recursion with an explicit list of cells, as in Program 2, or do the walk with BFS from lesson 1.
Common mistakes and the messages they produce
Mistake 1: no seen check. The recursive function calls itself on every neighbour, including the ones it already came from. On an undirected edge, that means going back and forth forever. The result is the error below. Python stops with RecursionError after about 1000 nested calls, and the repeated line in the traceback is your function name. The example uses a two-vertex graph with the edge 0-1, and the walk never checks seen:
def walk(adj, u):
for v in adj[u]:
walk(adj, v)
adj = [[1], [0]]
walk(adj, 0)Output (the file path is shortened):
Traceback (most recent call last):
File "...", line 7, in <module>
walk(adj, 0)
~~~~^^^^^^^^
File "...", line 3, in walk
walk(adj, v)
~~~~^^^^^^^^
File "...", line 3, in walk
walk(adj, v)
~~~~^^^^^^^^
File "...", line 3, in walk
walk(adj, v)
~~~~^^^^^^^^
...
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededThe ... marks lines left out of this excerpt. Fix it by marking the vertex and checking the mark before each call.
Mistake 2: starting only from vertex 0. A walk from one start reaches only its own group. On a disconnected graph, the count of groups or the cycle check is wrong, but nothing crashes. This bug is silent, so test with a graph that has an isolated vertex. The count of components should include it.
Mistake 3: undirected rule on a directed graph. If you use the parent check on a directed graph, it can miss cycles or report false ones. Use the three-state rule for directed graphs. Test with a small DAG where one vertex has two incoming edges, like 0 to 2 and 1 to 2, to see the false cycle appear.
Mistake 4: forgetting the reverse edge when undirected. If you store an undirected edge once, the walk can go from u to v but never back. Components are then split into pieces that are not really separate, and the count goes up. Store both directions.
Mistake 5: wrong bounds in the grid. Python raises an error when an index is too large, but it does not raise an error when an index is -1. Instead, -1 counts from the end of the list, so grid[-1] is the last row. A bounds check that only tests the upper edge, such as r >= len(grid), misses the top edge and quietly walks into the bottom row. This version has that bug:
def sink(grid, r, c):
if r >= len(grid) or not (0 <= c < len(grid[0])):
return
if grid[r][c] != "1":
return
grid[r][c] = "0"
sink(grid, r + 1, c)
sink(grid, r - 1, c)
sink(grid, r, c + 1)
sink(grid, r, c - 1)On this input, the grid has two islands, one at row 0 and one at row 2 of the same column:
3 1
1
0
1The program prints islands: 1. There is no error message, which makes this bug harder to find. The check 0 <= r < len(grid) in Program 6 prevents it. The error for an index that is too large looks like this:
IndexError: list index out of rangeMistake 6: a list repeated with *. The expression [[]] * n makes n references to one list, so changing one vertex changes all of them:
adj = [[]] * 3
adj[0].append(1)
print(adj)Output:
[[1], [1], [1]]Every vertex now appears to have the neighbour 1. Build the list with a comprehension: [[] for _ in range(n)].
Mistake 7: a default argument that is a list. A default value such as seen=[] is created once, when Python reads the function, and then every call uses that same list. Old marks stay in it:
def visit(u, seen=[]):
seen.append(u)
return seen
print(visit(1))
print(visit(2))Output:
[1]
[1, 2]The second call returns the marks from the first call too. Pass the list in, or use seen=None and create a new list inside the function when it is None.
Debugging walkthrough
Suppose your cycle detector says has cycle: True on a tree, where you are sure there is no cycle. Work through this sequence.
First, print the edges as the program reads them. Is the graph the one you meant? Often the input is read in the wrong order, for example the first line is taken as edges rather than n and m.
Second, check the parent argument. The start call is has_cycle(adj, seen, s, -1), and the recursive call is has_cycle(adj, seen, v, u). If either is wrong, the parent check fails. Add a print at the top of the function: print(f"at {u} parent {parent}"). You will see whether each vertex sees the right parent.
Third, check the seen marks. If a vertex is printed twice, it was entered twice, which means the marks are missing. The print at the top of the function shows that immediately.
Fourth, check the rule you are using. Is the graph directed or undirected? If you wrote the undirected rule and the graph has arrows, a false cycle can appear. Run the DAG example from the directed section, which should give False, and see if you get True.
Following these four steps in order finds most DFS bugs. The printed trace from the top of the function is the most useful tool, because it shows the walk as it happens.
Variations and edge cases
Iterative versus recursive. Both are fine for small graphs. Recursion is shorter to write and easy to read. The explicit stack is safer for big or deep graphs, because it does not hit the recursion limit. In an interview, either is accepted, but mention the limit if the graph might be large.
Finish order. DFS can also record the order in which vertices finish, meaning the order in which their calls return. This order is the key to topological sort in the next lesson. Append a vertex to a list after its loop ends, and the list is in finish order.
Disconnected graphs. Always loop over every vertex as the start of a walk, as Program 3 does. This is the single most common reason a component count is wrong.
Edge cases. Test a graph with no edges (every vertex is its own component), a single vertex, a graph that is one long chain, a graph with a self-loop (an edge from a vertex to itself, which is a cycle of length 1), and a graph with two parallel edges between the same pair. Two parallel edges form a cycle of length 2, and the parent check above reports it. Test each case on paper before you trust the program.
Interview questions this lesson answers
"How many connected components does this graph have?" Loop over vertices, start a DFS or BFS at each unseen one, and count the starts. O(V + E) time.
"Does this undirected graph contain a cycle?" Run DFS with a parent check, or use union-find (lesson 5). A cycle exists if a seen neighbour is not the parent.
"Does this directed graph contain a cycle?" Use three states and report a cycle when a neighbour is on the current path. Mention why the undirected rule is wrong here.
"Count the islands in a grid." The grid is a graph. Sink each island with DFS, or BFS, and count the starts.
"Why does DFS need the seen list?" Without it, the walk can revisit a vertex forever along a cycle, which fails with RecursionError or never finishes.
Real-world uses
Components answer "are these two users in the same group?" for a social network and "which pieces of a damaged road network are cut off?" for a map. Cycle detection checks whether a build system, a package manager or a spreadsheet has a dependency loop. Island counting is a standard way to count regions in an image, such as blobs in a microscope slide.
Practice
Exercise 1 (easy). How many components does a graph with 7 vertices and edges 0-1, 2-3 and 3-4 have? Hint: do not forget vertices 5 and 6.
Show the answer
Four. The groups are {0, 1}, {2, 3, 4}, {5} and {6}. The two lonely vertices each count as a group of their own.
Exercise 2 (easy). Does the directed graph with edges 0 to 1, 1 to 2 and 2 to 3 have a cycle? Hint: follow the arrows from each vertex.
Show the answer
No. The arrows only go forward from 0 to 3. No walk following arrows can return to a vertex it has left.
Exercise 3 (easy). Explain in one sentence why an undirected DFS must skip the parent when it checks for a cycle.
Show the answer
Every undirected edge is stored in both lists, so the vertex the walk came from always appears as a seen neighbour, and that is the edge just used, not a second route.
Exercise 4 (medium). Change Program 1 so it prints the finish order (the order in which each call's loop ends), not the visit order. Hint: add the order.append(u) line after the for loop, not before it.
Show the answer
Move order.append(u) from the top of dfs to the bottom, after the for loop. For the six-vertex input the output is order: 2 4 5 3 1 0. The last call made, on vertex 2, is the first to return, so it finishes first. Then its callers finish in reverse order of the walk: 4, 5, 3 and 1, and vertex 0 finishes last.
Exercise 5 (medium). For the directed graph with edges 0 to 1, 0 to 2, 2 to 1 and 1 to 3, trace the three-state check starting at 0 and say whether it finds a cycle. Give the state of each vertex when the walk finishes.
Show the answer
No cycle. From 0 (state 1), the walk goes to 1 (state 1), which goes to 3 (state 1). Vertex 3 has no outgoing edges, so it becomes 2, and 1 becomes 2. Back at 0, the next neighbour is 2 (state 0), so it is entered and its neighbour 1 is already 2, not 1. Vertex 2 becomes 2 and 0 becomes 2. Final states: 0 is 2, 1 is 2, 2 is 2, 3 is 2. A short Python check of this graph prints [2, 2, 2, 2].
Exercise 6 (medium). Modify Program 6 so it prints the size of the largest island. Hint: count the cells that sink turns to water. Add a counter that sink increments. A list can hold the counter, because a plain integer cannot be changed by a function that receives it.
Show the answer
Use a one-item list such as size = [0] and add 1 to size[0] in sink right after setting the cell to "0". In main, before calling sink, set size[0] to 0, call sink, then compare size[0] with the largest so far. For the example grid the largest island has 4 cells, so the output line is largest: 4.
Exercise 7 (medium). Explain why starting the cycle check only from vertex 0 can miss a cycle. Give a small graph that shows it.
Show the answer
A walk from 0 only reaches the group that contains 0. Take 5 vertices with the edges 0-1, 2-3, 3-4 and 4-2. Vertices 0 and 1 form a tree with no cycle, and 2, 3, 4 form a triangle. A walk that starts only at 0 never reaches the triangle and reports no cycle. A walk started from every unseen vertex, here the one at 2, finds it.
Exercise 8 (medium). Program 2 marks a vertex as seen when it is popped and checks if seen[u]: continue. What goes wrong in the visit order if you delete that check?
Show the answer
A vertex can be pushed more than once before its first pop. In the six-vertex example, vertex 1 is pushed twice. Without the check, the second copy is popped and processed again. A Python run of the program without the check prints order: 0 2 4 5 3 1 1. The vertex 1 appears twice in the order, so the output is wrong, even though the walk still ends. The second copy pushes nothing, because its neighbours 0 and 3 are already seen.
Exercise 9 (hard). Prove that a directed graph with a cycle reaches state 1 for some vertex, so the three-state check cannot miss a cycle.
Show the answer
Take a cycle of vertices c1, c2, ..., ck, with an edge from each to the next and from ck back to c1. Consider the first vertex of this cycle that the walk enters, say c1. Every other vertex of the cycle is unseen at that moment, so the walk must reach each of them through the cycle, which keeps c1 on the current path (state 1) until the walk returns to c1's neighbour ck. When the walk looks at the edge from ck to c1, c1 is still state 1, so the check returns True. The argument needs only that the walk visits the cycle's vertices before leaving c1's call, which holds because each is unseen and reachable from c1 along the cycle.
Exercise 10 (hard). Write a function that returns the number of connected components in a graph with up to 200,000 vertices, using an explicit list as a stack so it does not hit the recursion limit. Explain why recursion would be a bad choice for this size.
Show the answer
Use the stack version from Program 3 and wrap it in a function that returns len(sizes). Recursion with 200,000 vertices in one chain would need about 200,000 frames. Python's default limit is 1000, so the program would stop with RecursionError after about 1000 nested calls. The list used as a stack lives in heap memory and grows with the data, so it works for any size the computer has memory for.
What you now know
- Depth-first search goes as deep as it can along one path, then backs up and tries the next branch.
- The recursive version uses the call stack, one frame per active call. Deep graphs can hit Python's recursion limit and fail with
RecursionError. - A plain list used with
appendandpopis a stack. The explicit stack version walks the same graph without the recursion limit and can explore a different order. - Connected components are found by starting a walk from every unseen vertex and counting the starts.
- In an undirected graph, a cycle exists when a walk meets a seen neighbour that is not its parent.
- In a directed graph, a cycle exists when a walk meets a neighbour that is still on the current path (state 1).
- Grid problems such as island counting are graph problems, with the four neighbours of each cell as the edges.