DFS, components and cycle detection

Why it matters

"Is everything connected?", "how many separate groups are there?" and "does this network contain a loop?" are among the most common graph questions in interviews and in real systems. A network engineer asks the first when a cable is cut. A social app asks the second when it suggests groups of friends. A build tool asks the third when two packages depend on each other. One short recursive function answers all three, once you understand how it moves through the graph.

This lesson builds on the previous one. You should be comfortable with adjacency lists, with vector, and with the idea that a queue visits vertices in rings. Depth-first search, the subject here, uses a different order, and that order is what makes these three questions easy.

The idea of depth-first search

Depth-first search, usually shortened to DFS, goes as deep as it can along one path before it backs up. Picture yourself exploring a maze. You take a corridor, then another new corridor, always choosing a branch you have not walked before. When you reach a dead end, you walk back to the most recent fork where a corridor was still unexplored, and you try that. You keep doing this until every corridor you can reach has been walked.

Compare that with BFS from the previous lesson. BFS walks outward in rings, so it finishes every vertex one step away before any vertex two steps away. DFS dives. It does not care about distance from the start. It only cares about covering every reachable vertex exactly once. That single difference makes it the natural tool for questions about groups and loops, where distance does not matter.

DFS needs two things. The first is a seen array with one entry per vertex, which records whether we have already visited it. The second is recursion. Each call to dfs(v) visits v, then calls itself on each neighbour that is not yet seen. The call stack remembers the forks for you. When a call returns, the caller continues its own loop from the next neighbour, which is exactly the walk back to the last fork.

Without the seen check, DFS would call itself forever on any graph with a loop, because it would keep returning to the same vertices. The check is what turns an endless walk into a finite search.

Step through the recursion below. Watch which call is on top of the stack, and watch the seen marks appear as each vertex is first entered.

Now step through the same search on the graph itself. Notice how the path goes deep before any side branch is tried.

Look for two things while you step. First, the search goes down a single chain of vertices until it reaches one with no unseen neighbour. Second, when it comes back up, it tries the next unseen neighbour of the vertex it returned to, not the vertex it started from.

A worked trace by hand

Take the same six-vertex graph as the previous lesson, with the same input order. The adjacency lists are 0: 1 2, 1: 0 3, 2: 0 3, 3: 1 2 4, 4: 3, and 5: is empty. Start DFS at vertex 0. We record the order in which each call starts, which is called discovery, and the order in which each call finishes, which is called finishing.

Call dfs(0). Mark 0 as seen. Its first neighbour is 1, which is not seen, so we call dfs(1).

Call dfs(1). Mark 1 as seen. Its first neighbour is 0, which is seen, so skip it. The next neighbour is 3, which is not seen, so call dfs(3).

Call dfs(3). Mark 3 as seen. Its first neighbour is 1, which is seen, skip. The next neighbour is 2, which is not seen, so call dfs(2).

Call dfs(2). Mark 2 as seen. Its neighbours are 0 and 3. Both are seen, so nothing happens. Return. Vertex 2 is finished.

Back in dfs(3). The next neighbour is 4, which is not seen, so call dfs(4).

Call dfs(4). Mark 4 as seen. Its only neighbour is 3, which is seen. Return. Vertex 4 is finished.

Back in dfs(3), there are no neighbours left. Return. Vertex 3 is finished. Back in dfs(1), no neighbours are left, so return. Back in dfs(0), the next neighbour is 2, but it is already seen, so nothing happens. Return.

The visit order was 0, 1, 3, 2, 4. Vertex 5 was never reached. We will use a counter to record the discovery and finish times. The counter goes up by one at each discovery and each finish. Writing the numbers down gives a table:

vertex:   0   1   2   3   4   5
in:       1   2   4   3   6   -
out:     10   9   5   8   7   -

The program below records the same two counters, so you can check your table.

Type the same graph with source 0 into the Input box, which is 6 5 0 followed by the five edges from the earlier trace. The program prints:

vertex 0: in 1, out 10
vertex 1: in 2, out 9
vertex 2: in 4, out 5
vertex 3: in 3, out 8
vertex 4: in 6, out 7
vertex 5: not reached

The two counters match the table. Vertex 1 was entered at time 2 and finished at time 9, and everything between those two times happened inside it. Vertex 3 sits inside 1, and 2 and 4 sit inside 3. This nesting is the key idea behind the topological sort in the next lesson, which uses finish times.

