Depth-First Search (DFS) Theory Guide

Rules & Common Mistakes

• Exam Trap: Pulling from the Front Turns DFS into BFS

  This is the single fastest way to lose all traversal marks on a DFS question. The Stack is a Last-In-First-Out structure — the node that was added most recently must always be the first one popped. The moment a node is pulled from the bottom or front of the list instead of the top, the algorithm silently becomes BFS and every subsequent step produces the wrong traversal order. Always mark the top of the Stack clearly on the exam paper and cross off nodes strictly from that end.
• Exam Trap: Pushing Neighbours in Alphabetical Order Instead of Reverse

  When a node has multiple new neighbours to push, the order they enter the Stack determines which one gets processed first. Since DFS pops from the top, the neighbour that should be explored first must be the last one pushed — meaning neighbours must be pushed in reverse alphabetical order. If A, B, and C are all neighbours, push C first, then B, then A. A ends up on top and gets popped next. Pushing in straight alphabetical order puts the wrong node on top and produces a trace that will not match the grading rubric.
• Exam Trap: Stalling When a Popped Node Has No New Neighbours

  Students often freeze when they pop a node and find that every one of its neighbours is already in the `closedList`. This feels like a dead end, but it is not an error — it is backtracking working exactly as intended. There is nothing to calculate and no decision to make. Simply move the dead-end node to the `closedList` and pop whatever is sitting on top of the Stack next. The Stack automatically returns the algorithm to the most recent unfinished branching point.
• Exam Trap: Forgetting the Closed List Check and Looping Forever

  On any graph with cycles — where edges can lead back to a node already visited — DFS will get trapped in an infinite loop if the `closedList` is not checked before pushing a neighbour. Without that check, the algorithm will keep rediscovering and re-pushing the same nodes indefinitely. Before pushing any neighbour onto the Stack, always verify it is not already in the `closedList`. If it is already there, skip it completely and move to the next neighbour.

Strengths, Weaknesses & When To Use It

When to use it:Reach for DFS whenever the goal is exhaustive exploration rather than optimal routing. It is the right tool for cycle detection, topological sorting, finding all connected components in a network, and navigating deep structures where any valid path is acceptable. DFS is also the memory champion — if a graph is too wide for BFS to fit its entire frontier into RAM, DFS can traverse the same graph using a fraction of the memory. The one scenario where DFS should never be used is shortest-path problems — it has no mechanism to guarantee the first path it finds is the cheapest or most efficient one.

Depth-First Search vs. Breadth-First Search

Breadth-First Search and DFS are opposite personalities built from the same skeleton. Both maintain an `openList` and a `closedList`, both expand neighbours one at a time, and both terminate when the goal is found. The entire difference between them comes down to a single data structure swap: BFS uses a Queue to sweep cautiously outward level by level, while DFS uses a Stack to plunge recklessly down one branch at a time. One prioritizes finding the shortest path; the other prioritizes getting somewhere deep with as little memory as possible.

• The Mechanics — Queue vs. Stack: BFS uses a First-In-First-Out Queue, so the oldest discovered node always gets processed next — this creates the level-by-level ripple. DFS uses a Last-In-First-Out Stack, so the most recently discovered node always gets processed next — this creates the deep plunge. Swap the data structure and the traversal order changes completely. The rest of the algorithm is identical.
• Optimality Guarantee — Shortest Path vs. Any Path: BFS guarantees the shortest unweighted path because it reaches every node via the fewest possible edges before going deeper. DFS makes no such guarantee — it returns the first complete path it finds, which is often a long, winding route that ignores a much shorter alternative sitting on a nearby branch. DFS is memory-optimal, not path-optimal.
• Memory Complexity — $O(b^d)$ vs. $O(bm)$: BFS must store every node on the current level in memory simultaneously, giving it $O(b^d)$ space complexity that explodes exponentially on wide graphs. DFS only stores the active path from root to the current node, giving it $O(bm)$ space complexity where $m$ is the maximum depth. On a graph too wide for BFS to fit in RAM, DFS can traverse the same structure using a fraction of the memory.
• Exam Strategy — What the Grader Actually Wants: When asked to trace both algorithms on the same graph, the examiner is checking two things. First, can the Stack and Queue mechanics be correctly applied without mixing them up? Second, is there an explicit written statement identifying that BFS found the shortest path while DFS found the first path — and that the reason they differ is the data structure, not arbitrary chance? Writing that explanation is often the difference between full marks and partial marks.

