Strategy 1 — Breadth First: Start at the entrance. Visit every attraction within 5 minutes of the entrance. Then visit every attraction within 10 minutes. Work outward in rings. You will always find your group by the fastest route, because you check nearby areas before far ones. This is Breadth-First Search (BFS).

Strategy 2 — Depth First: Pick any path. Follow it all the way to its end before trying another one. Go deep into the roller coaster area, explore everything there, backtrack, then go deep into the food court area. You will eventually find your group, but not necessarily by the shortest route. This is Depth-First Search (DFS).

Both strategies visit every location. The difference is order — and that order determines what problems each algorithm solves best.

The Graph We Will Use

    A
   / \
  B   C
 / \   \
D   E   F

As an adjacency list:

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"]
}

BFS: Breadth-First Search

Core idea: Explore level by level. Use a queue — FIFO ensures we always process the node we discovered earliest, keeping us close to the starting point before going further.

BFS Implementation

def bfs(graph, start):
    visited = set()              # Track visited nodes to avoid infinite loops
    queue = deque([start])       # Initialize queue with the starting node
    visited.add(start)
    traversal_order = []

    while queue:
        node = queue.popleft()   # Process the OLDEST discovered node (front)
        traversal_order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:      # Only visit each node once
                visited.add(neighbor)
                queue.append(neighbor)       # Add to BACK of queue (discover later)

    return traversal_order

print("BFS from A:", bfs(graph, "A"))

Output:

BFS from A: ['A', 'B', 'C', 'D', 'E', 'F']

Step-by-step trace:

Step	Process	Queue After
1	A	[B, C]
2	B	[C, D, E]
3	C	[D, E, F]
4	D	[E, F]
5	E	[F]
6	F	[]

Notice that A and C are processed before D, E, and F — all level-1 nodes before level-2 nodes.

BFS: Shortest Path

BFS finds the shortest path (by number of edges) between two nodes in an unweighted graph. Since we explore level by level, the first time we reach the destination, we have taken the fewest possible steps.

def bfs_shortest_path(graph, start, end):
    visited = set([start])
    queue = deque([[start]])         # Queue holds PATHS, not just nodes

    if start == end:
        return [start]

    while queue:
        path = queue.popleft()       # Get the oldest path
        node = path[-1]              # Last node in this path

        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path          # Found the destination!
                visited.add(neighbor)
                queue.append(new_path)

    return None   # No path exists

print("Shortest path A→F:", bfs_shortest_path(graph, "A", "F"))
print("Shortest path A→E:", bfs_shortest_path(graph, "A", "E"))

Output:

Shortest path A→F: ['A', 'C', 'F']
Shortest path A→E: ['A', 'B', 'E']

def friends_within_degrees(graph, start, max_degrees):
    """Find all people within max_degrees connections of start."""
    visited = {start}
    queue = deque([(start, 0)])   # (person, degrees away)
    results = []

    while queue:
        person, degree = queue.popleft()
        if degree > 0:
            results.append((person, degree))

        if degree < max_degrees:
            for friend in graph.get(person, []):
                if friend not in visited:
                    visited.add(friend)
                    queue.append((friend, degree + 1))

    return results

social = {"Alice": ["Bob","Charlie"], "Bob": ["Alice","Diana","Eve"],
          "Charlie": ["Alice","Frank"], "Diana": ["Bob"],
          "Eve": ["Bob"], "Frank": ["Charlie"]}

print("People within 2 degrees of Alice:")
for person, deg in friends_within_degrees(social, "Alice", 2):
    print(f"  {person} ({deg} degree(s) away)")

Output:

People within 2 degrees of Alice:
  Bob (1 degree(s) away)
  Charlie (1 degree(s) away)
  Diana (2 degree(s) away)
  Eve (2 degree(s) away)
  Frank (2 degree(s) away)

DFS: Depth-First Search

Core idea: Go as deep as possible before backtracking. Use a stack (or recursion) — LIFO means we always continue down the most recently discovered path before exploring alternatives.

DFS Implementation — Recursive

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")              # Visit the node

    for neighbor in graph[node]:
        if neighbor not in visited:   # Only explore unvisited neighbors
            dfs_recursive(graph, neighbor, visited)
    return visited

