Fundamentals/Patterns/Graph — BFS/DFS on Adjacency List10 problems· Graph

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_products
Breadth First Search on Graphs
graph_bfs
BFS or DFS?
graph_bfs_vs_dfs
Depth First Search on Graphs
graph_dfs
Longest Cycle
longest_cycle
Open the Lock
open_the_lock
Shortest Path Between A and B
shortest_path_unweight
Sliding Puzzle
sliding_puzzle
Word Ladder
word_ladder
Clone Graphmedium
clone_graph · no slots
INITIALIZE
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;