🔹.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
Last updated