如何编写返回bfs的程序

Question

我想写一个JavaScript函数，它需要3个参数：一个2D数组形式的邻接矩阵、节点数和起始顶点。

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

---