DSA — DFS

What is DFS?

DFS explores as far as possible along each branch before backtracking.

# Recursive
def dfs_recursive(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_recursive(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)

DFS for Cycle Detection

def has_cycle(graph):
    visited = set()
    recursion_stack = set()
    
    def dfs(vertex):
        visited.add(vertex)
        recursion_stack.add(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in recursion_stack:
                return True
        
        recursion_stack.remove(vertex)
        return False
    
    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex):
                return True
    return False

Time Complexity

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

Mini Practice

1. Implement recursive DFS
2. Implement iterative DFS
3. Detect cycles
4. Topological sort with DFS

Up Next

Continue with Linear Search — simple search algorithm.