I am trying to implement the doBFS function, which performs a breadth-first search on a graph and returns an array of objects describing each vertex and it doesn't traverse the vertex 0. Here is the code:

var doBFS = function(graph, source) {
    var bfsInfo = [];

    for (var i = 0; i < graph.length; i  ) {
        bfsInfo[i] = {
            distance: null,
            predecessor: null };
    }

    bfsInfo[source].distance = 0;

    var queue = new Queue();
    queue.enqueue(source);

    // Traverse the graph
    while(!queue.isEmpty()){
        var deq = queue.dequeue();

        for(var j = 0; j < graph[source].length; j  ){
            var el = graph[source][j];
            // println('from = '   source);
            // println('to = '   el);

            if (bfsInfo[el].distance === null){
                bfsInfo[el] = { 
                    distance: bfsInfo[source].distance 1, 
                    predecessor: source };
                source = el;
                queue.enqueue(source);
            }
        }
    }
    
    return bfsInfo;
};

The graph I am trying to traverse is:

var adjList = [
    [1],        //0
    [0, 4, 5],  //1
    [3, 4, 5],  //2
    [2, 6],     //3
    [1, 2],     //4
    [1, 2, 6],  //5
    [3, 5],     //6
    []          //7
    ];

I am trying to traverse from index 3 so I called the function by calling doBFS(adjList, 3); Here is the output, I got

vertex 0: distance = null, predecessor = null
vertex 1: distance = 3, predecessor = 4
vertex 2: distance = 1, predecessor = 3
vertex 3: distance = 0, predecessor = null
vertex 4: distance = 2, predecessor = 2
vertex 5: distance = 4, predecessor = 1
vertex 6: distance = 5, predecessor = 5
vertex 7: distance = null, predecessor = null

CodePudding user response：

There are two issues:

• var deq = queue.dequeue();: This variable deq is never used elsewhere in your code. Instead your loop continues to work with source. Correct this by pulling the next item into source.

• source = el;: this is not how BFS is supposed to work. The source should remain unchanged while iterating its neighbors (el). So enqueue el without assigning it to source.

So the relevant part should be:

        source = queue.dequeue();

        for(var j = 0; j < graph[source].length; j  ){
            var el = graph[source][j];
            if (bfsInfo[el].distance === null){
                bfsInfo[el] = { 
                    distance: bfsInfo[source].distance 1, 
                    predecessor: source 
                };
                queue.enqueue(el);
            }
        }

If your queue is correctly implemented, then this corrected code will give the distances from the given source:

[
  { "distance": 4,    "predecessor": 1    }, // 0
  { "distance": 3,    "predecessor": 4    }, // 1
  { "distance": 1,    "predecessor": 3    }, // 2
  { "distance": 0,    "predecessor": null }, // 3
  { "distance": 2,    "predecessor": 2    }, // 4
  { "distance": 2,    "predecessor": 2    }, // 5
  { "distance": 1,    "predecessor": 3    }, // 6
  { "distance": null, "predecessor": null }  // 7
]