Recursive Depth-First Search | The Personal Website of Dustin Boston

A recursive depth-first search algorithm that explores branches deeply before backtracking, managing traversal state with recursion.

code.ts

/**
 * @file Recursive Depth-First Search
 * @author Dustin Boston)
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/** Enum representing possible states of a vertex in graph traversal. */
export enum VertexColor {
  Unvisited = 0, // Vertex has not been visited.
  Visiting = 1, // Vertex is being visited.
  Visited = 2, // Vertex has been fully visited.
}

/** Class representing a vertex in a graph. */
export class GraphVertex {
  public adjacent: GraphVertex[] = [];
  public predecessor: GraphVertex | undefined = undefined;
  public distance = Infinity;
  public finalDistance = Infinity;
  public state: VertexColor = VertexColor.Unvisited;

  constructor(public value: string) {}
}

let time: number;

// Recursive depth first search
export function depthFirstSearch(graph: GraphVertex[]): void {
  for (const node of graph) {
    node.state = VertexColor.Unvisited;
    node.predecessor = undefined;
  }

  time = 0;

  for (const node of graph) {
    if (node.state === VertexColor.Unvisited) {
      visitNode(node);
    }
  }
}

/**
 * Visits a node in a graph using a recursive depth-first search (DFS)
 * algorithm. Marks the node as visited, updates its discovery and finishing
 * times, and recursively visits all its adjacent nodes.
 *
 * @param node - The node to visit.
 */
export function visitNode(node: GraphVertex): void {
  node.state = VertexColor.Visiting;
  time++;
  node.distance = time;

  for (const adjacentNode of node.adjacent) {
    if (adjacentNode.state === VertexColor.Unvisited) {
      adjacentNode.predecessor = node;
      visitNode(adjacentNode);
    }
  }

  node.state = VertexColor.Visited;
  time++;
  node.finalDistance = time;
}

test.ts

import {describe, test, expect, beforeAll} from "bun:test";
import {depthFirstSearch, GraphVertex} from "./code.ts";

function printStructure(g: GraphVertex[]) {
  let ptime = 0;

  function print() {
    ptime = 1;

    const accumulator: string[] = [];
    for (const u of g) {
      const s = printAdjacentVertices(u);
      accumulator.push(`(${u.value}${s}${u.value})`);
    }

    return accumulator.join("");
  }

  function printAdjacentVertices(u: GraphVertex) {
    ptime += 1;
    let s = "";

    for (const v of u.adjacent) {
      s += `(${v.value}`;
      // Distance matches current
      const d = v.distance === ptime;
      // Next adjacent vertex has been visited
      const n = ptime + 1 !== v.finalDistance;

      if (d && n) {
        s += printAdjacentVertices(v);
      }

      s += `${v.value})`;
    }

    ptime += 1;
    return s;
  }

  return print();
}

describe("Depth First Search", () => {
  let graph: GraphVertex[] = [];

  beforeAll(() => {
    // Create verticies V
    graph = [
      new GraphVertex("u"),
      new GraphVertex("v"),
      new GraphVertex("w"),
      new GraphVertex("x"),
      new GraphVertex("y"),
      new GraphVertex("z"),
    ];

    const [nu, nv, nw, nx, ny, nz] = graph;

    // Add edges E
    nu.adjacent = nw.adjacent.concat([nv, nx]);
    nv.adjacent.push(ny);
    nw.adjacent = nw.adjacent.concat([ny, nz]);
    nx.adjacent.push(nv);
    ny.adjacent.push(nx);
    nz.adjacent.push(nz);

    graph = [nu, nv, nw, nx, ny, nz];
  });

  test("Depth", () => {
    depthFirstSearch(graph);
    const nw = graph[2];
    const expectedTime = 12; // Time is V + E (from u and w)
    expect(nw.finalDistance).toBe(expectedTime);
  });

  test("Structure", () => {
    depthFirstSearch(graph);
    const [nu, , nw] = graph;
    const expectedStructure = "(u(v(y(xx)y)v)(xx)u)(w(yy)(zz)w)";
    const structure = printStructure([nu, nw]);
    expect(expectedStructure).toBe(structure);
  });
});