Library

Breadth and Depth Traversal

An undirected graph: visit in breadth or depth, find the shortest hop path, and detect a cycle without counting the walk back to a parent.

JAVASCRIPT Free to use

Code

class Graph {
    constructor() {
        this.links = new Map();
    }

    addVertex(vertex) {
        if (!this.links.has(vertex)) {
            this.links.set(vertex, new Set());
        }
        return this;
    }

    addEdge(from, to) {
        if (from === to) {
            return this;
        }

        this.addVertex(from).addVertex(to);
        this.links.get(from).add(to);
        this.links.get(to).add(from);
        return this;
    }

    neighbors(vertex) {
        return [...(this.links.get(vertex) ?? [])];
    }

    bfs(start) {
        if (!this.links.has(start)) {
            return [];
        }

        const seen = new Set([start]);
        const order = [];
        const queue = [start];

        for (let index = 0; index < queue.length; index += 1) {
            const vertex = queue[index];
            order.push(vertex);

            for (const next of this.links.get(vertex)) {
                if (!seen.has(next)) {
                    seen.add(next);
                    queue.push(next);
                }
            }
        }

        return order;
    }

    dfs(start) {
        if (!this.links.has(start)) {
            return [];
        }

        const seen = new Set();
        const order = [];

        const walk = (vertex) => {
            seen.add(vertex);
            order.push(vertex);

            for (const next of this.links.get(vertex)) {
                if (!seen.has(next)) {
                    walk(next);
                }
            }
        };

        walk(start);
        return order;
    }

    shortestPath(start, end) {
        if (!this.links.has(start) || !this.links.has(end)) {
            return null;
        }

        if (start === end) {
            return [start];
        }

        const seen = new Set([start]);
        const prev = new Map();
        const queue = [start];

        for (let index = 0; index < queue.length; index += 1) {
            const vertex = queue[index];

            for (const next of this.links.get(vertex)) {
                if (seen.has(next)) {
                    continue;
                }

                seen.add(next);
                prev.set(next, vertex);

                if (next === end) {
                    return this.rebuild(start, end, prev);
                }

                queue.push(next);
            }
        }

        return null;
    }

    hasCycle() {
        const seen = new Set();

        for (const start of this.links.keys()) {
            if (seen.has(start)) {
                continue;
            }

            const stack = [[start, null]];
            seen.add(start);

            while (stack.length) {
                const [vertex, parent] = stack.pop();

                for (const next of this.links.get(vertex)) {
                    if (next === parent) {
                        continue;
                    }
                    if (seen.has(next)) {
                        return true;
                    }
                    seen.add(next);
                    stack.push([next, vertex]);
                }
            }
        }

        return false;
    }

    rebuild(start, end, prev) {
        const path = [end];
        let current = end;

        while (current !== start) {
            current = prev.get(current);
            path.push(current);
        }

        path.reverse();
        return path;
    }
}

Quick try

const graph = new Graph();
graph.addEdge('A', 'B').addEdge('B', 'C').addEdge('A', 'D');

console.log(graph.bfs('A')); // ['A', 'B', 'D', 'C']
console.log(graph.dfs('A')); // ['A', 'B', 'C', 'D']
console.log(graph.shortestPath('D', 'C')); // ['D', 'A', 'B', 'C']
console.log(graph.hasCycle()); // false

graph.addEdge('C', 'D');
console.log(graph.hasCycle()); // true

What it does

The graph is undirected. An edge is stored both ways, and cycle checks skip the walk back to a parent.
bfs reaches nearer vertices first, so the shortest path here is by hop count, not by weights.
A missing vertex returns [] or null instead of throwing. A self-loop is ignored.

Where it fits

A practical place for this snippet in a real project.

Useful for unweighted links such as related pages or mutual contacts. Package dependencies need a directed graph, and this snippet is not that.

Similar snippets

JAVASCRIPT

Binary Search Tree

Insert, search, and delete while keeping values sorted. Average O(log n), worst O(n) if the tree becomes a chain.

JAVASCRIPT

Function Memoization

Wrap a function and reuse its result for the same inputs. The next call with the same values skips the work.

JAVASCRIPT

LRU Cache

Keep a fixed number of entries and evict the least recently used item when the cache is full.

Need a snippet that is not here?

Describe the problem or idea, and I will see if it belongs in the library.

Contact me Library