DFS Implementation — Iterative

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]             # Use a stack — process most recently added first
    traversal_order = []

    while stack:
        node = stack.pop()      # Process the MOST RECENTLY discovered node (top)
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            for neighbor in reversed(graph[node]):  # Reverse to match recursive order
                if neighbor not in visited:
                    stack.append(neighbor)

    return traversal_order

print("DFS recursive from A:", end=" ")
dfs_recursive(graph, "A")
print()
print("DFS iterative from A:", dfs_iterative(graph, "A"))

Output:

DFS recursive from A: A B D E C F
DFS iterative from A: ['A', 'B', 'D', 'E', 'C', 'F']

Step-by-step trace (iterative):

Step	Pop	Stack After
1	A	[C, B]
2	B	[C, E, D]
3	D	[C, E]
4	E	[C]
5	C	[F]
6	F	[]

DFS goes all the way down B→D before coming back up for E and C.

DFS: Cycle Detection

DFS can detect cycles in a directed graph by tracking the current recursion path (the "call stack"):

def has_cycle(graph):
    visited = set()
    rec_stack = set()   # Nodes in the current DFS path

    def dfs(node):
        visited.add(node)
        rec_stack.add(node)    # Mark as part of current path

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True       # Cycle found deeper in recursion
            elif neighbor in rec_stack:
                return True           # Back edge found — cycle!

        rec_stack.remove(node)        # Done with this path — remove from rec stack
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

cyclic_graph = {"A": ["B"], "B": ["C"], "C": ["A"]}       # A→B→C→A — cycle!
acyclic_graph = {"A": ["B"], "B": ["C"], "C": []}          # No cycle

print("Cyclic graph has cycle:", has_cycle(cyclic_graph))    # True
print("Acyclic graph has cycle:", has_cycle(acyclic_graph))  # False

Output:

Cyclic graph has cycle: True
Acyclic graph has cycle: False

BFS vs DFS: When to Use Each

Feature	BFS	DFS
Data structure	Queue (FIFO)	Stack / Recursion (LIFO)
Traversal order	Level by level	As deep as possible first
Finds shortest path?	Yes (unweighted graphs)	No — not guaranteed
Memory usage	O(V) — can store many nodes	O(h) — only the current path depth
Good for	Shortest path, level-order	Cycle detection, topological sort
Complete?	Yes — always finds if reachable	Yes
Best for sparse graphs?	Both are O(V+E)	Both are O(V+E)

Time Complexity

Both BFS and DFS visit every vertex and every edge exactly once:

Time complexity: O(V + E) — V vertices and E edges
Space complexity: O(V) — visited set and the queue/stack

Real-World Applications

Algorithm	Application
BFS	Shortest path in GPS navigation
BFS	Social network: degrees of separation
BFS	Web crawlers: explore pages level by level
BFS	Finding all reachable nodes from a source
DFS	Maze solving: explore one path completely
DFS	Cycle detection in dependency graphs
DFS	Topological sorting (task ordering)
DFS	Finding connected components

Key Takeaway

BFS and DFS are the two fundamental strategies for exploring a graph. BFS fans outward, level by level, guaranteed to find the shortest unweighted path. DFS dives deep first, making it natural for cycle detection, topological sorting, and maze solving. Both run in O(V + E) time. The only choice is your data structure: a queue makes BFS, a stack (or recursion) makes DFS. Mastering both opens the door to nearly every graph algorithm in competitive programming and systems design.

Previous 🎉 View Course Summary

💬 DiscussionPowered by GitHub Discussions

📱

Get this course's notes on Telegram!

Free cheat sheets, summaries & practice exercises

Get Notes Free →

35 minLesson 17 of 17

Course Contents(17 lessons)

▾

Chapter 1: Why Data Structures Matter

What Are Data Structures and Why Do They Exist?20 min

Big O Notation: Measuring Code Efficiency30 min

Chapter 2: Arrays and Strings

Arrays: The Foundation of Everything25 min

Dynamic Arrays and How Python Lists Really Work25 min

2D Arrays and Matrices22 min

Chapter 3: Linked Lists

Singly Linked Lists: Nodes and Chains30 min

Doubly Linked Lists: Going Both Ways28 min

Chapter 4: Stacks and Queues

Stacks: Last In, First Out (LIFO)28 min

Queues: First In, First Out (FIFO)25 min

Deques and Priority Queues22 min

