Skip to content
Computational Lab.

BFS & DFS

Queue versus stack, two shapes of search.

Beginner / graph / search

The same walled grid, searched two ways: breadth-first expands in rings and its first path is the shortest; depth-first dives down one corridor to its end before trying the next. Switch strategies and watch the frontier change shape - a queue and a stack are different geometries.

Tagged: breadth-first, depth-first, frontier, shortest path

Live simulation

Switch strategies to compare the frontier shapes on the same maze.

Speed

Switch strategies to compare the frontier shapes on the same maze.

Mathematics

Breadth-first search expands outward in exact rings: every cell at graph distance d is visited before any cell at distance d + 1. Depth-first search commits to a corridor until it dead-ends. Same graph, same neighbors - the only difference is queue versus stack.

BFS frontier = FIFO queue => first path found is shortest (unweighted)

DFS frontier = LIFO stack => path found, no length guarantee

both: O(V + E) time, O(V) frontier

The optimality of BFS falls straight out of the ring structure: a cell first reached at depth d cannot be reached in fewer steps, because all depth d-1 cells were already expanded. DFS gives no such guarantee - which the path-length metric makes concrete on the same maze.

How it works

The grid, walls, and start/goal are shared with the A* experiment; visited flags and parent pointers are flat typed arrays. Expanding a cell enqueues its four unvisited neighbors with the parent recorded; BFS shifts from the front of the array, DFS pops from the back.

Switching strategies restarts the run over the same walls, so the visited-region shapes are directly comparable.

Implementation

