Recursive Depth-First Search

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

Time complexity of insertion and deletion is Constant, i.e. O(1)
Time complexity of search is is Linear, i.e. O(n)
Space complexity is Linear, i.e. O(n)

/**
 * @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;
}

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

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);
  });
});

Iterative Depth-First Search

Iterator Pattern

Docs

computer-science.dev

Title here

Recursive Depth-First Search