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 
const ROLE_PERMISSIONS = {
  admin: ['users:read', 'users:write', 'billing:read', 'billing:write'],
  manager: ['users:read', 'billing:read'],
  member: ['users:read'],

Role-based permissions middleware in Express

authorization middleware rbac
Intermediate 9 steps
javascript 
function attachThousandSeparators(input, { locale = 'en-US' } = {}) {
  const formatter = new Intl.NumberFormat(locale);
  const groupSep = formatter.format(11111).replace(/\d/g, '')[0] || ',';
  const decimalSep = formatter.format(1.1).replace(/\d/g, '')[0] || '.';

Live thousand separators without losing the caret

dom intl caret-preservation
Advanced 8 steps
java 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion
Intermediate 8 steps
ruby 
class KeyTransformer
  def self.camelize(data)
    new.camelize(data)
  end

Recursively camelizing nested Ruby data

recursion data-transformation pattern-matching
Intermediate 7 steps
javascript 
import { useReducer, useEffect } from "react";
 
const initialState = { status: "idle", data: null, error: null };
 

Building a data-fetching hook in React

custom-hooks usereducer data-fetching
Intermediate 9 steps
javascript 
const express = require('express');
const app = express();
 
app.get('/health', (req, res) => res.json({ status: 'ok' }));

Graceful shutdown in an Express server

graceful-shutdown signal-handling connection-tracking
Advanced 9 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