Counting connected components

A connected component is a group of vertices where every vertex can reach every other vertex in the group. In the sample graph, the vertices 0 to 4 are one component, and 5 is a component by itself. To count components, we run DFS from every vertex that has not been seen yet. Each new start finds one whole component, because DFS reaches everything that is connected to its start. The count of starts is the count of components.

The first program prints each component and then the total. The input is a graph with seven vertices and four edges.

Type this into the Input box:

7 4
0 1
1 2
3 4
5 6

The program prints:

component 1: 0 1 2
component 2: 3 4
component 3: 5 6
total: 3

Read the program carefully, because it has three parts that do three jobs. The global adj and seen are shared by dfs, so the recursive function does not need them as parameters. The current vector collects the members of the component being explored. The outer for loop does the counting. It skips vertices already seen, and for each unseen vertex it runs DFS, adds one to the count, and prints what DFS collected.

Notice that the outer loop is what finds the second and third groups. A single call to dfs(0) finds only 0, 1 and 2. If you leave out the loop, your program reports one component when the graph has three. That is the most common bug in component code, and it is listed in the mistakes section below.

The output order within a component follows the order DFS visits it. For component 1, DFS starts at 0, goes to 1, then goes to 2. Vertex 2 has neighbour 1 only, so the search goes back. The members are printed in visit order, not sorted order. If a problem wants sorted members, sort the vector afterwards.

Detecting a cycle in an undirected graph

A cycle is a path that starts and ends at the same vertex without reusing an edge. A triangle 0-1-2-0 is a cycle. A line 0-1-2 is not. Many problems need to know whether a graph has any cycle, such as checking whether a set of tasks can be laid out as a tree, or whether a network has a redundant link.

In an undirected graph, DFS finds a cycle with one simple rule. When we are at vertex v, we came from some parent p. The edge v-p is the one we just walked along, so p is always a seen neighbour of v. That is not a cycle. Any other seen neighbour of v is a problem. It means we have found a second route back to a vertex already on our walk, and two routes between the same two vertices form a loop.

The second program applies that rule. It answers yes or no for two graphs. The first graph is a line, and the second graph is a triangle with a tail. Here is the code.

Type this into the Input box. It is a line of four vertices:

4 3
0 1
1 2
2 3

The program prints:

no

Now type this instead. It is the triangle 0-1-2 with the extra edge 2-3 hanging off it:

4 4
0 1
1 2
2 0
2 3

The program prints:

yes

Trace the triangle. Start at 0 with parent -1. Mark 0. Its neighbours are 1 and 2. Vertex 1 is not seen, so go to 1 with parent 0. Vertex 1 marks itself, and its neighbours are 0 and 2. Vertex 0 is seen and it is the parent, so skip. Vertex 2 is not seen, so go to 2 with parent 1. Vertex 2 marks itself, and its neighbours are 1, 0 and 3. Vertex 1 is seen and is the parent, so skip. Vertex 0 is seen and is not the parent, which means we found a second route back to 0. Return true.

The line w != parent is the heart of the check. Without it, every edge would look like a cycle, because the edge we walked along would always show up as a seen neighbour. The parent test skips exactly one edge: the one we came in by. Every other edge to a seen vertex is a real extra route.

Two more details. The first is that the loop in main stops as soon as one component reports a cycle. There is no reason to check the rest. The second is that the parent test treats two parallel edges between the same pair of vertices as a cycle. That is the right answer, because two different edges between 0 and 1 form a loop of length 2. Some problems say that the graph has no parallel edges. In that case the test still works.

The parent trick works only for undirected graphs. For a directed graph, the edge a -> b does not give b a way back to a, so the parent test is wrong. A directed cycle needs a different method, which the next lesson covers with the topological sort.

DFS with an explicit stack

Recursion is convenient, but it uses the program's call stack. Each call takes memory, and a path of 100,000 vertices makes 100,000 nested calls. Many systems allow only a few megabytes for the call stack. A very deep recursion then crashes the program, usually with a message like Segmentation fault (core dumped) on Linux.

