#### Breadth First Shortest Path

P
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 []
}