DSA Series · Graphs · Traversal · Overview

Graph Traversal: The Foundation

March 2026 · 12 min read

Graph traversal is the backbone of nearly every graph algorithm. Whether you are finding the shortest path, detecting cycles, or checking connectivity, you are fundamentally walking through nodes and edges in some order. This post sets up the vocabulary, the data structures, and the intuition you need before diving into BFS and DFS individually.

What Is a Graph

A graph is a set of vertices (nodes) connected by edges. Unlike a tree, a graph can have cycles, disconnected components, and edges going in any direction.

Key terminology:

Vertex (node): a point in the graph. The circles above (0 through 5).
Edge: a connection between two vertices. The lines above.
Directed vs undirected: arrows on edges (one-way) vs plain lines (two-way).
Weighted vs unweighted: edges may carry a cost/distance, or they may not.
Degree: number of edges touching a vertex. Node 1 above has degree 3.

How to Store a Graph

Before traversing, you need to store the graph. Two standard approaches:

Adjacency List

Each vertex stores a list of its neighbors. Space: O(V + E). Lookup "is u connected to v?": O(degree(u)).

// C++ adjacency list
vector<vector<int>> adj(n);
adj[0] = {1, 3};
adj[1] = {0, 2, 4};
adj[2] = {1, 4};
adj[3] = {0, 4, 5};
adj[4] = {1, 2, 3};
adj[5] = {3};

Use when: the graph is sparse (few edges relative to V²). This is the default for competitive programming.

Adjacency Matrix

A V x V grid. matrix[u][v] = 1 if edge exists. Space: O(V²). Lookup: O(1).

// C++ adjacency matrix
vector<vector<int>> mat(n, vector<int>(n, 0));
mat[0][1] = mat[1][0] = 1;
mat[0][3] = mat[3][0] = 1;
mat[1][2] = mat[2][1] = 1;
// ... etc

Use when: the graph is dense, or you need O(1) edge lookup (rare in competitive programming).

Competitive programming default: almost always use adjacency list. It is faster to iterate over neighbors and uses less memory.

Trees vs Graphs

A tree is a special graph: connected, acyclic, with exactly V-1 edges. Graph traversal has two extra considerations that tree traversal does not:

Trees

No cycles. You can never revisit a node by following edges.
Exactly one path between any two nodes.
No need for a "visited" array (just track parent).

Graphs

Cycles are possible. Following edges can bring you back.
Multiple paths between nodes.
Must track visited nodes or you loop forever.

The orange edges form a cycle: B → C → D → A → B. A BFS or DFS without a visited check would loop around this cycle indefinitely. That is why graph traversal always needs a visited[] array (or equivalent).

The Two Fundamental Approaches

Every graph traversal is either BFS or DFS (or a variation of one of them).

BFS (Breadth-First Search)

Explore all neighbors at the current depth before moving deeper. Uses a queue.

Think: ripples expanding outward from a stone dropped in water.

Best for: shortest path in unweighted graphs, level-order traversal, minimum steps problems.

DFS (Depth-First Search)

Explore as deep as possible before backtracking. Uses a stack (or recursion).

Think: exploring a maze by always taking the next unexplored path until you hit a dead end.

Best for: cycle detection, topological sort, connected components, path existence.

When to Use Which

Problem Type	Use	Why
Shortest path (unweighted)	BFS	BFS guarantees minimum edges
Minimum steps / moves	BFS	Level = number of steps
Level-order anything	BFS	BFS naturally processes level by level
Cycle detection	DFS	Back edges are easy to detect in DFS
Topological sort	DFS	Post-order of DFS gives reverse topo order
Connected components	Either	Both work. DFS is slightly simpler to code.
Path existence	Either	Both find reachable nodes
Bipartite check	BFS	Two-color by level is intuitive

The Visited Pattern

The single most important concept in graph traversal is tracking which nodes you have already seen. Without it, cycles cause infinite loops. The pattern is consistent across BFS and DFS:

vector<bool> visited(n, false);

// When you first encounter a node:
visited[node] = true;

// Before processing a neighbor:
if (!visited[neighbor]) {
    // process it
}

When to mark visited matters:

BFS: mark visited when you add to the queue (not when you dequeue). This prevents the same node from being enqueued multiple times.
DFS: mark visited when you enter the node (at the start of the recursive call or when you push to the stack).

Common bug: marking visited when you dequeue in BFS instead of when you enqueue. This causes the same node to appear in the queue multiple times, wasting time and potentially producing wrong results.

Complexity of Graph Traversal

Both BFS and DFS, when using an adjacency list, run in:

Time: O(V + E) where V is vertices and E is edges. Every vertex is visited once. Every edge is examined once (undirected) or examined from its source (directed).
Space: O(V) for the visited array. BFS additionally uses O(V) for the queue. DFS uses O(V) for the recursion stack (or explicit stack).

With an adjacency matrix, the time becomes O(V²) because checking all possible neighbors of a node takes O(V) regardless of how many actual edges exist.

What Comes Next

This post covered the foundations. The next posts go deep into each traversal:

BFS: Queue mechanics, level-by-level processing, shortest path guarantee, step-by-step animation.
DFS: Stack/recursion mechanics, edge classification, backtracking, step-by-step animation.
Multi-source BFS: Starting from multiple nodes simultaneously. Rotten oranges, 0-1 BFS, nearest distance problems.
DFS Applications: Cycle detection, connected components, topological sort connection, flood fill.