What is DFS in Graph: Explanation, Example, and Uses

DFS (Depth-First Search) is a graph traversal method that explores as far as possible along each branch before backtracking. It uses a stack-like approach to visit nodes deeply before moving to neighbors.

How It Works

Depth-First Search (DFS) starts at a chosen node and explores one path fully before moving to another. Imagine walking through a maze by always taking the first unexplored path until you reach a dead end, then backtracking to try other paths.

DFS uses a stack structure, either explicitly or via recursion, to remember where to return after reaching the end of a path. This way, it visits nodes deeply and backtracks only when necessary, ensuring every node connected to the start is visited.

Example

This example shows DFS on a simple graph represented by an adjacency list. It prints nodes in the order they are visited.

python

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Graph represented as adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

Output

A B D E F C 

When to Use

DFS is useful when you need to explore all possible paths deeply, such as solving puzzles, maze navigation, or checking connectivity in networks. It helps find paths, detect cycles, and classify edges in graphs.

For example, DFS can be used in social networks to find friend groups, in file systems to list all files in folders, or in games to explore moves deeply.

Key Points

• DFS explores graph nodes by going deep before backtracking.
• It uses a stack or recursion to keep track of nodes.
• Useful for pathfinding, cycle detection, and connectivity checks.
• Works well on both directed and undirected graphs.

Key Takeaways

DFS explores graph nodes deeply before backtracking to explore other paths.

It uses recursion or a stack to remember where to return after reaching dead ends.

DFS is ideal for tasks like pathfinding, cycle detection, and connectivity checks.

It works on both directed and undirected graphs.

DFS helps solve real-world problems like maze navigation and social network analysis.