Implementation Pseudocode

// DFS maintains two structures throughout the entire search
// openList  = a strict LIFO Stack — the most recently added node is always popped first
// closedList = a visited set — nodes here are permanently processed and never revisited
// There are no scores, no heuristics, and no math — just Stack order

function DFS(startNode, goalNode):

    // ── INITIALIZATION ──────────────────────────────────────────────────

    // Push the start node onto the top of the Stack to begin the search
    // The closedList starts empty — nothing has been visited yet
    openList   = [startNode]
    closedList = []


    // ── MAIN LOOP ────────────────────────────────────────────────────────

    while openList is not empty:

        // EXAM TRAP — Always pop from the TOP of the Stack
        // Popping from the FRONT or BOTTOM turns the Stack into a Queue — that is BFS, not DFS
        // The most recently added node always gets processed next
        current = openList.popTop()

        // Goal check happens HERE, immediately after popping from the Stack
        // This keeps termination logic consistent with BFS, A*, UCS, and Greedy Search
        if current == goalNode:
            return reconstruct_path(current)  // trace parent pointers back to start

        // Move current to the closedList — it is permanently processed
        // It will never be pushed onto the Stack again
        add current to closedList


        // ── EXPAND NEIGHBOURS ───────────────────────────────────────────

        // EXAM TRAP — Add neighbours in REVERSE alphabetical order
        // Because the Stack is LIFO, the last node pushed ends up on top
        // Pushing Z before A means A sits on top and gets processed first
        // This ensures the alphabetically first neighbour is always explored next
        for each neighbour in getNeighbours(current) in REVERSE alphabetical order:

            // Skip neighbours already fully processed — they are permanently settled
            if neighbour is in closedList:
                continue

            // Skip neighbours already waiting in the Stack — no updates needed
            // Unlike A* or UCS, there is no g(n) to recalculate — DFS is completely blind to cost
            if neighbour is in openList:
                continue

            // Brand new node — record its parent and push it onto the TOP of the Stack
            // Pushing to the top is what forces DFS to plunge deep into this branch immediately
            neighbour.parent = current
            openList.pushTop(neighbour)

    // openList is empty and goal was never popped — no path exists in this graph
    return failure


// ── INITIAL CALL ─────────────────────────────────────────────────────
// DFS(startNode, goalNode)

Time & Space Complexity

DFS Exam Questions Students Always Get Wrong

• I pulled the node from the front of my openList instead of the top. Does that matter?

  It matters enormously — that single mistake transforms DFS into BFS. DFS is defined by the LIFO Stack: the most recently added node must always be the first one removed. Pulling from the front processes the oldest node first, which is exactly what a Queue does. Every subsequent step of the trace will follow BFS traversal order, and every mark awarded for DFS behaviour will be lost.

• Why do I have to push neighbours in reverse alphabetical order? It feels backwards.

  Because the Stack is LIFO, whatever goes on last comes off first. If A, B, and C all need to be pushed, pushing C first then B then A leaves A sitting on top — so A gets popped and processed next. Pushing in straight alphabetical order puts C on top instead, which produces a different traversal order that will not match the grading rubric.

• I popped a node and none of its neighbours are new — they are all in the closedList. Did I break something?

  Nothing is broken — this is backtracking working exactly as designed. When a popped node has no new neighbours to push, simply move it to the `closedList` and pop whatever is sitting on top of the Stack next. The Stack automatically returns the algorithm to the most recent unfinished branching point. There is no manual calculation required and nothing to fix.

• What actually happens if I forget to use a closedList on a graph that has cycles?

  The algorithm enters an infinite loop and never terminates. Without a `closedList`, DFS will pop a node, push its neighbours including one it already visited, and then pop that visited node again — rediscovering the same cycle endlessly. On an exam, forgetting the `closedList` on a cyclic graph means the trace can never reach a valid termination condition.

• Does DFS find the shortest path on a weighted graph if I follow the edge weights?

  No — DFS is completely blind to edge weights regardless of what values are written on the graph. It follows Stack order, not cost order, which means the first path it finds is determined entirely by traversal sequence. That path is almost never the cheapest one. For shortest paths on weighted graphs, the correct tools are Uniform Cost Search or A*.