To avoid that, you can keep your own stack in a vector. The third program finds every vertex reachable from a source, using a loop instead of recursion. It pushes the source, pops one vertex at a time, and pushes its unseen neighbours. The order of visits is different from recursive DFS, so the program prints a set rather than a sequence. That is still the right answer for "which vertices can I reach?"

Type this into the Input box. It is the same six-vertex graph from earlier, with source 0:

6 5 0
0 1
0 2
1 3
2 3
3 4

The program prints:

reachable: 0 1 2 3 4
count: 5

Notice the difference from recursive DFS. Here seen is set when a vertex is pushed, not when it is popped. That is the same rule as BFS, and it has the same reason: a vertex must never go on the stack twice. Also notice that the program prints the reachable vertices in index order, by scanning seen at the end, not in the order they were visited. The search order does not matter for a reachability question, so a scan is the simplest way to print them.

The explicit stack is the way to write DFS for very large graphs. The memory is in a vector on the heap, which can grow much larger than the call stack. The time is the same as the recursive version.

Counting islands in a grid

A grid of land and water is a graph again. Each land cell is a vertex, and two land cells are neighbours when they touch up, down, left or right. An island is a connected component of land. Counting islands is therefore counting components in a grid. The usual method is a DFS that "sinks" each island it finds, which means it changes land cells to water so that they are never counted again.

The fourth program counts the islands in a grid and also reports the size of the largest one. It uses recursion, so you can see the flood spread out from each starting cell.

Type this into the Input box. The first line gives the rows and columns, and each following line is one row of the photo:

4 5
11000
11011
00100
00011

The program prints:

islands: 4
largest: 4

Work through the photo by hand. The top-left island has four cells: (0,0), (0,1), (1,0) and (1,1). The cell (1,3) and (1,4) form a second island with two cells. The cell (2,2) is alone and forms a third island with one cell. The cells (3,3) and (3,4) form the fourth island. There are four islands and the largest has four cells, which matches the output.

The function fill does two things at once. It returns the size of the island by adding one for the current cell and the sizes of the four neighbours. It also sinks each cell by setting it to '0', which is the seen mark. Without that line the function would recurse into the same cells forever, because fill on a land cell would call fill on its neighbour, which would call fill back on the first cell.

The outer loops visit every cell. When fill returns a positive size, a new island has been found. Cells that are already water return 0 and are not counted, so each island is counted exactly once.

The grid version also shows the recursion-depth problem clearly. In the worst case, the photo is one big island, and fill recurses once for every land cell. A 1000 by 1000 grid of land can make a million nested calls, which is likely to overflow the call stack. For a grid that large, use an explicit stack like the third program, or a queue like BFS, which is what the practice exercise asks you to write.

The island count step by step

Walk through the photo from the program, one cell at a time, to see the flood happen. The outer loops scan the rows from top to bottom, and each row from left to right.

Row 0: cell (0,0) is land, so fill starts there. It sinks (0,0), then looks at its neighbours. (0,1) is land and is sunk. (1,0) is land and is sunk. (1,1) is land and is sunk. Every other neighbour is water or off the grid. The flood returns 4, so the count of islands is 1 and the largest so far is 4. The water cells in row 0 each return 0 and are skipped.

Row 1: cell (1,3) is land and island A is already sunk, so this is new land. fill sinks (1,3) and (1,4), and returns 2. The count is now 2. The largest is still 4.

Row 2: cell (2,2) is land, but no land touches it up, down, left or right. Its diagonal neighbours do not count. fill sinks it and returns 1. The count is now 3.

Row 3: cell (3,3) is land. fill sinks it, then sinks its right neighbour (3,4), and returns 2. The count is now 4.

Every cell has now been visited once. The count is 4 and the largest size is 4. The key point is that sinking happens during the walk. A cell sunk early is never counted again, because the outer loops see water when they reach it later.

Checking whether a graph splits into two teams

A graph is bipartite when its vertices can be coloured with two colours so that no edge joins two vertices of the same colour. Think of the two-teams idea: rivals must not share a team. A graph is bipartite exactly when the rivals can be split into two teams.

DFS or BFS can test this. Colour the first vertex of a component 0. Every neighbour must get the other colour, 1. Keep walking. Whenever you reach a vertex that already has a colour, check that its colour is different from the vertex you came from. If an edge joins two vertices of the same colour, the answer is no.

