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

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

Related explainers

javascript

'use server'
 
import { revalidatePath } from 'next/cache'
import { redirect } from 'next/navigation'

How a Next.js Server Action updates a post

server-actions authorization validation

Intermediate 7 steps

python

from collections.abc import Mapping
from typing import Any, Iterator

Flattening nested config into dotted keys

recursion generators tree-traversal

Intermediate 7 steps

javascript

const express = require('express');
 
const v1 = express.Router();

Versioning an API with Express Routers

api versioning routing modularity

Intermediate 10 steps

javascript

const RATE_LIMIT = 100;
const WINDOW_MS = 60 * 1000;
const BLOCK_MS = 5 * 60 * 1000;

Building a rate-limiting middleware in Express

rate-limiting middleware closures

Intermediate 9 steps

ruby

require 'json'
require 'set'
 
class SensitiveScrubber

Recursively scrubbing secrets from JSON

recursion data-masking pattern-matching

Intermediate 7 steps

javascript

const transitions = {
  cart: { checkout: 'shipping' },
  shipping: { submitAddress: 'payment', back: 'cart' },
  payment: { submitPayment: 'review', back: 'shipping' },