2022-10-26 23:11:39 -07:00
|
|
|
import Queue from '../Data-Structures/Queue/Queue'
|
|
|
|
|
|
2021-10-07 09:03:38 +02:00
|
|
|
/**
|
|
|
|
|
* Breadth-first search is an algorithm for traversing a graph.
|
|
|
|
|
*
|
|
|
|
|
* It discovers all nodes reachable from the starting position by exploring all of the neighbor nodes at the present
|
|
|
|
|
* depth prior to moving on to the nodes at the next depth level.
|
|
|
|
|
*
|
|
|
|
|
* (description adapted from https://en.wikipedia.org/wiki/Breadth-first_search)
|
|
|
|
|
* @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core
|
|
|
|
|
*/
|
|
|
|
|
export function breadthFirstSearch (graph, startingNode) {
|
2021-02-25 15:22:35 +05:30
|
|
|
// visited keeps track of all nodes visited
|
2021-02-27 09:44:33 +05:30
|
|
|
const visited = new Set()
|
2021-02-25 15:22:35 +05:30
|
|
|
|
|
|
|
|
// queue contains the nodes to be explored in the future
|
2022-10-26 23:11:39 -07:00
|
|
|
const queue = new Queue()
|
|
|
|
|
queue.enqueue(startingNode)
|
2021-02-25 15:22:35 +05:30
|
|
|
|
2022-10-26 23:11:39 -07:00
|
|
|
while (!queue.isEmpty()) {
|
2021-02-25 15:22:35 +05:30
|
|
|
// start with the queue's first node
|
2022-10-26 23:11:39 -07:00
|
|
|
const node = queue.dequeue()
|
2021-02-25 15:22:35 +05:30
|
|
|
|
2021-02-27 09:44:33 +05:30
|
|
|
if (!visited.has(node)) {
|
2021-02-25 15:22:35 +05:30
|
|
|
// mark the node as visited
|
2021-02-27 09:44:33 +05:30
|
|
|
visited.add(node)
|
2021-02-25 15:22:35 +05:30
|
|
|
const neighbors = graph[node]
|
|
|
|
|
|
|
|
|
|
// put all its neighbors into the queue
|
|
|
|
|
for (let i = 0; i < neighbors.length; i++) {
|
2022-10-26 23:11:39 -07:00
|
|
|
queue.enqueue(neighbors[i])
|
2021-02-25 15:22:35 +05:30
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return visited
|
|
|
|
|
}
|
