javascript 31 lines · 8 steps

Depth-first search and pathfinding in JS

Two recursive graph walks: one that records every node visited, and one that returns the first path to a target.

Explained by highlit
Intermediate graphs recursion depth-first-search backtracking pathfinding
1function depthFirstSearch(graph, start) {
2 const visited = new Set();
3 const order = [];
4 
5 function visit(node) {
6 if (visited.has(node)) return;
7 visited.add(node);
8 order.push(node);
9 
10 const neighbors = graph[node] || [];
11 for (const next of neighbors) {
12 visit(next);
13 }
14 }
15 
16 visit(start);
17 return order;
18}
19 
20function findPath(graph, start, target, path = [start], visited = new Set([start])) {
21 if (start === target) return path;
22 
23 for (const next of graph[start] || []) {
24 if (visited.has(next)) continue;
25 visited.add(next);
26 const result = findPath(graph, next, target, [...path, next], visited);
27 if (result) return result;
28 }
29 
30 return null;
31}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A visited set is what keeps depth-first traversal from looping forever on cyclic graphs.
  2. 2Closures let an inner recursive helper share accumulating state without threading it through every argument.
  3. 3Returning a truthy result up the call stack lets DFS short-circuit the moment a target is found.

Related explainers

javascript 
function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;
 

Building a recursive descent calculator

parsing recursion operator-precedence
Intermediate 8 steps
javascript 
import { useState, useEffect, useCallback, useRef } from 'react';
 
const cache = new Map();
const inflight = new Map();

Building a stale-while-revalidate hook in React

caching request-deduplication custom-hooks
Advanced 10 steps
javascript 
import { useEffect, useRef, useState } from 'react';
 
export function useDelayedFlag(active, delay = 300) {
  const [visible, setVisible] = useState(false);

Delaying a loading spinner with a React hook

custom-hooks debouncing cleanup
Intermediate 8 steps
javascript 
const SWIPE_THRESHOLD = 80;
const MAX_TRANSLATE = 120;
 
export function attachSwipeToDismiss(element, onDismiss) {

Building a swipe-to-dismiss gesture in JS

touch-events gesture-detection dom-manipulation
Intermediate 10 steps
javascript 
const { pool } = require('./db');
 
function withTransaction() {
  return async (req, res, next) => {

A per-request transaction middleware in Express

middleware database-transactions connection-pooling
Advanced 7 steps
javascript 
function collapseConsecutiveLogs(lines, { keyFn = (l) => l.message } = {}) {
  const groups = [];
 
  for (const line of lines) {

Collapsing consecutive log lines in JavaScript

grouping run-length-encoding data-transformation
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Depth-first search and pathfinding in JS — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code