Chapter 5: Hash Tables

Hash Functions: Turning Keys Into Addresses30 min

Collision Handling and Python Dict Internals25 min

Chapter 6: Trees

Binary Trees: Hierarchical Data32 min

Binary Search Trees: Ordered Lookup35 min

Tree Traversal: In-Order, Pre-Order, Post-Order28 min

Chapter 7: Graphs

Graph Representations: Adjacency List vs Matrix30 min

BFS and DFS: Exploring Graphs Systematically35 min

Chapter 7: Graphs

BFS and DFS: Exploring Graphs Systematically

BFS and DFS: Graph Traversal Algorithms

Lost in a Theme Park

You are visiting a giant theme park and you have lost your group. You need to find them systematically — no random wandering, no retracing steps.

Both strategies visit every location. The difference is order — and that order determines what problems each algorithm solves best.

The Graph We Will Use

    A
   / \
  B   C
 / \   \
D   E   F

As an adjacency list:

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"]
}

BFS: Breadth-First Search

Core idea: Explore level by level. Use a queue — FIFO ensures we always process the node we discovered earliest, keeping us close to the starting point before going further.

BFS Implementation

def bfs(graph, start):
    visited = set()              # Track visited nodes to avoid infinite loops
    queue = deque([start])       # Initialize queue with the starting node
    visited.add(start)
    traversal_order = []

    while queue:
        node = queue.popleft()   # Process the OLDEST discovered node (front)
        traversal_order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:      # Only visit each node once
                visited.add(neighbor)
                queue.append(neighbor)       # Add to BACK of queue (discover later)

    return traversal_order

print("BFS from A:", bfs(graph, "A"))

Output:

BFS from A: ['A', 'B', 'C', 'D', 'E', 'F']

Step-by-step trace:

Step	Process	Queue After
1	A	[B, C]
2	B	[C, D, E]
3	C	[D, E, F]
4	D	[E, F]
5	E	[F]
6	F	[]

Notice that A and C are processed before D, E, and F — all level-1 nodes before level-2 nodes.

BFS: Shortest Path

def bfs_shortest_path(graph, start, end):
    visited = set([start])
    queue = deque([[start]])         # Queue holds PATHS, not just nodes

    if start == end:
        return [start]

    while queue:
        path = queue.popleft()       # Get the oldest path
        node = path[-1]              # Last node in this path

        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path          # Found the destination!
                visited.add(neighbor)
                queue.append(new_path)

    return None   # No path exists

print("Shortest path A→F:", bfs_shortest_path(graph, "A", "F"))
print("Shortest path A→E:", bfs_shortest_path(graph, "A", "E"))

Output:

Shortest path A→F: ['A', 'C', 'F']
Shortest path A→E: ['A', 'B', 'E']

def friends_within_degrees(graph, start, max_degrees):
    """Find all people within max_degrees connections of start."""
    visited = {start}
    queue = deque([(start, 0)])   # (person, degrees away)
    results = []

    while queue:
        person, degree = queue.popleft()
        if degree > 0:
            results.append((person, degree))

        if degree < max_degrees:
            for friend in graph.get(person, []):
                if friend not in visited:
                    visited.add(friend)
                    queue.append((friend, degree + 1))

    return results

social = {"Alice": ["Bob","Charlie"], "Bob": ["Alice","Diana","Eve"],
          "Charlie": ["Alice","Frank"], "Diana": ["Bob"],
          "Eve": ["Bob"], "Frank": ["Charlie"]}

print("People within 2 degrees of Alice:")
for person, deg in friends_within_degrees(social, "Alice", 2):
    print(f"  {person} ({deg} degree(s) away)")

Output:

People within 2 degrees of Alice:
  Bob (1 degree(s) away)
  Charlie (1 degree(s) away)
  Diana (2 degree(s) away)
  Eve (2 degree(s) away)
  Frank (2 degree(s) away)

DFS: Depth-First Search

Core idea: Go as deep as possible before backtracking. Use a stack (or recursion) — LIFO means we always continue down the most recently discovered path before exploring alternatives.

DFS Implementation — Recursive

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")              # Visit the node

    for neighbor in graph[node]:
        if neighbor not in visited:   # Only explore unvisited neighbors
            dfs_recursive(graph, neighbor, visited)
    return visited

