Graph class that implements depth-first search algorithm.

graph.ts

/**
 * References:
 * https://adelachao.medium.com/graph-topological-sort-javascript-implementation-1cc04e10f181
 * http://peterknolle.com/page/51/
 * https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
 */

class Graph {
    private vertices: Record<string, Array<string>>;

    constructor() {
        this.vertices = {};
    }

    public addVertex(vertex: string): void {
        if (!this.vertices[vertex]) {
            this.vertices[vertex] = new Array<string>();
        }
    }

    public addEdge(v1: string, v2: string): void {
        this.addVertex(v1);
        this.addVertex(v2);
        if (!this.vertices[v1].includes(v2)) {
            this.vertices[v1].push(v2);
        }
    }

    public depthFirstSearch(): Array<string> {
        const sortedVertices = Array<string>();

        const visited = {}; // vertices we've already processed
        const visiting = {}; // vertex we're processing; detects cycles

        const visit = (vertex: string): void => {
            if (visited[vertex]) {
                return;
            }
            if (visiting[vertex]) {
                throw new Error('Cycle found at vertex ' + vertex);
            }
            visiting[vertex] = true;
            this.vertices[vertex].forEach(visit);
            visiting[vertex] = false;
            visited[vertex] = true;
            sortedVertices.push(vertex);
        };
        for (const vertex of Object.keys(this.vertices)) {
            visit(vertex);
        }
        return sortedVertices;
    }
}

((): void => {
    const vertexA = 'A';
    const vertexB = 'B';
    const vertexC = 'C';
    const vertexD = 'D';
    const vertexE = 'E';

    const graph = new Graph();
    graph.addVertex(vertexA);
    graph.addVertex(vertexB);
    graph.addVertex(vertexC);
    graph.addVertex(vertexD);
    graph.addVertex(vertexE);

    graph.addEdge(vertexA, vertexB);
    graph.addEdge(vertexA, vertexC);
    graph.addEdge(vertexC, vertexD);
    graph.addEdge(vertexD, vertexE);

    console.log(JSON.stringify(graph, null, 2));

    console.log(graph.depthFirstSearch());
})();