E

T

a

R

```
import Queue from '../Data-Structures/Queue/Queue'
/**
* Breadth-first approach can be applied to determine the shortest path between two nodes in an equi-weighted graph.
*
* It searches the target node among all neighbors of the starting node, then the process is repeated on the level of
* the neighbors of the neighbors and so on.
*
* @see 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 breadthFirstShortestPath (graph, startNode, targetNode) {
// check if startNode & targetNode are identical
if (startNode === targetNode) {
return [startNode]
}
// visited keeps track of all nodes visited
const visited = new Set()
// queue contains the paths to be explored in the future
const initialPath = [startNode]
const queue = new Queue()
queue.enqueue(initialPath)
while (!queue.isEmpty()) {
// start with the queue's first path
const path = queue.dequeue()
const node = path[path.length - 1]
// explore this node if it hasn't been visited yet
if (!visited.has(node)) {
// mark the node as visited
visited.add(node)
const neighbors = graph[node]
// create a new path in the queue for each neighbor
for (let i = 0; i < neighbors.length; i++) {
const newPath = path.concat([neighbors[i]])
// the first path to contain the target node is the shortest path
if (neighbors[i] === targetNode) {
return newPath
}
// queue the new path
queue.enqueue(newPath)
}
}
}
// the target node was not reachable
return []
}
```