我的广度优先搜索算法如何在下面的教程示例中找到最短路径

Question

我了解广度优先搜索工作原理的基础知识。它利用队列数据结构逐层查找相邻顶点。

我的问题是了解如何找到两个顶点之间的最短路径。在下面的例子中，我们将新访问的顶点连同它们的边分配给一个名为 edgeTo 的数组，但我的问题是数据是如何存储的？是二维数组吗？以及如何使用 pathTo 函数检索它？

pathTo 函数中的 for loop 对我来说看起来有点奇怪，当然是因为我可能是新手。这是如何获得最短路径的，数据是如何构造的，或者它是如何保存边缘的？

// add this to Graph class
this.edgeTo = [];
// bfs function
function bfs(s) {
    var queue = [];
    this.marked[s] = true;
    queue.push(s); // add to back of queue
    while (queue.length > 0) {
        var v = queue.shift(); // remove from front of queue
        if (v == undefined) {
            print("Visited vertex: " + v);
        }
        for each(var w in this.adj[v]) {
            if (!this.marked[w]) {
                this.edgeTo[w] = v;
                this.marked[w] = true;
                queue.push(w);
            }
        }
    }
}

function pathTo(v) {
    var source = 0;
    if (!this.hasPathTo(v)) {
        return undefined;
    }
    var path = [];
    for (var i = v; i != source; i = this.edgeTo[i]) { // this for loop is new to me 
        path.push(i);
    }
    path.push(s);
    return path;
}

function hasPathTo(v) {
    return this.marked[v];
}

Answer 1

this.edgeTo 是一个简单的数组。

BFS 从源顶点开始，当它发现一个新顶点 i 时，它会将 edgeTo[i] 设置为 predecessor 顶点，这必须必须 更接近 源头一步。

在 pathTo 函数中，for 循环遵循从 v 返回源的 edgeTo 链接链。这枚举了reverse中的最短路径。这些顶点在找到时附加到 path。

pathTo 然后 returns 路径倒序，有点奇怪。一个更常见的实现会在返回它之前反转 path，这样它就会从 source 开始并在 v 结束。这个功能似乎在其他方面也有一些问题。也许你还在努力......

我的广度优先搜索算法如何在下面的教程示例中找到最短路径

How is my breadth first search algorithm finding the shortest path in my tutorial example below

javascript

algorithm

data-structures