JSFiddle - React, Tailwind, and code Playground
JavaScript
function bfs(start, finish, matr){
if(start === finish){
return 0;
}
//превращаю матрицу в список
let graph = {};
for(let i = 0; i < matr.length; i++){
graph[i] = [];
for(let j = 0; j < matr[i].length; j++){
if(matr[i][j] === 1){
graph[i].push(j);
}
}
}
//Задаю очередь и массив пройденных узлов
let explored = [];
let queue = [start];
//Ищу путь, пока очередь не кончится
while(queue.lenght != 0){
let path = [];
path.push(queue[0]);
queue.shift(0);
let node = path[path.length - 1];
if(!explored.includes(node)){
let neighbours = graph[node];
//Проверяю всех соседей
for (let neighbour in neighbours){
let new_path = path;//путь к узлу
new_path.push(neighbours[neighbour]);
new_path.forEach((elem) => {queue.push(elem);});
//Если в соседях нужный узел, завершаю и вывожу путь
if(neighbours[neighbour] === finish){
return new_path;
}
}
explored.push(node);
}
}
//Если прошли по всей очереди и не дошли до нужного узла - пути нет
return 'No path';
}
let arr = [
[0,1,0,0,1],
[1,0,1,0,0],
[0,1,0,0,0],
[0,0,0,0,0],
[1,0,0,0,0]
]
console.log(bfs(0,4,arr));