CODEWITHSUNDEEP
javascriptbreadth-first-searchadjacency-matrix
DMaC
DMaC

Reputation: 11

how to write a program to return bfs

I want to write a JavaScript function that takes 3 arguments: an adjacency matrix in the form of a 2D array, number of nodes, and starting vertex. The function returns the BFS traversal of the graph represented by the adjacency matrix.

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

Upvotes: 0

Views: 279

Answers (1)

Colin
Colin

Reputation: 1215

Please see comments in code snippet for details. Also you can use a map to replace your visited array, probably it is more efficient if there are some nodes not connected to any other nodes. 

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

Upvotes: 2

Related Questions