Who Can I Reach? Depth-First Search
Find everyone a person can reach through friends, and split a network into the groups that don't touch, with a short recursive walk that never goes round in circles: why the folder walk from Module 3 loops forever here, and the search that fixes it, depth-first search, and when to choose it over breadth-first search.
Journeyman · Data Structures · Updated
After this lesson you can
- Trace depth-first search as it goes as deep as it can, then backs up
- Choose between breadth-first and depth-first search for a job
Key takeaways
- The folder walk from Module 3 calls itself for every friend, so on a graph it goes round a loop of friends forever; chalk marks, a visited set, stop it.
- Depth-first search follows one path as far as it can, then backs up to the last fork with an unexplored way and goes deep again.
- Recursion does the backing up for you, because the call stack remembers each fork; a loop with your own stack does the same.
- Like breadth-first search, it needs a visited set and takes O(V + E) time, but it doesn't find the fewest steps.
- Use breadth-first search for "fewest steps"; use either one for "can I get there?" and "who is in this group?"
Before this: in Module 3, How Big Is This Folder? Recursion walked a folder tree by calling itself for each folder inside. A tree has no loops, so the walk always ends. Friends have loops.
The social app wants a "your circle" page: everyone you can reach through friends, friends of friends, and so on, however far. It also wants to know which groups of people don't touch the rest at all, so it can suggest a first friend to each lonely group. On the chapter's network, Ava's circle should be Ben, Cara, Dev, Eli and Fay, and Gus and Hana are a group of their own.
This time nobody asks for the fewest steps, only who is reachable. A game asks the same thing when it checks that every room of a level can be reached from the entrance, and so does a photo app collecting every photo in a folder and the folders inside it.
What would you try?
Reuse the folder walk. Visit a person, then call the same function for each of their friends, the way the folder tool called itself for each folder inside. Start at Ava: she calls Ben, Ben's first friend is Ava, Ava calls Ben again, and so on. On a tree that never happens, because a folder isn't inside its own subfolder. On friends it goes round Ava and Ben until the call stack runs out: a stack overflow, with nobody counted.
Breadth-first search from the last lesson. Run it from Ava: everyone it finds is her circle. Then run it again from anyone not found yet, Gus, and that's the second group. This works, in O(V + E). It keeps a queue of everyone found but not yet explored, which is fine on a computer. It's not how one person would explore, though: a walker in a maze can't stand in every corridor at once.
The folder walk, with chalk. Keep the folder walk, but mark each person the moment you visit them, and never call the function for someone already marked. From Ava: Ben, then Dev, then Cara (Ava and Dev are marked, so stop), back to Dev, then Eli, then Fay. Everyone in the circle, each once, in a function of six lines.
| What we tried | Ava's circle | Where it breaks |
|---|---|---|
| The folder walk, as it is | never finishes | loops of friends |
| Breadth-first search | O(V + E) | works, with a queue of everyone waiting |
| The folder walk, with marks | O(V + E) | works, with one walker and a trail back |
The questions that lead to it
When the walk reaches Cara and every friend of hers is marked, where does it go next? Back to the last place that still had an untried friend: Dev, who still has Eli.
Which structure hands back the newest thing first? A stack (Undo the Last Thing First: Stacks). The forks to go back to pile up, and the newest one is always the first you need.
Where is that stack in the folder walk? It's already there: the call stack (Where Do the Waiting Calls Wait? The Call Stack). Each call that hasn't finished is a fork waiting for the walker to come back.
How it got its name
This search was so useful that it got a name: depth-first search, or DFS. "Depth" is the opposite of breadth-first search's ripples: instead of finishing a whole level, it plunges down one path first, as deep as it goes, then backs up.
The picture to keep is a corn maze, a piece of chalk and a ball of string. At every fork you take a way you haven't tried and chalk it. At a dead end, or a spot already chalked, you follow the string back to the last fork with an untried way. The chalk is the visited set, and the string is the stack.

Here's depth-first search from Ava, taking each person's friends in the order they're listed:
- Ava. Her first friend is Ben: go there.
- Ben. Ava is seen; his next friend is Dev: go there.
- Dev. Ben is seen; his next friend is Cara: go there.
- Cara. Ava and Dev are both seen: a dead end. Back up to Dev.
- Dev again. His next friend is Eli: go there.
- Eli. Dev is seen; Fay is next: go there.
- Fay. Eli is seen: a dead end. Back up to Eli, then Dev, then Ben, then Ava. Ava's other friend, Cara, is seen. Done.
The visit order is Ava, Ben, Dev, Cara, Eli, Fay. Breadth-first search visited Ava, Ben, Cara, Dev, Eli, Fay: same people, different order. DFS reached Cara third, the long way round through Ben and Dev, even though Cara is Ava's own friend. That's why DFS can't tell you the fewest steps.

