BFS & DFS on Graphs

Two essential traversal strategies, and when to use each

BFS (Breadth-First Search): Explore level by level. Uses a queue. Finds shortest path in unweighted graphs.
DFS (Depth-First Search): Explore as deep as possible before backtracking. Uses a stack (or recursion). Better for detecting cycles, finding all paths, topological sort.
Both are O(V + E), they visit every vertex and edge once.

BFS, shortest path in unweighted graphpython

from collections import deque

def shortest_path(graph, start, end):
    if start == end: return 0
    visited = {start}
    queue = deque([(start, 0)])  # (node, distance)

    while queue:
        node, dist = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1  # No path

graph = {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2,4], 4: [3]}
print(shortest_path(graph, 0, 4))  # → 3

DFS, detect cycle in directed graphpython

def has_cycle(graph, n):
    # 0 = unvisited, 1 = in current path, 2 = fully processed
    state = [0] * n

    def dfs(node):
        state[node] = 1  # Mark as "in progress"
        for neighbor in graph.get(node, []):
            if state[neighbor] == 1:  # Back edge → cycle!
                return True
            if state[neighbor] == 0 and dfs(neighbor):
                return True
        state[node] = 2  # Fully processed
        return False

    return any(dfs(i) for i in range(n) if state[i] == 0)

# 0→1→2→0 forms a cycle
graph = {0:[1], 1:[2], 2:[0]}
print(has_cycle(graph, 3))  # → True

🤔Quick Check

You need to find the minimum number of moves to solve a puzzle. Which traversal?

🎯

Phase Complete!

Graphs

Graphs mastered! BFS for shortest paths, DFS for exploration and cycle detection. Dynamic programming is next, arguably the hardest and most rewarding topic.

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1hard

⏱ 00:00

Course Schedule (Topological Sort)

Given n courses and prerequisites [[a,b] = "a requires b"], determine if you can finish all courses (no circular dependencies).
Expected output: True

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next