Depth-First Search

Explore as deep as possible before backtracking; uses recursion or a stack.

Intermediate

def dfs(graph, node, seen=None):
    seen = seen or set()
    seen.add(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(graph, nxt, seen)
    return seen

Also $O(V + E)$ . DFS detects cycles, finds connected components and produces a topological order — e.g. the order to build files with dependencies.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)