A small example shows the rule. Take a square 0-1-2-3-0. Colour 0 as 0. Its neighbours 1 and 3 get colour 1. The neighbour 2 of 1 must be 0, and 2 is also a neighbour of 3, which has colour 1, so every edge joins different colours. The square is bipartite. Now add the edge 0-2, which makes a triangle. Vertex 0 has colour 0 and vertex 2 has colour 0, and they are joined, so the answer is no. A triangle is an odd cycle, and an odd cycle always breaks two-colouring.

The rule of thumb is that a graph is bipartite exactly when it has no cycle of odd length. The check costs O(n + e), the same as a search, because it is one walk with a colour stored for each vertex.

What the computer does with the calls

Each call to dfs or fill creates a stack frame. A frame holds the parameters, the local variables and the return address for that call. The frame is pushed onto the call stack when the call starts and popped when it returns. The program can only be as deep as the call stack allows.

The call stack while dfs(2) runs, with the frames above it still waiting

On a typical Linux system the call stack is about 8 megabytes. A frame for a simple function like dfs might use 32 to 64 bytes, so the stack can hold roughly 100,000 to 250,000 nested calls. Those numbers are approximate and depend on the compiler and the options, but the lesson is clear. A path of 100,000 vertices is risky for recursion, and a grid with a million land cells in one island is certain to crash.

The memory cost of DFS on an adjacency list is O(n) for the seen array plus the recursion depth, which is at most n. The time is O(n + e), because every vertex is entered once and every edge is looked at twice, once from each end. For a grid with R rows and C columns, the same bound becomes O(R * C), since each cell is a vertex and each cell has at most four neighbours.

Choosing between BFS and DFS

Use BFS when the question involves distance or fewest steps. Use DFS when the question is about reachability, components, cycles or the structure of the graph. Both run in linear time on an adjacency list, so speed is not the deciding factor. The deciding factor is what the question asks, and what order of visits the answer needs.

When both work, DFS is usually shorter to write with recursion, and BFS is usually safer for very deep graphs, because a queue uses heap memory. In an interview, mention the stack depth limit if the graph might be large. Interviewers often ask about it.

Self-loops and duplicate edges

Real input is not always tidy. Two cases come up often: an edge from a vertex to itself, which is a self-loop, and the same edge listed twice. Many problem statements allow both, so check how your program treats them.

Take the input 3 1 followed by the self-loop 2 2. The list of vertex 2 gets 2 added twice, once for each end of the edge. DFS is not confused by this, because the seen check stops it from entering 2 again. For the cycle check, the self-loop is a real cycle of length one. When hasCycle runs at vertex 2 and looks at the neighbour 2, that neighbour is seen and it is not the parent, so the function returns true. The program prints yes, which is correct.

Now take a duplicate edge, 0 1 listed twice in a two-vertex graph. The search goes from 0 to 1 and back. At vertex 1, both copies of the edge to 0 are the parent edge, so both are skipped. The cycle shows up back at vertex 0, when its loop reaches the second copy of the edge to 1. That neighbour is seen and it is not the parent of 0, so the program prints yes. Two parallel edges do form a loop of length two, so the answer is right. If the statement promises no duplicates, the input is not what you expected, so ask before you rely on the answer.

For components, neither case changes the count. A loop or a duplicate joins vertices that are already in the same group, so the number of groups stays the same. Only the cycle answer depends on these cases, which is why the problem statement matters.

Common mistakes

The first mistake is forgetting the outer loop. If you call dfs(0) once and print "connected" or "one component", you have missed every other group. A graph with seven vertices and three groups needs three starts. Count how many times you start a search, not how many times you call dfs.

The second mistake is treating the edge back to the parent as a cycle. A line 0-1-2 has no cycle. If your check does not skip the parent, the program will say yes for a line. The fix is the test w != parent, which skips exactly one edge.

The third mistake is not clearing the seen array between separate test graphs. A program that reads several graphs from one input must reset seen for each one. If it does not, the second graph starts with some vertices already marked, and the component count comes out too small. The compile-time code looks fine, so this bug only shows up when you run more than one test. A sign of it is a count that is smaller than the number of groups you can see by eye.

The fourth mistake is running the undirected cycle check on a directed graph. In a directed graph, a -> b does not give b an edge back to a, so the parent test returns wrong answers. Use the method from the next lesson for directed graphs.