Depth-first search in code
visit marks a person, then calls itself for each friend not seen yet. When a call returns, the search is back at the fork before it.
The second half finds the separate groups: start a search from anyone not seen yet, and everyone it reaches is one group. Textbooks call these groups connected components.
Dictionary<string, List<string>> network = new Dictionary<string, List<string>>
{
["Ava"] = new List<string> { "Ben", "Cara" },
["Ben"] = new List<string> { "Ava", "Dev" },
["Cara"] = new List<string> { "Ava", "Dev" },
["Dev"] = new List<string> { "Ben", "Cara", "Eli" },
["Eli"] = new List<string> { "Dev", "Fay" },
["Fay"] = new List<string> { "Eli" },
["Gus"] = new List<string> { "Hana" },
["Hana"] = new List<string> { "Gus" },
};
void Visit(string person, HashSet<string> seen, List<string> order)
{
seen.Add(person);
order.Add(person);
foreach (string friend in network[person])
{
if (!seen.Contains(friend))
{
Visit(friend, seen, order);
}
}
}
List<string> fromAva = new List<string>();
Visit("Ava", new HashSet<string>(), fromAva);
Console.WriteLine("Depth-first from Ava: " + string.Join(", ", fromAva));
HashSet<string> seenAll = new HashSet<string>();
int groups = 0;
foreach (string person in network.Keys)
{
if (!seenAll.Contains(person))
{
List<string> group = new List<string>();
Visit(person, seenAll, group);
groups++;
Console.WriteLine("Group " + groups + ": " + string.Join(", ", group));
}
}
Depth-first from Ava: Ava, Ben, Dev, Cara, Eli, Fay
Group 1: Ava, Ben, Dev, Cara, Eli, Fay
Group 2: Gus, Hana
Map<String, List<String>> network = new LinkedHashMap<>();
void visit(String person, Set<String> seen, List<String> order) {
seen.add(person);
order.add(person);
for (String friend : network.get(person)) {
if (!seen.contains(friend)) {
visit(friend, seen, order);
}
}
}
void main() {
network.put("Ava", List.of("Ben", "Cara"));
network.put("Ben", List.of("Ava", "Dev"));
network.put("Cara", List.of("Ava", "Dev"));
network.put("Dev", List.of("Ben", "Cara", "Eli"));
network.put("Eli", List.of("Dev", "Fay"));
network.put("Fay", List.of("Eli"));
network.put("Gus", List.of("Hana"));
network.put("Hana", List.of("Gus"));
List<String> fromAva = new ArrayList<>();
visit("Ava", new HashSet<>(), fromAva);
IO.println("Depth-first from Ava: " + String.join(", ", fromAva));
Set<String> seenAll = new HashSet<>();
int groups = 0;
for (String person : network.keySet()) {
if (!seenAll.contains(person)) {
List<String> group = new ArrayList<>();
visit(person, seenAll, group);
groups++;
IO.println("Group " + groups + ": " + String.join(", ", group));
}
}
}
Depth-first from Ava: Ava, Ben, Dev, Cara, Eli, Fay
Group 1: Ava, Ben, Dev, Cara, Eli, Fay
Group 2: Gus, Hana
network = {
"Ava": ["Ben", "Cara"],
"Ben": ["Ava", "Dev"],
"Cara": ["Ava", "Dev"],
"Dev": ["Ben", "Cara", "Eli"],
"Eli": ["Dev", "Fay"],
"Fay": ["Eli"],
"Gus": ["Hana"],
"Hana": ["Gus"],
}
def visit(person, seen, order):
seen.add(person)
order.append(person)
for friend in network[person]:
if friend not in seen:
visit(friend, seen, order)
from_ava = []
visit("Ava", set(), from_ava)
print("Depth-first from Ava: " + ", ".join(from_ava))
seen_all = set()
groups = 0
for person in network:
if person not in seen_all:
group = []
visit(person, seen_all, group)
groups += 1
print(f"Group {groups}: " + ", ".join(group))
Depth-first from Ava: Ava, Ben, Dev, Cara, Eli, Fay
Group 1: Ava, Ben, Dev, Cara, Eli, Fay
Group 2: Gus, Hana
const network = new Map([
["Ava", ["Ben", "Cara"]],
["Ben", ["Ava", "Dev"]],
["Cara", ["Ava", "Dev"]],
["Dev", ["Ben", "Cara", "Eli"]],
["Eli", ["Dev", "Fay"]],
["Fay", ["Eli"]],
["Gus", ["Hana"]],
["Hana", ["Gus"]],
]);
function visit(person, seen, order) {
seen.add(person);
order.push(person);
for (const friend of network.get(person)) {
if (!seen.has(friend)) {
visit(friend, seen, order);
}
}
}
const fromAva = [];
visit("Ava", new Set(), fromAva);
console.log(`Depth-first from Ava: ${fromAva.join(", ")}`);
const seenAll = new Set();
let groups = 0;
for (const person of network.keys()) {
if (!seenAll.has(person)) {
const group = [];
visit(person, seenAll, group);
groups++;
console.log(`Group ${groups}: ${group.join(", ")}`);
}
}
Depth-first from Ava: Ava, Ben, Dev, Cara, Eli, Fay
Group 1: Ava, Ben, Dev, Cara, Eli, Fay
Group 2: Gus, Hana
const network = new Map<string, string[]>([
["Ava", ["Ben", "Cara"]],
["Ben", ["Ava", "Dev"]],
["Cara", ["Ava", "Dev"]],
["Dev", ["Ben", "Cara", "Eli"]],
["Eli", ["Dev", "Fay"]],
["Fay", ["Eli"]],
["Gus", ["Hana"]],
["Hana", ["Gus"]],
]);
function visit(person: string, seen: Set<string>, order: string[]): void {
seen.add(person);
order.push(person);
for (const friend of network.get(person) ?? []) {
if (!seen.has(friend)) {
visit(friend, seen, order);
}
}
}
const fromAva: string[] = [];
visit("Ava", new Set<string>(), fromAva);
console.log(`Depth-first from Ava: ${fromAva.join(", ")}`);
const seenAll = new Set<string>();
let groups = 0;
for (const person of network.keys()) {
if (!seenAll.has(person)) {
const group: string[] = [];
visit(person, seenAll, group);
groups++;
console.log(`Group ${groups}: ${group.join(", ")}`);
}
}
Depth-first from Ava: Ava, Ben, Dev, Cara, Eli, Fay
Group 1: Ava, Ben, Dev, Cara, Eli, Fay
Group 2: Gus, Hana
Try it. Swap the order of Ava's friends to Cara, Ben and run it again. The visit order becomes Ava, Cara, Dev, Ben, Eli, Fay: DFS's order depends on which way it tries first, but it still finds everyone in the group.
Recursion or your own stack
Every unfinished visit call waits on the call stack, and that pile of waiting calls is the trail of forks to back up through. A very long path, say a chain of 100,000 people, would make 100,000 calls wait at once, and the program can run out of call-stack space (Python stops at about 1,000 by default). For graphs that deep, the same search is written as a loop with a stack of your own: push the start, then pop a person, mark them, and push their friends not yet seen. Breadth-first search with its queue swapped for a stack is depth-first search.
Which search for which job
Both searches visit everything the start can reach, so for Ava's circle either one is right. What tips the choice is the rest of the job:
| The job | Use | Why |
|---|---|---|
| The fewest steps, hops or transfers | Breadth-first | It finishes each level before the next, so the first route it finds is the shortest |
| Friends exactly two steps away | Breadth-first | Levels are its whole idea |
| Can I get from here to there at all? | Either | Both visit everything reachable |
| Find every separate group | Either (DFS is the usual) | Each search from an unseen vertex is one group, and the recursive version is shortest |
| Explore every possible path, as in a maze or a puzzle | Depth-first | It finishes one path before starting another, and backing up is built in |
Cost card
| What it does | Big-O | The everyday reason |
|---|---|---|
| Visit every vertex the start can reach | O(V + E) time | Each person is visited once, and each friendship is looked at from both ends |
| Remember the trail and who's seen | O(V) memory | At worst every person is waiting on the trail at once, and everyone seen is in the set |
| Find every group | O(V + E) time | One search per group, and nobody is visited twice across all of them |
Check yourself
2 questions to try on the lesson page.
So what
You now have both ways to explore a graph: breadth-first when "how many steps?" matters, depth-first when you need to go everywhere or try every path. Both need chalk marks, because a graph, unlike a tree, can lead you back to where you started.