Traversal, components, cycles & topological sort

BFS and DFS on a general graph, then the structural algorithms they unlock. · 12 min read

BFS and DFS need a visited set

Unlike a tree, a graph can have cycles and multiple paths to a node, so a traversal must remember where it's been. BFS (queue) explores in layers — shortest path in unweighted graphs. DFS (stack/recursion) dives deep — natural for components, cycles, and ordering. Both are O(V + E).

// BFS from src
queue<int> q; vector<bool> seen(V, false);
q.push(src); seen[src] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) if (!seen[v]) { seen[v] = true; q.push(v); }
}

Interactive visualization: BFS/DFS exploring a graph (grid + node views) — step through it frame by frame on this page.

Connected components

Run a traversal from every unvisited vertex; each launch discovers one component. Counting the launches counts the components (or use union-find — see DSU).

Cycle detection

In an undirected graph, a DFS that reaches an already-visited vertex that isn't the parent means a cycle. In a directed graph, a cycle exists iff DFS finds a back edge to a node currently on the recursion stack — equivalently, iff a topological sort fails to order every node.

Topological sort

For a DAG (directed acyclic graph), a topological order lists vertices so every edge points forward — the order you can do tasks with dependencies. Kahn's algorithm repeatedly removes a vertex with in-degree 0:

vector<int> indeg(V, 0);
for (int u = 0; u < V; u++) for (int v : adj[u]) indeg[v]++;
queue<int> q;
for (int u = 0; u < V; u++) if (!indeg[u]) q.push(u);
vector<int> order;
while (!q.empty()) {
    int u = q.front(); q.pop(); order.push_back(u);
    for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
if ((int)order.size() != V) { /* cycle: no topo order */ }

Practice: Number of Connected Components (Easy) — Count the connected pieces of an undirected graph.

Practice: Course Schedule (Medium) — Can you finish all courses? — detect a cycle in a dependency graph.

Practice: Topological Order (lexicographically smallest) (Hard) — Order a DAG so every edge points forward — smallest order, or none.