๐Ÿ”น.findPath()

๐Ÿšง under construction

data structure โŸฉ graph โŸฉ .findPath

find a path using breadth-first or depth-first search.

// โญ Graph
class Graph {

    // omitted ...

    // ๐Ÿ”น .findPath()
    findPath(start, target, {

        // log debug info if true
        debug = false,
        
        // search mode:
        // โ€ข 'breadth-first': shortest (default)
        // โ€ข 'depth-first'
        mode = 'breadth-first',   
        
    } = {}) {

        // choose stack or queue for waiting list
        const waitinglistMode = {
            'breadth-first': 'queue',
            'depth-first': 'stack',
        };

        // nodes waiting to be explored
        const waitingList = new WaitingList(waitinglistMode[mode]);

        let current = null;                   // currently examined node
        const visited = Object.create(null);  // visited nodes (a dictionary)
        const parent = Object.create(null);   // parents of each node in path

        // enqueue node
        function enqueue(node) {
            waitingList.enqueue(node);        // put node in queue
            visited[node] = true;       // mark it as visited
            parent[node] = current;     // save its parent (`current`)
        }

        // initial setup
        enqueue(start);    // put `start` in queue

        // debug
        let i = 0;
        const line = '-'.repeat(20);

        // 1. while the queue is not empty
        while (!waitingList.isEmpty) {

            // debug info
            if (debug) {
                log(`[${i}] ${line}`);
                log(`current: ${current}`);
                log(waitingList.toString());
                log(`visited: ${Object.keys(visited)}`);
                i += 1;
            }

            // pick and examine first node in queue 
            current = waitingList.dequeue();

            // 1.1 if `current` is `target`, path is found.
            if (current === target) {

                // construct the path
                let node = target;        // by starting at `target`
                let path = [target];

                // and following the parents back to `start`.
                while (node = parent[node], node !== null) {
                    path.push(node);
                }

                return path.reverse();
            }

            // 1.2 `current` is not `target`, 
            //     add unvisited neighbors to `queue`
            this.neighborsOf(current)
                .filter(node => !visited[node])
                .forEach(node => enqueue(node));
        }

        // 2. `queue` empty and `target` not found, 
        //    no path from `start` to `target`.
        return null;
    }
}
PreviousGraphNext.findShortestPath()

Last updated