🔹.findPath()

🚧 under construction

data structure ⟩ graph ⟩ .findPath

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

💾 程式

• replit > Graph (js)

// ⭐ 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;
    }
}

💈範例

graph.findPath('M', 'E', {debug: true, mode: 'depth-first'}),
// graph.findPath('M', 'E', {debug: false}),
// breadth-first: [ 'M', 'F', 'G', 'E' ]
// depth-first  : [ 'M', 'S', 'G', 'E' ]

// [0] --------------------
// current: null
// Stack: [M ->
// visited: M
// [1] --------------------
// current: M
// Stack: [P,T,F,S ->
// visited: M,P,T,F,S
// [2] --------------------
// current: S
// Stack: [P,T,F,G ->
// visited: M,P,T,F,S,G
// [3] --------------------
// current: G
// Stack: [P,T,F,E ->
// visited: M,P,T,F,S,G,E