Graphs and Traversal
A graph is a set of vertices (nodes) connected by edges. Unlike a tree, a graph can have cycles, multiple paths between two nodes, and disconnected pieces. Graphs model almost any network: cities and roads, friends on social media, web pages and links, dependencies between tasks.
Vocabulary
- Vertex (or node) — a single entity in the graph
- Edge — a connection between two vertices
- Directed — edges go one way (
A -> B); undirected — they go both ways - Weighted — edges carry a number (distance, cost); unweighted — they don't
- Cycle — a path that returns to its starting vertex
Adjacency List vs Adjacency Matrix
The two main ways to represent a graph in code:
- Adjacency list: a map from each vertex to the list of its neighbors. Compact when the graph is sparse (few edges).
- Adjacency matrix: a 2D array where
m[i][j] = 1if there's an edge from i to j. Best when the graph is dense or you frequently ask "is there an edge between i and j?"
For most real graphs (social networks, road maps, web), adjacency lists win on both memory and speed.
BFS — Breadth-First Search
BFS uses a queue. It explores the start node, then all neighbors, then all neighbors of neighbors, expanding outward in layers. BFS finds the shortest path in an unweighted graph because it visits nearer nodes before farther ones.
DFS — Depth-First Search
DFS uses a stack (often the recursion call stack). It dives deep along one path before backtracking. DFS is great for detecting cycles, topological sorting, and exploring connected components.
The "Visited" Set
Both BFS and DFS need a visited set. Without it, cycles cause infinite loops — you'd revisit the same nodes forever. Always mark a node as visited the moment you queue it (BFS) or enter it (DFS).
Try It Yourself
- Modify BFS to find the shortest path length from A to F
- Use DFS to detect whether a graph contains a cycle
- Find all connected components in a graph by running DFS from every unvisited node