BFS or DFS over a graph represented as an adjacency list (or implicit state graph)
When to useGeneric graph traversal where neighbors come from a Map/array (not a grid)
iterative
Find Related Products
find_related_productsBreadth First Search on Graphs
graph_bfsBFS or DFS?
graph_bfs_vs_dfsDepth First Search on Graphs
graph_dfsLongest Cycle
longest_cycleOpen the Lock
open_the_lockShortest Path Between A and B
shortest_path_unweightSliding Puzzle
sliding_puzzleWord Ladder
word_ladderClone Graphmedium
clone_graph · no slotsINITIALIZE
build adjacency list; visited set; queue/stack with start
const graph = new Map(); const allNodes = new Set();for (const row of input) {const hub = row[0];for (let i = 1; i < row.length; i++) {/* add bidirectional edges */}}const visited = new Set(); let best = [];
const visited = new Set([start]);const queue = [start];const order = [];
const visited = new Set([start]);const queue = [start]; const bfsOrder = [];const stack = [start]; const dfsVisited = new Set(); const dfsOrder = [];
const visited = new Set();const stack = [start];const order = [];
const graph = Array.from({ length: n + 1 }, () => []);for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); }const distance = new Array(n + 1).fill(-1);distance[start] = 0;const queue = [start]; let farthest = start;
const trapped = new Set(trappedCombos);const visited = new Set(['0000']);const queue = [['0000', 0]];
const visited = new Set([A]);const queue = [[A, 0]];
const start = initPos.flat().join('');const visited = new Set([start]);const queue = [[start, 0]];
const wordSet = new Set(wordList);const visited = new Set([start]);const queue = [[start, 0]];
—
TRAVERSE
while queue not empty
for (const node of allNodes) {if (visited.has(node)) continue;const queue = [node]; visited.add(node); const component = [];
while (queue.length > 0) {
while (queue.length > 0) { /* BFS */
while (stack.length > 0) {
while (queue.length > 0) {
while (queue.length > 0) {
while (queue.length > 0) {
while (queue.length > 0) {
while (queue.length > 0) {
—
dequeue
pop node (BFS shift, DFS pop)
const curr = queue.shift(); component.push(curr);
const node = queue.shift();
const node = queue.shift();
const node = stack.pop();if (visited.has(node)) continue;visited.add(node);
const node = queue.shift();
const [combo, steps] = queue.shift();
const [node, dist] = queue.shift();
const [state, steps] = queue.shift();const zero = state.indexOf('0');
const [word, steps] = queue.shift();
—
expand
for each neighbor in graph.get(node)
for (const next of graph.get(curr) || []) {
for (const next of adj.get(node) ?? []) {
for (const next of getNeighbors(node)) {
for (const next of adj.get(node) ?? []) {
for (const next of graph[node]) {
for (let i = 0; i < 4; i++) { for (const delta of [-1, 1]) { /* generate next */ } }
for (const next of graph[node]) {
for (const swap of neighbors[zero]) {
for (let i = 0; i < word.length; i++) { for (let c = 0; c < 26; c++) { /* try each letter */ } }
—
[VISIT]
if unvisited, mark and enqueue with new state
if (!visited.has(next)) { visited.add(next); queue.push(next); }
if (!visited.has(next)) { visited.add(next); queue.push(next); }
if (!visited.has(next)) { visited.add(next); queue.push(next); }
stack.push(next);
if (distance[next] === -1) {distance[next] = distance[node] + 1;queue.push(next);if (distance[next] > distance[farthest]) farthest = next;}
if (next === targetCombo) return steps + 1;if (!visited.has(next) && !trapped.has(next)) {visited.add(next);queue.push([next, steps + 1]);}
if (node === B) return dist;if (!visited.has(next)) {visited.add(next);queue.push([next, dist + 1]);}
const next = /* swap zero and swap in state string */;if (next === target) return steps + 1;if (!visited.has(next)) {visited.add(next);queue.push([next, steps + 1]);}
if (word === end) return steps;if (wordSet.has(next) && !visited.has(next)) {visited.add(next);queue.push([next, steps + 1]);}
—
RETURN
result (path, count, distance, etc.)
if (component.length > best.length) best = component;}return best;
return order;
return [bfsOrder, dfsOrder];
return order;
const [u] = bfs(1);const [, diameter] = bfs(u);return diameter + 1;
return -1;
return -1;
return -1;
return 0;
—