Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a selected node (or an arbitrary node for a disconnected graph) and explores as far as possible along each branch before backtracking.

DFS is often implemented using a stack (either explicitly with a stack data structure or implicitly with recursion). It's useful for problems like finding connected components, cycle detection, and topological sorting. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

DFS Traversal (Graph)

Step 1 of 0

Action

Ready to start

Current Node

None

Stack

[]

Traversal Order

[]

Start Node

Current Node

Visited

In Stack

Unvisited

Traversed Edge

Depth-First Search (DFS) for Graphs

Depth-First Search (DFS) in graphs explores as far as possible along each branch before backtracking. It's useful for pathfinding, cycle detection, and topological sorting.

Algorithm Steps (Recursive)

Create a set to store visited nodes.
Start the traversal from a given node.
Mark the current node as visited and process it.
For each of its unvisited neighbors, recursively call the DFS function.
If the graph is disconnected, repeat the process for all unvisited nodes.

Graph DFS


def dfs(graph, start_node):
    visited = set()
    result = []

    def _dfs_recursive(node):
        visited.add(node)
        result.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                _dfs_recursive(neighbor)

    _dfs_recursive(start_node)
    return result