Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 3x 3x 3x 3x 3x 3x 3x 3x 3x 11x 11x 11x 17x 17x 17x 2x 2x 17x 14x 14x 14x 14x 17x 9x 9x 9x 1x 1x 1x 1x 1x 2x 2x 2x 2x 2x 2x 2x 2x 2x 2x 7x 7x 7x 10x 10x 10x 2x 2x 2x 8x 8x 8x 8x 8x 8x 8x 10x 9x 9x 8x 8x 10x 8x 8x 8x 2x 1x 1x | // use case: using to find shortest (operation) path between two nodes in a graph
// keywords: queue, breadth first search, shortest path
import findPathChildToParent from "../utils/findPathChildToParent";
type Graph = {
[key: string]: string[];
};
// where have a queue to check each node
// a set with Visited to check if node is visited
// each item in queue
// if item already in visited set so we will skip
// if (item === end) => true
// else push graph[item] to queue
// if not found return -1
const breadthFirstSearch = (
graph: Graph,
start: string,
end: string
): number => {
const visited = new Set();
const queue: string[] = [start];
let degrees = 0;
while (queue.length) {
const size = queue.length;
for (let x = 0; x < size; x++) {
const node = queue.shift() as string;
if (node === end) {
return degrees;
}
if (!visited.has(node)) {
const children = graph[node];
queue.push(...children);
visited.add(node);
}
}
degrees++;
}
return -1;
};
export const breadthFirstSearchPath = (
graph: Graph,
start: string,
end: string
): string[] => {
const visited = new Set();
const queue: string[] = [start];
let degrees = 0;
const childParent: { [key: string]: string } = {};
while (queue.length) {
const size = queue.length;
for (let x = 0; x < size; x++) {
const node = queue.shift() as string;
if (node === end) {
// stop here
return findPathChildToParent(childParent, end);
}
if (!visited.has(node)) {
const children = graph[node];
queue.push(...children);
visited.add(node);
children.forEach((child) => {
if (!childParent[child]) {
childParent[child] = node;
}
});
}
}
degrees++;
}
return [];
};
export default breadthFirstSearch;
|