src/engine/experiments/bfs-dfs.ts · 208 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4/**
5 * Breadth-first and depth-first traversal on the same walled grid the A*
6 * experiment uses. BFS discovers shortest paths by layer; DFS dives - and
7 * the metrics make the difference measurable rather than anecdotal.
8 */
9export class BfsDfsExperiment extends BaseExperiment {
10 readonly id = "bfs-dfs";
11
12 private cols = 0;
13 private rows = 0;
14 private offsetX = 0;
15 private offsetY = 0;
16 private walls = new Uint8Array(0);
17 private visited = new Uint8Array(0);
18 private queue: number[] = [];
19 private parents = new Int32Array(0);
20 private start = 0;
21 private goal = 0;
22 private status: "running" | "found" | "exhausted" = "running";
23 private visitedCount = 0;
24 private path: number[] = [];
25 private current = -1;
26
27 protected params(): ParameterDef[] {
28 return [
29 {
30 key: "strategy",
31 label: "Strategy",
32 options: [
33 { value: "bfs", label: "Breadth-first (queue)" },
34 { value: "dfs", label: "Depth-first (stack)" },
35 ],
36 defaultValue: "bfs",
37 },
38 { key: "cell", label: "Grid cell", min: 8, max: 24, step: 1, defaultValue: 14, unit: "px" },
39 { key: "density", label: "Wall density", min: 0, max: 45, step: 1, defaultValue: 28, unit: "%" },
40 { key: "rate", label: "Expansions per tick", min: 1, max: 30, step: 1, defaultValue: 3 },
41 ];
42 }
43
44 protected onReset(): void {
45 this.cols = Math.max(10, Math.floor(this.width / this.num("cell")));
46 this.rows = Math.max(10, Math.floor(this.height / this.num("cell")));
47 this.offsetX = Math.floor((this.width - this.cols * this.num("cell")) / 2);
48 this.offsetY = Math.floor((this.height - this.rows * this.num("cell")) / 2);
49 const n = this.cols * this.rows;
50 this.walls = new Uint8Array(n);
51 this.visited = new Uint8Array(n);
52 this.parents = new Int32Array(n).fill(-1);
53 const density = this.num("density") / 100;
54 for (let i = 0; i < n; i++) this.walls[i] = this.rng() < density ? 1 : 0;
55 this.start = (this.rows >> 1) * this.cols + 1;
56 this.goal = (this.rows >> 1) * this.cols + (this.cols - 2);
57 this.walls[this.start] = 0;
58 this.walls[this.goal] = 0;
59 this.queue = [this.start];
60 this.visited[this.start] = 1;
61 this.visitedCount = 1;
62 this.status = "running";
63 this.path = [];
64 this.current = -1;
65 }
66
67 protected onParameterChange(key: string): void {
68 if (key === "cell" || key === "density") this.reset();
69 else if (key === "strategy" || key === "rate") this.beginRun();
70 }
71
72 private beginRun(): void {
73 const n = this.cols * this.rows;
74 this.visited.fill(0);
75 this.parents.fill(-1);
76 this.queue = [this.start];
77 this.visited[this.start] = 1;
78 this.visitedCount = 1;
79 this.status = "running";
80 this.path = [];
81 this.current = -1;
82 void n;
83 }
84
85 protected onUpdate(): void {
86 if (this.status !== "running") return;
87 const rate = this.num("rate");
88 for (let k = 0; k < rate && this.status === "running"; k++) this.expandOne();
89 }
90
91 private expandOne(): void {
92 if (this.queue.length === 0) {
93 this.status = "exhausted";
94 return;
95 }
96 // BFS takes from the front (queue); DFS pops from the back (stack).
97 const node = this.str("strategy") === "bfs" ? this.queue.shift()! : this.queue.pop()!;
98 this.current = node;
99 if (node === this.goal) {
100 this.reconstruct();
101 this.status = "found";
102 return;
103 }
104 const x = node % this.cols;
105 const y = (node / this.cols) | 0;
106 const neighbors = [
107 x > 0 ? node - 1 : -1,
108 x < this.cols - 1 ? node + 1 : -1,
109 y > 0 ? node - this.cols : -1,
110 y < this.rows - 1 ? node + this.cols : -1,
111 ];
112 for (const next of neighbors) {
113 if (next < 0 || this.walls[next] || this.visited[next]) continue;
114 this.visited[next] = 1;
115 this.parents[next] = node;
116 this.visitedCount += 1;
117 this.queue.push(next);
118 }
119 }
120
121 private reconstruct(): void {
122 this.path = [];
123 let node = this.goal;
124 while (node !== -1 && node !== this.start) {
125 this.path.push(node);
126 node = this.parents[node];
127 }
128 this.path.push(this.start);
129 this.path.reverse();
130 }
131
132 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
133 const { cols, rows, offsetX, offsetY } = this;
134 const cell = this.num("cell");
135 ctx.fillStyle = theme.bg;
136 ctx.fillRect(0, 0, this.width, this.height);
137 for (let y = 0; y < rows; y++) {
138 for (let x = 0; x < cols; x++) {
139 const node = y * cols + x;
140 const px = offsetX + x * cell;
141 const py = offsetY + y * cell;
142 if (this.walls[node]) {
143 ctx.fillStyle = theme.fgTertiary;
144 ctx.fillRect(px, py, cell - 1, cell - 1);
145 } else if (this.visited[node]) {
146 ctx.fillStyle = theme.raised;
147 ctx.fillRect(px + 1, py + 1, cell - 2, cell - 2);
148 }
149 }
150 }
151 ctx.fillStyle = theme.viz[1];
152 for (const node of this.queue.slice(0, 4000)) {
153 ctx.fillRect(offsetX + (node % cols) * cell + 1, offsetY + Math.floor(node / cols) * cell + 1, cell - 2, cell - 2);
154 }
155 if (this.current >= 0 && this.status === "running") {
156 ctx.fillStyle = theme.accentStrong;
157 ctx.fillRect(
158 offsetX + (this.current % cols) * cell + 1,
159 offsetY + Math.floor(this.current / cols) * cell + 1,
160 cell - 2,
161 cell - 2,
162 );
163 }
164 if (this.path.length > 1) {
165 ctx.strokeStyle = theme.accent;
166 ctx.lineWidth = Math.max(2, cell * 0.3);
167 ctx.lineJoin = "round";
168 ctx.lineCap = "round";
169 ctx.beginPath();
170 for (let i = 0; i < this.path.length; i++) {
171 const node = this.path[i];
172 const cx = offsetX + (node % cols) * cell + cell / 2;
173 const cy = offsetY + Math.floor(node / cols) * cell + cell / 2;
174 if (i === 0) ctx.moveTo(cx, cy);
175 else ctx.lineTo(cx, cy);
176 }
177 ctx.stroke();
178 }
179 ctx.fillStyle = theme.viz[2];
180 ctx.fillRect(offsetX + (this.start % cols) * cell + 2, offsetY + Math.floor(this.start / cols) * cell + 2, cell - 4, cell - 4);
181 ctx.strokeStyle = theme.accent;
182 ctx.lineWidth = 2;
183 ctx.strokeRect(offsetX + (this.goal % cols) * cell + 2, offsetY + Math.floor(this.goal / cols) * cell + 2, cell - 4, cell - 4);
184 }
185
186 getMetrics() {
187 return {
188 strategy: this.str("strategy") === "bfs" ? "BFS" : "DFS",
189 visited: this.visitedCount,
190 frontier: this.queue.length,
191 pathLength: this.status === "found" ? this.path.length : "n/a",
192 status: this.status === "found" ? "Found" : this.status === "exhausted" ? "No path" : "Searching",
193 };
194 }
195
196 describe(): string {
197 if (this.status === "found") {
198 return `${this.str("strategy") === "bfs" ? "Breadth-first" : "Depth-first"} search reached the goal after visiting ${this.visitedCount} cells; path length ${this.path.length}.`;
199 }
200 if (this.status === "exhausted") return "No path exists; the frontier is empty.";
201 return `${this.str("strategy") === "bfs" ? "Breadth-first" : "Depth-first"} search: ${this.visitedCount} cells visited, ${this.queue.length} in the frontier.`;
202 }
203
204 entities(): number {
205 return this.cols * this.rows;
206 }
207}
208

Performance

Time per tick
O(V + E) for either strategy
Space
O(V): visited flags, parents, frontier
Notes
Try the same density with both strategies: BFS's visited region is a disk, DFS's is a starfish.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.