A graph is a set of vertices connected by edges — a model for roads, networks, dependencies and relationships. Stored as an adjacency list, it is traversed two ways: breadth-first (BFS) explores neighbours level by level; depth-first (DFS) plunges down one path before backtracking.
BFS for shortest, DFS for structure
BFS uses a queue and visits nodes in order of distance, so in an unweighted graph it finds shortest paths. DFS uses recursion or a stack and is the natural tool for connectivity, cycle detection and topological ordering.
BFS and DFS skeletons
function bfs(start):
queue = [start]; visited = {start}
while queue not empty:
node = dequeue()
for nb in adj[node]:
if nb not in visited:
visited.add(nb); enqueue(nb)
function dfs(node):
visited.add(node)
for nb in adj[node]:
if nb not in visited: dfs(nb)O(V + E)→O(V)
Each vertex and edge is examined once.
⚡ The edge
- BFS = queue = shortest path in unweighted graphs; DFS = recursion/stack = connectivity, cycles, topological sort. Pick by what the question asks.
- Always keep a visited set — without it, a cyclic graph sends the traversal into an infinite loop.
Worked example
BFS from A on edges A-B, A-C, B-D. What order are nodes visited?
- Start at A, enqueue its neighbours B and C.
- Dequeue B (visit), enqueue its unvisited neighbour D; dequeue C (visit).
- Dequeue D (visit). Order: A, B, C, D — level by level.
Answer: A, B, C, D (level order)
Worked example
How do you count connected components in an undirected graph?
- Iterate over all vertices; when you find one not yet visited, start a new traversal from it.
- That BFS/DFS marks the whole component reachable from it as visited.
- Each new traversal you launch is one more component; count them.
Answer: Run DFS/BFS from each unvisited vertex; the launch count is the answer (O(V+E))
⚠ Watch out
- Forgetting the visited set causes infinite loops on graphs with cycles.
- Distinguish directed from undirected — it changes cycle detection and edge handling.
- Plain BFS gives shortest paths only when edges are unweighted; weighted graphs need Dijkstra.