Iterative Depth-First Search

An iterative depth-first search algorithm using a stack, exploring as far along each branch as possible before backtracking, useful for pathfinding and cycle detection.

/**
 * @file Iterative Depth-First Search (DFS)
 * @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. */
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. */
class GraphVertex {
  public neighbors: GraphVertex[] = [];
  public predecessor: GraphVertex | undefined = undefined;
  public discoveryTime = Infinity;
  public finishTime = Infinity;
  public state: VertexColor = VertexColor.Unvisited;

/**
   * Constructs a new vertex instance.
   *
   * @param id The unique identifier of the vertex.
   * @param neighbors An array of adjacent vertices.
   * @param predecessor The preceding vertex in traversal.
   * @param discoveryTime Discovery time during traversal.
   * @param finishTime Finish time during traversal.
   * @param state The visitation state of the vertex.
   */
  constructor(public id: string) {}
}

/**
 * Function to perform iterative depth-first search on a graph.
 *
 * @param graph Array of vertices representing the graph.
 */
function iterativeDepthFirstSearch(graph: GraphVertex[]): void {
  for (const vertex of graph) {
    vertex.state = VertexColor.Unvisited;
    vertex.predecessor = undefined;
  }

let timeCounter = 0;
  const vertexStack: GraphVertex[] = [];

for (const vertex of graph) {
    if (vertex.state === VertexColor.Unvisited) {
      vertexStack.push(vertex);

while (vertexStack.length > 0) {
        const currentVertex = vertexStack.pop();
        if (!currentVertex) throw new Error('Stack unexpectedly empty.');

if (currentVertex.state === VertexColor.Unvisited) {
          currentVertex.state = VertexColor.Visiting;
          currentVertex.discoveryTime = ++timeCounter;
        } else if (currentVertex.state === VertexColor.Visited) {
          continue;
        }

let adjacentAdded = 0;
        for (let i = currentVertex.neighbors.length - 1; i >= 0; i--) {
          const neighbor = currentVertex.neighbors[i];
          if (neighbor.state === VertexColor.Unvisited) {
            neighbor.predecessor = currentVertex;
            vertexStack.push(neighbor);
            adjacentAdded++;
          }
        }

if (adjacentAdded === 0) {
          currentVertex.state = VertexColor.Visited;
          currentVertex.finishTime = ++timeCounter;
          if (currentVertex.predecessor)
            vertexStack.push(currentVertex.predecessor);
        }
      }
    }
  }
}

/**
 * Utility to print graph structure for debugging using a for loop.
 *
 * @param graph Array of graph vertices.
 * @returns String representation of the graph structure.
 */
function printGraphStructure(graph: GraphVertex[]): string {
  const pseudoTime = 1;
  let output = '';

for (const vertex of graph) {
    const details = getVertexDetails(vertex, pseudoTime);
    output += `(${vertex.id}${details}${vertex.id})`;
  }

return output;
}

/**
 * Helper function to print details of adjacent vertices.
 *
 * @param vertex Current vertex being explored.
 * @param currentTime Reference to traversal time.
 * @returns String representation of adjacent vertices.
 */
function getVertexDetails(vertex: GraphVertex, currentTime: number): string {
  currentTime++;
  let details = '';
  for (const neighbor of vertex.neighbors) {
    details += `(${neighbor.id}`;
    const distanceMatches = neighbor.discoveryTime === currentTime;
    const isNextVisited = currentTime + 1 !== neighbor.finishTime;

if (distanceMatches && isNextVisited) {
      details += getVertexDetails(neighbor, currentTime);
    }

details += `${neighbor.id})`;
  }

currentTime++;
  return details;
}

// Test rewritten with throw statements.
(() => {
  const u = new GraphVertex('u');
  const v = new GraphVertex('v');
  const w = new GraphVertex('w');
  const x = new GraphVertex('x');
  const y = new GraphVertex('y');
  const z = new GraphVertex('z');

u.neighbors = [v, x];
  v.neighbors.push(y);
  w.neighbors = [y, z];
  x.neighbors.push(v);
  y.neighbors.push(x);
  z.neighbors.push(z);

const graph = [u, v, w, x, y, z];
  iterativeDepthFirstSearch(graph);

const expectedTime = 12;
  if (w.finishTime !== expectedTime)
    throw new Error(
      `Test failed: expected finish time ${expectedTime}, got ${w.finishTime}`,
    );

const expectedStructure = '(u(v(y(xx)y)v)(xx)u)(w(yy)(zz)w)';
  const actualStructure = printGraphStructure([u, w]);
  if (actualStructure !== expectedStructure)
    throw new Error(
      `Test failed: expected structure ${expectedStructure}, got ${actualStructure}`,
    );

console.log('Graph structure:', actualStructure);
})();