как написать программу для возврата BFS - PullRequest
Новая
       15

как написать программу для возврата BFS

0 голосов
/ 22 апреля 2020

Я хочу написать JavaScript функцию, которая принимает 3 аргумента: матрицу смежности в виде двумерного массива, количество узлов и начальную вершину. Функция возвращает BFS обход графа, представленного матрицей смежности. 

function task24(mat,n,v){
let visited=new Array(n)
let queue=[]
let result=[]

while(queue.length!=0){
queue.push(v)
result.push(queue.pop())
for(i=0;i<n;i++){
  visited[i]=0
}
let i=v
visited[i]=1


for(j = 0; j < n; j++) {
if(visited[j] == 0 && Adj[i][j] == 1) {
visited[j] = 1;
queue.push(j)
result.push(j)
i=queue.shift()
}
}
}
return result
}

console.log(task24([[0, 1, 0, 0], [0, 1, 1, 1], [1, 0, 0, 1], [0, 0, 1, 0]],4,2))```

1 Ответ

2 голосов
/ 22 апреля 2020

Пожалуйста, смотрите комментарии в фрагменте кода для деталей. Также вы можете использовать карту для замены вашего посещенного массива, возможно, это будет более эффективно, если есть некоторые узлы, не связанные с другими узлами. 

function task24(mat,n,v){
  const visited=[], queue=[v], result = [];
  //start from v and v is already in queue, so visited[v] is 1
  visited[v] = 1;

  //loop until queue is empty
  while(queue.length>0){
    //remove the node index from queue using shift and push it result
    const curr = queue.shift();
    result.push(curr);
    //check connected nodes
    for(let i = 0; i<mat[curr].length; i++){
      //if a node is connected and has not been seen, mark it as seen and push it to queue
      if(mat[curr][i] === 1 && !visited[i]){
        visited[i] = 1;
        queue.push(i)
      }
    }
  }
  return result
}

console.log(task24([[0, 1, 0, 0], [0, 1, 1, 1], [1, 0, 0, 1], [0, 0, 1, 0]],4,2))
...