BFS & DFS

IntermediateAlgorithms

The two fundamental graph traversal strategies. BFS explores level by level (shortest path in unweighted graphs). DFS dives deep first (connectivity, cycle detection, topological sort).

AVG TIME

O(V + E)

SPACE

O(V)

BEST

O(V + E)

WORST

O(V + E)

Step-by-Step Walkthrough

step-by-step walkthrough

Breadth-First Search (BFS)

1 / 6

algorithm.py

1def bfs(graph, start):

2 visited = set()

3 queue = [start]

4 visited.add(start)

5 result = []

7 while queue:

8 node = queue.pop(0)

9 result.append(node)

11 for neighbor in graph[node]:

12 if neighbor not in visited:

13 visited.add(neighbor)

14 queue.append(neighbor)

16 return result

visualization

graph

currentvisitedin queue

edges: A-B, A-C, B-D, B-E, C-F

variable inspectorO(1) setup

visited={A}

queue=[A]

result=[]

The Graph

We have a graph: A connects to B and C. B connects to D and E. C connects to F. We start at A and want to visit all nodes. BFS explores ALL neighbors at the current level before going deeper.

speedmed

← →space

In Python

Concept to Code- 3 structures for this topic

declare

visited = set()  # or visited = {1, 2, 3}

common ops

visited.add(x)

O(1)

x in visited

O(1)

visited.remove(x)

O(1)

visited.discard(x)

O(1)

a | b  /  a & b

O(n)

say in interview

"I'll track visited nodes with a set for O(1) membership checks"

Don't confuse {} (empty dict) with set() (empty set). Use set() explicitly.

Math You Need For This

BFS frontier: imagine all nodes currently "in the queue" lit up at once. For a wide graph, this can be a large layer. DFS stack: only one path from root to current node is active at once - much narrower.

Required concepts

Key math ideas

1 / 2

Graph theory - dots and lines

A graph is just dots (called nodes or vertices) connected by lines (called edges). That is it. A social network is a graph: people are nodes, friendships are edges. A city map is a graph: intersections are nodes, roads are edges.

Visual: Five circles on screen connected by lines between some pairs. Each circle is a node. Each line is an edge. If the lines have arrows, it is a directed graph (one-way streets). Without arrows it is undirected (two-way).

Think of it this way: Any network you can think of: power grid, airline routes, the internet, your friend group. All graphs.

For algorithms: Graph algorithms (BFS, DFS) work on any of these structures. Understanding what a graph IS makes the traversal algorithms click immediately.

Interactive 3D Visualization

Graph
BFS: O(V+E)DFS: O(V+E)Space: O(V+E)
Drag to orbit  -  Scroll to zoom

Brute Force vs Optimized

Interview Strategy - Shortest Path (Unweighted)

Start brute force, explain it, THEN optimize. "I can see a straightforward approach. Let me start there, then we can optimize."

Brute Force

DFS - Try All Paths

TimeO(V! or 2^V)

SpaceO(V)

"Explore every possible path from source to destination. Track the shortest one found."

Pros

+Guarantees finding shortest if you explore all paths
+Uses DFS which is simpler to code

Cons

-Exponentially slow on dense graphs
-Explores many unnecessary paths

Optimized

BFS - Level by Level

TimeO(V + E)

SpaceO(V)

"Explore all nodes at distance 1, then distance 2, etc. First time you reach the target is the shortest path."

Pros

+Guaranteed shortest path in unweighted graphs
+Visits each node at most once
+Standard interview approach

Cons

-Queue can grow large for wide graphs
-Only works for unweighted graphs

The Tradeoff

BFS naturally finds shortest paths because it explores level by level. DFS would need to try ALL paths to find the shortest. For a grid graph, that is the difference between seconds and years.

For n=100

Brute Forcepotentially millions ops

Optimized~200 ops

Say This

Say: "For shortest path in an unweighted graph, BFS is the right tool because it explores nodes in order of distance from the source."

Watch It Run

Breadth-First Search (BFS)

A queue drives level-by-level exploration. Finds shortest paths in unweighted graphs.

SPEED

1 / 8

Your data

Start Node (A-F):

algorithm.py

1 from collections import deque

3>def bfs(graph, start):

4 visited = set()

5 queue = deque([start])

6 visitedadd(start)

7 result = []

8 while queue:

9 node = queuepopleft()

10 resultappend(node)

11 for neighbor in graph[node]:

12 if neighbor not in visited:

13 visitedadd(neighbor)

14 queueappend(neighbor)

15 return result

queue visualization

FRONTBACK

empty queue

Starting BFS from node 'A'. Our graph has nodes A through F. BFS explores level by level - all neighbors before going deeper. Think of ripples spreading from a stone in water.

VariablesStep 1 of 10 (setup)

graph=A:B,CB:D,EC:F

start=A

Spaceplay/pause← →step+ -speed

Python Implementation

example.py

Now try it yourself

1 challenge with test cases and AI feedback

Practice Now

Complexity Analysis

COMMON OPERATIONS

Array

Access:O(1)

Search:O(n)

Insert end:O(1)*

Insert mid:O(n)

Hash Map

Get/Set:O(1)*

Delete:O(1)*

Search value:O(n)

Iterate:O(n)

Linked List

Access:O(n)

Search:O(n)

Insert head:O(1)

Delete known:O(1)

Binary Search

Search:O(log n)

Insert:O(log n)

Balanced BST

Search:O(log n)

Insert:O(log n)

Delete:O(log n)

Heap

Peek min/max:O(1)

Push:O(log n)

Pop:O(log n)

Heapify:O(n)

Graph (BFS/DFS)

Traversal:O(V+E)

Dijkstra (heap):O((V+E) log V)

Merge / Quick Sort

Sort:O(n log n)

Space (merge):O(n)

Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put BFS & DFS into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Greedy Algorithms

BFS & DFS

Next: Greedy Algorithms