DSA — Depth First Search

What is DFS?

Explores as far as possible along each branch before backtracking.

# Recursive
def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(vertex)
    print(vertex)
    
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Iterative
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

Time Complexity

Operation	Complexity
Visit all vertices	O(V + E)
Space	O(V)

Applications

• Cycle detection
• Topological sorting
• Path finding
• Connected components

Mini Practice

1. Implement recursive DFS
2. Implement iterative DFS
3. Detect cycles
4. Find connected components

Up Next

Continue with Breadth First Search — BFS algorithm.