javascript - 广度优先搜索算法

Question

我正在学习算法。我坚持执行 BFS 练习部分。在他们的网站上没有练习的线索或解决方案。我不知道我在哪里犯了错误？

请有人帮助我理解我做错的地方。

这是我的代码。

        /* A Queue object for queue-like functionality over JavaScript arrays. */
    var Queue = function() {
        this.items = [];
    };
    Queue.prototype.enqueue = function(obj) {
        this.items.push(obj);
    };
    Queue.prototype.dequeue = function() {
        return this.items.shift();
    };
    Queue.prototype.isEmpty = function() {
        return this.items.length === 0;
    };

    /*
     * Performs a breadth-first search on a graph
     * @param {array} graph - Graph, represented as adjacency lists.
     * @param {number} source - The index of the source vertex.
     * @returns {array} Array of objects describing each vertex, like
     *     [{distance: _, predecessor: _ }]
     */


          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

                // As long as the queue is not empty:
                //  Repeatedly dequeue a vertex u from the queue.
                //  
                //  For each neighbor v of u that has not been visited:
                //     Set distance to 1 greater than u's distance
                //     Set predecessor to u
                //     Enqueue v
                //
                //  Hint:
                //  use graph to get the neighbors,
                //  use bfsInfo for distances and predecessors 

                while(!queue.isEmpty()){
                    var vertex= queue.dequeue();

                for(var i=0; i<vertex.length; i++){
                    var  neighbour = graph[vertex][i];

                    if(bfsInfo[neighbour].distance===null){
                        bfsInfo[neighbour].distance+=1;
                        bfsInfo[neighbour].predecessor=vertex;
                        queue.enqueue(neighbour);
                    }
                }



                }
                return bfsInfo;
            };

            var adjList = [
                [1],
                [0, 4, 5],
                [3, 4, 5],
                [2, 6],
                [1, 2],
                [1, 2, 6],
                [3, 5],
                []
                ];
            var bfsInfo = doBFS(adjList, 3);
            for (var i = 0; i < adjList.length; i++) {
                println("vertex " + i + ": distance = " + bfsInfo[i].distance + ", predecessor = " + bfsInfo[i].predecessor);
            }

测试用例

 Program.assertEqual(bfsInfo[0], {distance: 4, predecessor: 1});
Program.assertEqual(bfsInfo[1], {distance: 3, predecessor: 4});
Program.assertEqual(bfsInfo[2], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[3], {distance: 0, predecessor: null});
Program.assertEqual(bfsInfo[4], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[5], {distance: 2, predecessor: 2});
Program.assertEqual(bfsInfo[6], {distance: 1, predecessor: 3});
Program.assertEqual(bfsInfo[7], {distance: null, predecessor: null});

Answer 1

你需要改变

  bfsInfo[neighbour].distance+=1;

类似的东西

  bfsInfo[neighbour].distance = bfsInfo[vertex].distance + 1;

由于距离为空，所以加一没有多大意义。 您想获取到当前节点(vertext)的距离并加一以获得到新节点(neighbor)的距离。

此外，我认为您需要遍历顶点邻居 (graph[vertex]) 而不是顶点本身(因为它只是一个数字)。

不完全确定它是如何与 javascript 一起工作的。您需要知道当前节点(顶点)是哪一个才能获得正确的距离。