Part 1 · Concepts · Graphs
Graphs, BFS and DFS
Nodes connected by edges. BFS explores level by level and finds the fewest hops. DFS goes deep first and is good for reachability and cycles.
How it works
Store graphs as an adjacency list (each node keeps a list of neighbours), usually built from an edge list. BFS: a queue plus a distance array. The first time you reach a node is its shortest hop count. DFS: recursion or a stack, plus a visited set. Mark a node visited when you add it, so it's never added twice. Connected components: start a DFS from every unvisited node and count the starts.
| BFS / DFS | O(V + E) |
| adjacency list space | O(V + E) |
| adjacency matrix | O(V²) space, O(1) edge check |
Reach for it when
- Fewest steps or hops: BFS
- Can I reach it? Are there cycles? Count groups: DFS
- Grids are graphs: each cell has 4 neighbours
Implementation (JavaScript, tested)
function buildGraph(n, edges, directed = false) {
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
adj[a].push(b);
if (!directed) adj[b].push(a);
}
return adj;
}
function bfsDistances(adj, src) {
const dist = new Array(adj.length).fill(-1);
dist[src] = 0;
const q = [src];
for (let h = 0; h < q.length; h++) {
// head index = O(1) dequeue
const u = q[h];
for (const v of adj[u])
if (dist[v] === -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
return dist; // -1 = unreachable
}
function dfsOrder(adj, src) {
const seen = new Set(),
out = [];
const go = u => {
seen.add(u);
out.push(u);
for (const v of adj[u]) if (!seen.has(v)) go(v);
};
go(src);
return out;
}
function countComponents(n, edges) {
const adj = buildGraph(n, edges),
seen = new Array(n).fill(false);
let count = 0;
for (let s = 0; s < n; s++) {
if (seen[s]) continue;
count++;
const stack = [s];
seen[s] = true;
while (stack.length)
for (const v of adj[stack.pop()])
if (!seen[v]) {
seen[v] = true;
stack.push(v);
}
}
return count;
}Traps
- Forgetting visited: infinite loop on any cycle.
- BFS gives shortest paths only when every edge has the same weight. Weighted needs Dijkstra.
- Undirected: add the edge both ways.
In real systems: Service dependency maps, social graphs, crawlers, garbage collectors (mark reachable objects).
Say out loud: Shortest path with equal weights is BFS, O(V + E). With weights I'd switch to Dijkstra.