| 10 | * @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core |
| 11 | */ |
| 12 | export function breadthFirstSearch(graph, startingNode) { |
| 13 | // visited keeps track of all nodes visited |
| 14 | const visited = new Set() |
| 15 | |
| 16 | // queue contains the nodes to be explored in the future |
| 17 | const queue = new Queue() |
| 18 | queue.enqueue(startingNode) |
| 19 | |
| 20 | while (!queue.isEmpty()) { |
| 21 | // start with the queue's first node |
| 22 | const node = queue.dequeue() |
| 23 | |
| 24 | if (!visited.has(node)) { |
| 25 | // mark the node as visited |
| 26 | visited.add(node) |
| 27 | const neighbors = graph[node] |
| 28 | |
| 29 | // put all its neighbors into the queue |
| 30 | for (let i = 0; i < neighbors.length; i++) { |
| 31 | queue.enqueue(neighbors[i]) |
| 32 | } |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | return visited |
| 37 | } |