The Core Idea
Nodes and Edges, No Fixed Shape
A graph is a set of nodes (also called vertices) connected by edges, with no restriction on how many edges a node can have or what pattern the connections form — unlike a tree, a graph can have cycles (paths that loop back on themselves) and doesn't need a single designated root. This flexibility is exactly why graphs model so many real-world systems: social networks, road maps, web page links, and dependency chains are all naturally graphs.
Graphs can be directed (edges have a one-way direction, like a one-way street or a 'follows' relationship) or undirected (edges go both ways, like a mutual friendship or a two-way road), and edges can optionally carry weights (representing cost, distance, or time) or be unweighted (every edge counts equally).
💡 Memory Trick
DEPTH-FIRST SEARCH is exploring a maze by always taking the next available turn and going as deep as possible down that single path before backtracking — you use your memory of where you've been (a stack) to know how to retreat when you hit a dead end. BREADTH-FIRST SEARCH is a rumor spreading through a crowd evenly in every direction at once — everyone one step away hears it first, then everyone two steps away, using a queue to process people in the exact order they heard the rumor.
The Two Core Traversals
Depth-First Search vs. Breadth-First Search
1
Depth-First Search (DFS) — uses a stack
Starting at a node, visit an unvisited neighbor, then immediately visit one of ITS unvisited neighbors, plunging as deep as possible before backtracking. Implemented either with an explicit stack or, more commonly, with recursion (which uses the call stack implicitly). Good for exploring all possible paths, detecting cycles, and topological sorting.
2
Breadth-First Search (BFS) — uses a queue
Starting at a node, visit ALL of its immediate neighbors first, then all of their unvisited neighbors, processing the graph in expanding 'rings' outward from the start. Implemented with a queue, since you need to process discovered nodes in the exact order they were found. Guarantees the shortest path (in terms of number of edges) in an unweighted graph.
Example: BFS from a starting node reaches all nodes 1 edge away before touching any node 2 edges away.
Choosing Between Them
Same Graph, Different Guarantee
The complexity of both DFS and BFS is O(V + E) — every vertex and every edge gets visited exactly once — so speed alone rarely decides between them. The real deciding factor is which guarantee you need: BFS guarantees the shortest path (fewest edges) to every reachable node, which is essential for problems like 'find the shortest route in an unweighted network.' DFS doesn't offer that guarantee, but it's naturally suited to problems about exploring full paths, like finding all possible solutions in a maze or detecting whether a cycle exists.
Both traversals must track which nodes have already been visited (usually with a set or boolean array) to avoid infinite loops in a graph containing cycles — this is a detail trees don't need to worry about, since a tree by definition has no cycles.
🖥️ Applied Scenario
You're building a social network feature that finds the shortest 'degrees of connection' path between two users (like 'you are connected to them through 3 mutual friends').
1
You model the network as an unweighted, undirected graph — users are nodes, friendships are edges.
2
You choose BFS rather than DFS, because BFS specifically guarantees finding the shortest path (fewest edges) between two nodes in an unweighted graph — DFS could find a valid path, but not necessarily the shortest one.
3
You maintain a visited set as you traverse, to avoid re-processing users you've already reached through a different chain of friendships (which would happen constantly in a graph with cycles, like most real friendship networks).
4
Conclusion: BFS's queue-based, ring-by-ring exploration is exactly what guarantees you find the minimum degrees of separation, not just some valid chain of connections.
📌 Exam Application
Exam questions frequently give you a small graph and ask you to list the order nodes are visited under DFS versus BFS starting from a specified node — the expected answer must correctly use a stack-like (DFS) or queue-like (BFS) processing order. You may also be asked to explain why BFS guarantees shortest path in an unweighted graph while DFS does not, and why both traversals are O(V + E).
⚠️ Most Common Graphs and Graph Traversal Mistakes
The most common mistake is forgetting to track visited nodes, causing an infinite loop the moment the graph contains any cycle — trees never need this check since they have no cycles, but graphs almost always do. Another frequent error is assuming DFS or BFS alone can find the shortest path in a WEIGHTED graph — BFS's shortest-path guarantee only holds for unweighted graphs (or graphs where every edge counts as exactly one step); weighted shortest-path problems require Dijkstra's algorithm or Bellman-Ford instead.
✓ Quick Self-Test
Given a small graph drawn out, can you correctly list the DFS and BFS visit order starting from a specified node? Can you explain, in one sentence, why BFS specifically (and not DFS) guarantees the shortest path in an unweighted graph?
→
← All Data Structures Lessons