Created
September 25, 2023 12:16
-
-
Save poetix/a8c5aefa9b0a696cf58a685b1bc325e6 to your computer and use it in GitHub Desktop.
Breadth-first graph traversal in Typescript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Given a start node and a function which provides an Iterable of adjacent nodes for any node, | |
* perform a breadth-first traversal of the graph and yield each visited node together with | |
* the minimum number of steps needed to reach that node from the start node. | |
*/ | |
function *bft<T>(start: T, adjacent: (node: T) => Iterable<T>): IterableIterator<[T, number]> { | |
const visited: Set<T> = new Set(); | |
const queue: T[] = [start]; | |
visited.add(start); | |
var depth = 1; | |
while (queue.length > 0) { | |
const breadth = queue.length; | |
for (let i=0; i<breadth; i++) { | |
const next: T = queue.shift()!; | |
for (let node of adjacent(next)) { | |
if (!visited.has(node)) { | |
visited.add(node); | |
queue.push(node); | |
yield([node, depth]); | |
} | |
} | |
} | |
depth += 1; | |
} | |
} | |
/** | |
* Give a start node, a goal node, and a function which provides an Iterable of adjacent nodes for any node, | |
* return the minimum number of steps needed to reach the goal node from the start node, or undefined if it | |
* is unreachable. | |
*/ | |
function getDepth<T>(start: T, goal: T, adjacent: (node: T) => Iterable<T>): number | undefined { | |
for (let [node, depth] of bft(start, adjacent)) { | |
if (node == goal) return depth; | |
} | |
return undefined; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment