Graph DFS

Picture a treasure hunt at your school's annual fest. The first clue is taped to the notice board and says "go to the library." You run there and find a second clue pointing to the physics lab. From the lab, a third clue points to the auditorium. You keep charging forward, clue after clue, corridor after corridor, always chasing the newest lead as deep as it goes — until you reach a door with no clue behind it. A dead end. What do you do? You do not start the hunt over. You walk back to the last place that had an unopened door you skipped, and you try that one instead.

That instinct — go as deep as possible along one path, and only step back when you are truly stuck — is not just treasure-hunt logic. It is a precise, provable algorithm called Depth-First Search (DFS), and it is one of the two fundamental ways to systematically visit every point in a network of connections (the other being Breadth-First Search, which explores in rings outward instead of plunging deep first). This chapter builds DFS for graphs specifically — networks that can loop back on themselves — from the ground up, in code you can run and trust.

From Corridors to Graphs: Nodes and Edges

Strip away the treasure-hunt story and what is left is a set of locations and a set of direct connections between them. In computer science we call a location a vertex (or node) and a direct connection an edge. A collection of vertices joined by edges is a graph. Your school building is a graph: rooms are vertices, corridors connecting them are edges. A road map is a graph: towns are vertices, roads are edges. A WhatsApp group's "who has whose number saved" relationship is a graph too. We store a graph in code as an adjacency list — for every vertex, a list of the vertices directly reachable from it. Imagine a (simplified, made-up-for-this-lesson) loop of six cities you could road-trip through north India: Delhi connects to Agra and Jaipur; Agra connects onward to Mathura; Jaipur connects onward to Alwar; and Mathura and Alwar both connect to Bharatpur, closing the loop. In Python, a dictionary is a natural fit:

cities = {
    'Delhi':     ['Agra', 'Jaipur'],
    'Agra':      ['Delhi', 'Mathura'],
    'Jaipur':    ['Delhi', 'Alwar'],
    'Mathura':   ['Agra', 'Bharatpur'],
    'Alwar':     ['Jaipur', 'Bharatpur'],
    'Bharatpur': ['Mathura', 'Alwar']
}

Notice something important: the connection is listed both ways. Delhi's list contains Agra, and Agra's list also contains Delhi. That is because this is an undirected graph — a road you can drive in either direction. If instead each entry only pointed one way (like one-way streets, or "A follows B" on social media), we would call it a directed graph. DFS works on both, but every example in this chapter is undirected, matching the two-way roads on our map.

Six cities, six roads — and if you trace them, Delhi → Agra → Mathura → Bharatpur → Alwar → Jaipur → back to Delhi forms a complete loop, or what graph theory calls a cycle. That loop is not decoration — it is the entire reason DFS on a graph needs one more ingredient than DFS on a simpler structure like a family tree.

Why a Tree Trick Fails on a Loop

If you have ever traced through a family tree or a folder structure, you have informally done depth-first traversal already: start at the root, dive into the first child, dive into its first child, and so on, backing up only when a branch has no more children. That works perfectly for trees because a tree, by definition, has no cycles — you can never loop back to an ancestor by following child links forward.

A general graph gives you no such guarantee. Look again at our six-city loop. Suppose you naively wrote "visit a city, then visit every neighbour" with no memory of where you had already been. Starting at Delhi, you would go to Agra, then Mathura, then Bharatpur, then Alwar, then Jaipur — and then Jaipur's neighbour list says "go to Delhi." With no memory, you would visit Delhi again, then Agra again, then Mathura again — forever. A cycle turns a naive depth-first walk into an infinite loop.

The fix is a single extra piece of bookkeeping: a visited set. Before stepping into any city, DFS checks "have I already been here?" If yes, that path is abandoned immediately — no re-visit, no re-exploration of what lies beyond it. This one check is what separates "DFS on a tree" (easy, no cycles possible) from "DFS on a graph" (needs a visited check, because cycles are possible). Forgetting it is the single most common bug when students move from tree traversal to graph traversal.

Walking Through DFS by Hand

Let's trace DFS on the six-city loop by hand, starting at Delhi, always trying a city's first unvisited neighbour before backtracking.

Every one of the six cities got visited exactly once, and the loop-closing road from Jaipur back to Delhi was correctly recognised and skipped. That single skip is the visited check doing its job — without it, step 6 would have restarted the entire chain.

