Graph Traversal: Depth-First Search

Depth-First Search (DFS) is the second fundamental graph traversal algorithm. While BFS explores level by level, DFS explores as deep as possible along each branch before backtracking. DFS uses a stack (LIFO) — either explicitly or implicitly through recursion.

---

How DFS Works

Starting from a source vertex, DFS follows this strategy:

1. Visit the starting vertex and mark it as visited.
2. Move to an unvisited neighbour and repeat.
3. If all neighbours of the current vertex have been visited, backtrack to the previous vertex.
4. Continue until all reachable vertices have been visited.

DFS goes as deep as possible before backtracking — it follows one path all the way to the end before trying another.

---

Pseudocode (Recursive)

PROCEDURE DFS(graph, v, visited)
    ADD v TO visited
    OUTPUT v
    FOR EACH neighbour OF v IN graph
        IF neighbour NOT IN visited THEN
            DFS(graph, neighbour, visited)
        END IF
    END FOR
END PROCEDURE

To start: DFS(graph, startVertex, emptySet)

Pseudocode (Iterative with Stack)

PROCEDURE DFS_Iterative(graph, start)
    CREATE stack
    CREATE visited set
    PUSH start
    WHILE stack IS NOT EMPTY
        v = POP
        IF v NOT IN visited THEN
            ADD v TO visited
            OUTPUT v
            FOR EACH neighbour OF v IN graph (in reverse order)
                IF neighbour NOT IN visited THEN
                    PUSH neighbour
                END IF
            END FOR
        END IF
    END WHILE
END PROCEDURE

Note: The iterative version pushes neighbours in reverse order so that the first neighbour in the adjacency list is processed first (matching the recursive version).

---

Trace Example

Consider the same graph as the BFS lesson:

    A --- B --- E
    |         |
    C --- D ---+

Adjacency list:

A: [B, C]
B: [A, E, D]
C: [A, D]
D: [B, C, E]
E: [B, D]

Recursive DFS Trace from A

Call	Current	Action	Visited
DFS(A)	A	Visit A. Neighbour B is unvisited → recurse	{A}
DFS(B)	B	Visit B. Neighbour E is unvisited → recurse	{A, B}
DFS(E)	E	Visit E. Neighbour D is unvisited → recurse	{A, B, E}
DFS(D)	D	Visit D. Neighbour C is unvisited → recurse	{A, B, E, D}
DFS(C)	C	Visit C. All neighbours visited → backtrack	{A, B, E, D, C}
back to D	D	All neighbours visited → backtrack
back to E	E	All neighbours visited → backtrack
back to B	B	All neighbours visited → backtrack
back to A	A	All neighbours visited → done

DFS order: A, B, E, D, C

Compare with BFS order: A, B, C, E, D. DFS went deep (A→B→E→D→C) while BFS went wide (A→B,C→E,D).

---

Properties of DFS