Uninformed search

Depth-First Search (DFS)

Go as deep as you can, then back up and try the next path.

On the Sydney → London problem, Depth-First Search finds: Sydney → Colombo → Istanbul → London — total 23.5h.

The idea

Depth-First Search (DFS) is an uninformed search: it knows nothing about which direction the goal is in, so it just commits to one path and follows it as deep as possible. When it hits a dead end, it backtracks to the last place it had another choice and dives again. It's popular because it uses very little memory — it only needs to remember the single path it's currently on.

How it works

Put the start node into OPEN (the frontier of nodes waiting to be explored). CLOSED (already-explored nodes) starts empty.
If OPEN is empty, stop and report failure — there's nowhere left to search.
Take the node off the FRONT of OPEN (the most recently added one). Call it the current node.
If the current node is the goal, stop and report success — trace the path back.
Otherwise move the current node into CLOSED to mark it as explored.
Find the current node's children (neighbors). Skip any that are already in CLOSED or OPEN.
Add those children to the FRONT of OPEN, so the newest ones get explored next — this is what makes the search dive deep.
Repeat from step 2. Because newest nodes are taken first, DFS finishes one whole branch before backing up to try another.

See it step by step

Watch Depth-First Search search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Start at Sydney. OPEN (the frontier) holds just Sydney.

Expanding

OPEN — frontier

CLOSED — traversal

Path so far

Cost so far

Step 1 / 5

OPEN, CLOSED & the data structures

OPEN is a LIFO stack — Last In, First Out. New children are pushed onto the front and the next node pulled out is always the most recent one, which forces the search deeper before it ever backtracks. CLOSED is the set of nodes already expanded; it records the traversal order and, crucially, lets DFS avoid re-expanding nodes it has already seen so it doesn't loop forever on graphs with cycles.

Pseudocode

function DFS(start, goal):
    OPEN   = [start]          # a stack (LIFO); the frontier
    CLOSED = empty set        # already-expanded nodes

    while OPEN is not empty:
        node = OPEN.pop_front()        # take the newest node
        if node == goal:
            return reconstruct_path(node)   # success
        add node to CLOSED
        for each child of node:
            if child not in CLOSED and child not in OPEN:
                child.parent = node
                OPEN.push_front(child)      # push onto the stack
    return failure                      # OPEN emptied, no goal

At a glance

Complete?Not complete — on an infinite or cyclic graph it can dive down an endless branch and never come back to find a reachable goal.

Optimal?Not optimal — it returns the first goal its deep dive stumbles into, which may be far deeper and longer than a shallow goal it never bothered to check.

TimeO(b^m) — with branching factor b and maximum depth m, it may explore the whole tree in the worst case.

SpaceO(b*m) — very low. It only stores the current path plus each node's unexplored siblings, not the whole frontier like BFS does.

👍 When to use it

Memory is tight and the search space is deep — DFS's tiny footprint is its main strength.
Solutions are likely deep in the tree, or any valid path will do (you don't need the shortest one).
The graph is finite and you track CLOSED, so infinite dives and cycles aren't a danger.
You need a simple building block for other algorithms (e.g., Iterative Deepening layers depth limits on top of DFS).

⚠️ Watch out for

It is NOT complete on infinite or cyclic graphs — without a CLOSED set or depth limit it can loop or dive forever and miss an easy goal.
It is NOT optimal — the first goal found is rarely the shortest path; don't use plain DFS when path length matters.
The direction switch from BFS is subtle: BFS adds children to the BACK of OPEN (queue), DFS adds them to the FRONT (stack). One line, opposite behavior.
Always check CLOSED (and OPEN) before adding a child, or cycles will make you re-explore nodes endlessly.

Now see it for yourself

Open Depth-First Search in the visualizer — step through it, pause, and watch OPEN & CLOSED change.

▶ Watch it run