Depth-First Search

Explores as deep as possible along each branch before backtracking, using recursion or an explicit stack.

Complexity

Time (Worst)

O(V + E)

Space

O(V)

Key Points

›Explores one path completely before exploring alternatives
›Can be implemented recursively (call stack) or with an explicit stack
›O(V) space for the recursion stack in the worst case (path graph)
›Does not guarantee shortest path — use BFS for that
›Applications: topological sort, cycle detection, connected components, maze solving

Code Examples

Swift

func dfs(graph: [Int: [Int]], start: Int) -> [Int] {
    var visited = Set<Int>()
    var result  = [Int]()

    func explore(_ node: Int) {
        visited.insert(node)
        result.append(node)
        for neighbor in graph[node] ?? [] where !visited.contains(neighbor) {
            explore(neighbor)
        }
    }

    explore(start)
    return result
}

let graph = [0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]]
print(dfs(graph: graph, start: 0))  // [0, 1, 3, 4, 2, 5]

Practice Problems

Number of Islands

MediumLeetCode ↗

Clone Graph

MediumLeetCode ↗

Path Sum

EasyLeetCode ↗

Course Schedule II

MediumLeetCode ↗