DFS in Code: The Recursive Version

The hand trace above has a repeating shape: visit a city, mark it, then for its very first unvisited neighbour, do the exact same thing again. "Do the exact same thing again, on a smaller version of the problem" is precisely what a recursive function is built for. Each recursive call handles one city; the neighbours it hasn't explored yet become recursive calls of their own; and returning from a call is exactly the "backtrack" step.

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited, order)
    return order

cities = {
    'Delhi':     ['Agra', 'Jaipur'],
    'Agra':      ['Delhi', 'Mathura'],
    'Jaipur':    ['Delhi', 'Alwar'],
    'Mathura':   ['Agra', 'Bharatpur'],
    'Alwar':     ['Jaipur', 'Bharatpur'],
    'Bharatpur': ['Mathura', 'Alwar']
}

print(dfs_recursive(cities, 'Delhi'))
# ['Delhi', 'Agra', 'Mathura', 'Bharatpur', 'Alwar', 'Jaipur']

Read the function like the table above, line by line. visited.add(node) and order.append(node) are the "mark and record" step. The for loop walks through graph[node] in list order — which is exactly why Agra, not Jaipur, gets visited second: Agra is listed first in cities['Delhi']. Inside the loop, if neighbour not in visited is the entire cycle-safety mechanism in one line. When a call's loop finishes without finding any unvisited neighbour, Python's own call stack pops that call off — that automatic "return to whoever called me" behaviour is the backtracking; you never had to write it explicitly. Run the trace: Delhi calls dfs for Agra, which calls dfs for Mathura, which calls dfs for Bharatpur, which calls dfs for Alwar, which calls dfs for Jaipur, which finds no unvisited neighbour and returns; that return unwinds five call frames in a row, each one finding no further unvisited neighbour, until we're back in Delhi's own loop, which then checks Jaipur, sees it's visited, and finishes. The output matches our hand trace exactly.

DFS in Code: The Iterative Version, and a Subtle Gotcha

Recursion is really the computer maintaining a hidden stack of "calls I still need to finish" for you. You can make that stack explicit yourself with a Python list used as a stack (add to the end with append, remove from the end with pop — last in, first out, exactly like a stack of exam papers where you always take from the top):

