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)