Recursive Depth-First Search

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

/**
 * @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.
 */

/**
 * Represents the possible colors that can be assigned to vertices in graph
 * algorithms, which denote the state of a vertex during traversal or
 * processing.
 */
enum Color {
  White = 0, // Vertex has not been visited.
  Gray = 1, // Vertex is being visited.
  Black = 2, // Vertex has been fully visited.
}

/** Represents a vertex in a graph. */
class Vert {
  /** An array of vertices to which this vertex has direct edges. */
  public adjacent: Vert[] = [];
  /** The parent vertex in a traversal of the graph. */
  public parent: Vert | undefined = undefined;
  /** The distance from the starting vertex in a graph traversal. */
  public distance = Infinity;
  /** The final distance from the starting vertex in a graph traversal. */
  public final = Infinity; // Final Distance
  /** The color of the vertex. */
  public color: Color = Color.White;

/**
   * Constructs a new vertex instance.
   *
   * @param val The value of the vertex.
   */
  constructor(public value: string) {}
}

let time: number;

// Recursive depth first search
function depthFirstSearch(graph: Vert[]): void {
  for (const node of graph) {
    node.color = Color.White;
    node.parent = undefined;
  }

time = 0;

for (const node of graph) {
    if (node.color === Color.White) {
      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.
 */
function visitNode(node: Vert): void {
  node.color = Color.Gray;
  time++;
  node.distance = time;

for (const adjacentNode of node.adjacent) {
    if (adjacentNode.color === Color.White) {
      adjacentNode.parent = node;
      visitNode(adjacentNode);
    }
  }

node.color = Color.Black;
  time++;
  node.final = time;
}

(() => {
  let ptime: number;

function printStructure(g: Vert[]) {
    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: Vert) {
    ptime += 1;
    let s = '';
    // U.adjacent.forEach((v: Vert) => {

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.final;

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

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

ptime += 1;
    return s;
  }

// Create verticies V
  const nu = new Vert('u');
  const nv = new Vert('v');
  const nw = new Vert('w');
  const nx = new Vert('x');
  const ny = new Vert('y');
  const nz = new Vert('z');

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

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

function assertEquals(a: any, b: any) {
    if (a !== b) {
      throw new Error(`${a} !== ${b}`);
    }
  }

// Time is V + E (from u and w)
  const expectedTime = 12;
  assertEquals(nw.final, expectedTime);
  console.log(`expected time: ${expectedTime}`);
  console.log(`  actual time: ${nw.final}`);

const expectedStructure = '(u(v(y(xx)y)v)(xx)u)(w(yy)(zz)w)';
  const structure = printStructure([nu, nw]);
  assertEquals(expectedStructure, structure);
  console.log(`expected structure: ${expectedStructure}`);
  console.log(`  actual structure: ${structure}`);
})();