def dfs_iterative(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in visited:
                stack.append(neighbour)
    return order

print(dfs_iterative(cities, 'Delhi'))
# ['Delhi', 'Agra', 'Mathura', 'Bharatpur', 'Alwar', 'Jaipur']

Two design choices here reward close reading. First, the neighbours are pushed in reversed order. A stack pops whatever was pushed last, so if we want Agra explored before Jaipur (matching the recursive version's order, where the first listed neighbour is tried first), we must push Jaipur first and Agra last, so Agra sits on top and gets popped first. Trace it: from Delhi, reversed(['Agra', 'Jaipur']) gives ['Jaipur', 'Agra']; we push Jaipur, then push Agra; Agra is now on top and pops next. Get this backwards and your iterative DFS will still be a valid DFS — just visiting neighbours in a different order than the recursive one.

Second, notice the code checks if node in visited: continue right after popping — not only before pushing. This looks redundant, but trace what happens at Alwar: Alwar's neighbours are Jaipur and Bharatpur. Bharatpur is already visited by that point, so we skip pushing it. But Jaipur is not yet visited, so we push it — even though Jaipur is already sitting in the stack from the very first step (Delhi pushed it back at step 1, and it has been waiting under everything else this whole time). Now the stack briefly holds two separate entries for Jaipur. When we pop the first one, we visit Jaipur and record it. When we later pop the second, leftover one, the if node in visited: continue check catches it and throws it away with no side effects. Without that check-on-pop, Jaipur would be recorded twice in order — not an infinite loop, since the stack is still finite, but a wrong answer. This is the single most common bug in hand-rolled iterative graph DFS: checking "have I visited this?" only when deciding what to push, and forgetting to check again when deciding what to actually process.

Two Misconceptions Worth Correcting Now

Misconception 1: "DFS visits nodes level by level, closest ones first." That description belongs to Breadth-First Search, not DFS. DFS does the opposite: it commits to one path and rides it as far as it possibly can before considering any alternative, even a much shorter one sitting right next to the start. In our example, DFS from Delhi visits all five other cities, going all the way around the loop, before it ever "returns" to check Delhi's second neighbour. A student who has learned BFS first sometimes assumes "traversal" always spreads outward in rings; DFS's entire identity is that it does not.

Misconception 2: "If tree traversal didn't need a visited set, graph traversal doesn't either." This is exactly backwards, and it is the bug that produces an infinite loop the very first time a student's graph code meets a graph with a cycle. A tree is a special graph that happens to have no cycles, so a naive walk can never revisit a node by following forward links. The moment your structure has even one cycle — and road networks, friendship networks, and most real-world graphs are full of them — forward-only traversal can walk in circles forever. The visited set is not an optional optimisation for graphs; it is what makes the algorithm terminate at all.

How Much Work Does DFS Do?

Look again at the trace: DFS visited each of the 6 cities exactly once (that's the "mark and record" step), and for each city, it scanned through its full neighbour list once looking for an unvisited one. Our loop has 6 roads, and because each road is listed in both endpoints' adjacency lists, the neighbour lists across all six cities contain 12 entries in total. So the whole run does 6 node-visits plus 12 neighbour-checks — 18 basic steps for a graph with 6 vertices and 6 edges. In general, if a graph has V vertices and E edges, DFS visits each vertex once and inspects each edge at most twice (once from each end), giving a running time of O(V + E) — proportional to the size of the graph, not to anything larger. This is why DFS is considered efficient: doubling the number of roads roughly doubles the work, it never explodes. A campus map with 50 buildings and 120 corridors would take DFS on the order of 50 + 120 = 170 basic steps to visit every reachable building — nowhere close to the 50 × 120 = 6,000 steps a much less efficient method might take.

What This Actually Gets Used For

DFS is not just a hand-tracing exercise; the same "mark and dive" idea solves several concrete problems once you frame them as graphs. Reachability and connected components: if a district wants to check whether every village is reachable by road from the district headquarters, running DFS from the headquarters and checking whether every village ended up in the visited set answers it directly — any village left unvisited has no road path in. Cycle detection: while running DFS, if you ever reach a neighbour that is already visited and is not the vertex you just came from, you have found a cycle; this is exactly how tools detect circular dependencies, like two Python modules that each try to import the other. Maze and puzzle solving: a maze is a graph where junctions are vertices and corridors are edges, and "follow one path fully before trying another" is literally DFS with the visited set preventing you from re-entering a corridor you've already tried. Exploring nested folders: a file explorer that opens a folder, then opens the first sub-folder inside it, then the first sub-folder inside that, before ever looking at sibling folders, is performing DFS on the folder tree (a tree being a cycle-free graph, so it needs no visited set at all).

Check Your Understanding

Here is a second, unrelated graph — six buildings on a college campus, connected by covered walkways:

campus = {
    'Gate':          ['Library', 'Canteen'],
    'Library':       ['Gate', 'Lab'],
    'Canteen':       ['Gate', 'Auditorium', 'SportsComplex'],
    'Lab':           ['Library'],
    'Auditorium':    ['Canteen', 'SportsComplex'],
    'SportsComplex': ['Canteen', 'Auditorium']
}

Try each question yourself before opening the answer.

Summary

• A graph is a set of vertices (nodes) joined by edges; we store it in code as an adjacency list, a dictionary mapping each vertex to the list of vertices directly reachable from it.
• Depth-First Search explores by committing to one neighbour and diving as deep as possible along that path before trying any alternative, backtracking only when a path runs out of unvisited neighbours.
• Because graphs (unlike trees) can contain cycles, DFS must maintain a visited set and check it before entering any vertex — without this check, a cycle causes an infinite loop.
• DFS can be written recursively (the function call stack does the backtracking for you) or iteratively with an explicit stack list (where you must remember to re-check "visited" both when pushing and when popping, since the same vertex can end up pushed more than once).
• DFS runs in O(V + E) time — proportional to the number of vertices plus the number of edges — because it visits each vertex once and inspects each edge at most twice.
• DFS is not just a tracing exercise: it directly powers reachability checks (is every village connected to the district HQ?), cycle detection (circular software dependencies), maze-solving, and depth-first folder exploration.