如何将程序写入 return bfs

Question

我想编写一个 JavaScript 函数，它接受 3 个参数：二维数组形式的邻接矩阵、节点数和起始顶点。函数returns对邻接矩阵表示的图进行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))```

Answer 1

有关详细信息，请参阅代码段中的注释。您也可以使用地图来替换您访问过的数组，如果有一些节点没有连接到任何其他节点，它可能会更有效率。

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))

如何将程序写入 return bfs

how to write a program to return bfs

javascript

breadth-first-search

adjacency-matrix