Graphs and dynamic programming · Lesson 19 of 23
Graphs: BFS and DFS
Storing a graph, walking it breadth-first and depth-first, and seeing every grid as a graph.
A graph is nodes joined by edges. A tree is a special case, but graphs can have cycles and edges that go one way (directed) or both.
The usual storage is an adjacency list: for each node, a list of its neighbours. It takes O(V + E) memory.
// Undirected edges → adjacency list
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
const n = 5
const adj = Array.from({ length: n }, () => [])
for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a) }
// BFS: nearest first, with the distance (number of edges) to each node
function bfs(start) {
const dist = new Array(n).fill(-1)
dist[start] = 0
const queue = [start]
for (let head = 0; head < queue.length; head++) {
const u = queue[head]
for (const v of adj[u]) if (dist[v] === -1) { dist[v] = dist[u] + 1; queue.push(v) }
}
return dist
}
// DFS: go deep first; here it lists the order of visits
function dfs(u, seen = new Set(), order = []) {
seen.add(u); order.push(u)
for (const v of adj[u]) if (!seen.has(v)) dfs(v, seen, order)
return order
}
console.log(bfs(0), dfs(0))- 0 (dist 0)
- 1 (dist 1)
- 3 (dist 2)
- 4 (dist 3)
- 3 (dist 2)
- 2 (dist 1)
- 1 (dist 1)
The BFS tree from node 0: each level is a distance. Node 3 was reached via 1 first, so edge 2–3 goes unused.
Every grid is a graph
A map, a maze, an image: each cell is a node and its neighbours are the cells up/down/left/right. No adjacency list needed; compute neighbours on the fly. "Number of islands", "shortest path in a maze" and "rotting oranges" are all BFS/DFS on a grid.
// Count islands of "1" (land) in a grid
function countIslands(grid) {
const g = grid.map((row) => [...row])
const h = g.length, w = g[0].length
let islands = 0
const sink = (r, c) => {
if (r < 0 || c < 0 || r >= h || c >= w || g[r][c] !== "1") return
g[r][c] = "0" // mark visited by sinking the land
sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
}
for (let r = 0; r < h; r++) for (let c = 0; c < w; c++) if (g[r][c] === "1") { islands++; sink(r, c) }
return islands
}
console.log(countIslands(["11000", "11000", "00100", "00011"]))Quick question
You want the fewest knight moves between two squares on a chessboard. The best fit?
Exercise
Write components(n, edges) returning the number of connected groups (edges go both ways) using DFS. It must print 2 5.
Expected output: 2 5
function components(n, edges) {
}
console.log(components(5, [[0, 1], [1, 2], [3, 4]]), components(5, []))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.