DFS Implementation — Iterative

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]             # Use a stack — process most recently added first
    traversal_order = []

    while stack:
        node = stack.pop()      # Process the MOST RECENTLY discovered node (top)
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            for neighbor in reversed(graph[node]):  # Reverse to match recursive order
                if neighbor not in visited:
                    stack.append(neighbor)

    return traversal_order

print("DFS recursive from A:", end=" ")
dfs_recursive(graph, "A")
print()
print("DFS iterative from A:", dfs_iterative(graph, "A"))

Output:

DFS recursive from A: A B D E C F
DFS iterative from A: ['A', 'B', 'D', 'E', 'C', 'F']

Step-by-step trace (iterative):

Step	Pop	Stack After
1	A	[C, B]
2	B	[C, E, D]
3	D	[C, E]
4	E	[C]
5	C	[F]
6	F	[]

DFS goes all the way down B→D before coming back up for E and C.

DFS: Cycle Detection

DFS can detect cycles in a directed graph by tracking the current recursion path (the "call stack"):

def has_cycle(graph):
    visited = set()
    rec_stack = set()   # Nodes in the current DFS path

    def dfs(node):
        visited.add(node)
        rec_stack.add(node)    # Mark as part of current path

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True       # Cycle found deeper in recursion
            elif neighbor in rec_stack:
                return True           # Back edge found — cycle!

        rec_stack.remove(node)        # Done with this path — remove from rec stack
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

cyclic_graph = {"A": ["B"], "B": ["C"], "C": ["A"]}       # A→B→C→A — cycle!
acyclic_graph = {"A": ["B"], "B": ["C"], "C": []}          # No cycle

print("Cyclic graph has cycle:", has_cycle(cyclic_graph))    # True
print("Acyclic graph has cycle:", has_cycle(acyclic_graph))  # False

Output:

Cyclic graph has cycle: True
Acyclic graph has cycle: False

BFS vs DFS: When to Use Each

Feature	BFS	DFS
Data structure	Queue (FIFO)	Stack / Recursion (LIFO)
Traversal order	Level by level	As deep as possible first
Finds shortest path?	Yes (unweighted graphs)	No — not guaranteed
Memory usage	O(V) — can store many nodes	O(h) — only the current path depth
Good for	Shortest path, level-order	Cycle detection, topological sort
Complete?	Yes — always finds if reachable	Yes
Best for sparse graphs?	Both are O(V+E)	Both are O(V+E)

Time Complexity

Both BFS and DFS visit every vertex and every edge exactly once:

Time complexity: O(V + E) — V vertices and E edges
Space complexity: O(V) — visited set and the queue/stack

Real-World Applications

Algorithm	Application
BFS	Shortest path in GPS navigation
BFS	Social network: degrees of separation
BFS	Web crawlers: explore pages level by level
BFS	Finding all reachable nodes from a source
DFS	Maze solving: explore one path completely
DFS	Cycle detection in dependency graphs
DFS	Topological sorting (task ordering)
DFS	Finding connected components

Key Takeaway

Previous 🎉 View Course Summary

💬 DiscussionPowered by GitHub Discussions

📱

Get this course's notes on Telegram!

Free cheat sheets, summaries & practice exercises

Get Notes Free →

BFS and DFS: Exploring Graphs Systematically

BFS and DFS: Graph Traversal Algorithms

Lost in a Theme Park

The Graph We Will Use

BFS: Breadth-First Search

BFS Implementation

BFS: Shortest Path

Real-World BFS: Social Network Degrees

DFS: Depth-First Search

DFS Implementation — Recursive

DFS Implementation — Iterative

DFS: Cycle Detection

BFS vs DFS: When to Use Each

Time Complexity

Real-World Applications

Key Takeaway

💬 DiscussionPowered by GitHub Discussions

BFS and DFS: Exploring Graphs Systematically

BFS and DFS: Graph Traversal Algorithms

Lost in a Theme Park

The Graph We Will Use

BFS: Breadth-First Search

BFS Implementation

BFS: Shortest Path

Real-World BFS: Social Network Degrees

DFS: Depth-First Search

DFS Implementation — Recursive

DFS Implementation — Iterative

DFS: Cycle Detection

BFS vs DFS: When to Use Each

Time Complexity

Real-World Applications

Key Takeaway

💬 DiscussionPowered by GitHub Discussions