The fifth mistake is a stack overflow. The message on Linux looks like this:

Segmentation fault (core dumped)

That message does not say where the problem is. It says only that the program touched memory it did not own. A deep recursion on a large graph is the usual cause. If your program works on a small input and crashes on a large one, suspect recursion depth first. Switch to an explicit stack or a queue to confirm.

Debugging walkthrough

A classmate writes the cycle check, runs it on a tree, and gets yes. A tree is a graph with no cycles, so the answer is wrong. How do you find the bug?

Start with the smallest tree that shows the problem. A line of two vertices, 0-1, is enough. Run hasCycle(0, -1) by hand. Vertex 0 is marked. Its neighbour 1 is unseen, so call hasCycle(1, 0). Vertex 1 is marked. Its neighbour 0 is seen, and the test is w != parent. Here parent is 0, so w equals parent, and the test is false, so the else if does nothing. The function returns false. If the classmate's code gives yes here, the parent test must be missing or written wrong.

Look at the classmate's code and you will likely find else return true; with no parent test, or a parent that is passed as -1 in the recursive call. Either bug turns every edge into a cycle. Fix the call so that the parent is passed correctly, and run the two-vertex tree again. The answer should now be no.

The general lesson is to start with the smallest input that shows the bug. Trace it by hand with the recursion written out, as above. A single small trace shows more than an hour of staring at a large input.

Patterns that come up in interviews

Components come up in problems about friends, accounts, networks and groups of cells. The question "how many groups" is a component count. The question "are these two items in the same group" is a reachability check, and a single DFS from one of them answers it.

Island problems are grid components. The main variations are whether diagonal cells touch, whether the grid has walls, and whether you need the size or the shape of each island. The same flood fill covers all of them. Change the four direction steps to eight to allow diagonal touching.

Cycle detection is a common warm-up. The question "can this set of prerequisites or links be a tree" is a cycle question on an undirected graph, plus a connectivity check, since a tree must also be connected. Remember that a tree has exactly n - 1 edges when it is connected and has no cycles.

Flood fill is a related idea: paint all cells connected to a starting cell with a new colour. Interviewers like it because it tests the recursion base case and the mark-before-recursing rule in one short function.

Practice

1. Change the component program so that it prints the size of the largest component as well as the total. Hint: the size of a component is the length of current when DFS returns.

2. Change the island program to count islands when diagonal cells touch as well. Hint: the four direction steps become eight. Test it on the photo in this lesson: the answer should change.

3. Write a function that returns true if the undirected graph is a tree. Hint: a tree is connected, so there is one component, and it has exactly n - 1 edges, so count the edges as you read them.

4. Print the number of edges inside each connected component. Hint: after the DFS of a component, add the number of adjacency entries of its members and divide by two.

5. Write a flood fill that recolours the whole region of a cell in a grid of letters. Hint: the stop condition is that the cell has a different colour from the starting colour.

6. Detect a cycle in a directed graph using three colours: white for unvisited, grey for on the current path, and black for finished. Hint: a cycle exists exactly when DFS reaches a grey vertex. This is a hard exercise, so write it slowly.

7. Count the components of a grid of . and # characters, where . is open. Hint: this is the island problem with a different character.

8. Make the recursive island program crash on purpose with a grid of all land and a size of 1000 by 1000. Record what happens. Then change fill so that it uses an explicit vector stack and check that the crash is gone.

9. Explain in your own words why seen[w] = true must happen before the recursive call, not after. Hint: think about what the call would see if it checked the same vertex again.

10. Make the explicit stack version of DFS visit neighbours in the same order as the recursive version. Hint: push the neighbours in reverse order.

What you now know

• Depth-first search goes as deep as it can along one path, then backs up. It needs a seen array to stop from looping forever.
• A connected component is found by starting a DFS from every vertex that has not been seen. The number of starts is the number of components.
• In an undirected graph, a seen neighbour that is not the parent is a cycle. The parent test skips the one edge you walked in on.
• An explicit vector stack gives the same reachability answer and avoids deep recursion, at the cost of some extra code.
• Grid problems are graph problems. Flood fill counts islands by sinking each island as it is found.
• The call stack has a limit, and a deep recursion on a large graph crashes the program with a segmentation fault.
• DFS runs in O(n + e) time and O(n) memory plus the recursion depth.