DSA — Graph Algorithms

DFS Depth-First Search

Explore deep into a branch before backtracking. Uses a stack (explicit or implicit recursion). Essential for connectivity, cycles, and mazes.

— min read
O(V+E)Time
O(V)Space
BacktrackPrinciple
StackDFS Uses
TopoSort / Cycle
// DFS VISUALIZATION
Initialize to see DFS in action.
How It Works
Python Code
Complexity
Quiz
Practice
01
Start Node
Push the starting node onto the stack and mark it visited.
02
Dive Deep
Pop a node, visit it, and push all unvisited neighbors onto the stack.
03
Backtrack
When a branch is exhausted, return to the previous node on the stack and continue.
python 
def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        print(node, end=" ")

        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
O(V+E)
Time
Each vertex and edge visited once
O(V)
Space
Stack depth up to V in worst case
LIFO
Stack
Last-in-first-out exploration
DFS vs BFS
Use Case
DFS for paths & cycles; BFS for shortest unweighted paths
DFS uses which data structure?
Progress 0 / 5 solved
5 problems · 3 PBC · 2 Startup
#133 Clone Graph Google PBC →
#200 Number of Islands Amazon PBC →
#1219 Path with Maximum Gold Meta PBC →
#130 Surrounded Regions Zomato STARTUP →
#79 Word Search Cogoport STARTUP →
← BFS Traversal