仅返回实际最短路径上的顶点

Question

我知道标题有点乱，但我不知道如何更好地解释。

我的目标：

从文本文件中找到一张图，使用广度优先搜索算法，找到并打印出从顶点A到顶点B的最短路径（最少的顶点数）。

注意：不使用Dijkstra算法。

我已经得到的：

一个应用BFS算法的工作算法，但没有很好的方法来实际打印出最短路径。

我很难区分最短路径中的顶点和仅仅是通过算法运行的顶点，但不在最短路径中的顶点。

例如：找到0和4之间的最短路径。0连接到1、2和3。1连接到4。我的路径变成了[0,1,2,3,4]，而不是[0,1,4]。

我还没有找到任何问同样问题的线程，或者包括这个问题的BFS的步骤，所以我不确定是否把它想得太难了？

编辑：代码供那些可能感兴趣的人使用（不确定是否避免了循环？）

编辑2：将路径存储方式更改为堆栈。

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

一些变量和方法的解释：

v = 起点顶点

w = 目标顶点

g = 图

vi = 正常迭代器，用于遍历v的邻居

谢谢阅读！

- bjrnt

---

你好，请问你能否发布代码？ - michal.kreuzman

你的代码中如何表示图形？你如何避免出现环？类似这样的问题最好通过你发布一些代码来回答... - thkala

我已经添加了一些代码。如果关于图表有任何缺失的信息，请告诉我。 - bjrnt

我觉得这里缺少了一些东西。首先，在Java中，String对象不可变，改变runBFS中的path有什么好处呢？ - thkala

你说得完全正确，是我的错。不过我已经将它从String更改为Stack，并将在代码中进行适当的更改。 - bjrnt

Answer 1

您需要为每个顶点设置特定路径字段。这样，您就可以跟踪所选的路径，因此找到了最短路径。我将使用一个字符串数组，就像您用于存储访问过的顶点的布尔数组一样。

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];
    String[] pathTo = new String[g.numVertices()];

    q.add(v);
    pathTo[v] = v+" ";
    while(q.peek() != null) {
        if(runBFS(q.poll(),w,visited,q,pathTo))
        break;
    }
    return pathTo[w];
}

private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {
    if(visited[v]) {
    }
    else if(v == w)
        return true; 
    }
    else {
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
            int nextVertex = vi.next();
            pathTo[nextVertex] = pathTo[v] + nextVertex + " ";
            q.add(nextVertex);
        }
    }
    return false;
}

- jCoder

---

正是我所需要的，非常感谢！ 很棒的解决方案，我想我的问题在于我只对从X到Y的路径感兴趣，而其他什么都不关心。 - bjrnt

太棒了！正是我在寻找的东西。 - Shane Fulmer

Answer 2

另一个紧凑（空间方面）的解决方案是我们助手提出的，不使用O(n^2)的存储空间，每个节点仅存储它来自哪个节点。这可以通过将visited-list更改为整数数组（int[] visited）来实现。

步骤1：初始化visited列表，使每个元素都为'-1'或"未访问"

步骤2：将第一个节点标记为其本身访问visited[v] = v; 执行BFS（就像您所做的那样，进行以下修改：）

从v -> v_next移动时：

if(visited[v_next] == -1)
{
  visited[v_next] = v;
  q.put(v_next);
}
// else skip it, it's already been visited

这样，如果 w 是可达的，visited [w] 将会存储它来自哪个节点，从那个节点，你可以回溯一直返回到 v，最后以相反的顺序打印它们。(这可以使用堆栈或递归打印方法完成。)希望这样能让您理解。 :)

- pbos

Answer 3

当您将一个顶点存储在BFS队列中时，您还需要存储一份“已到达该顶点的路径”的副本，以便在该顶点出队后仍然可用。目前，您的代码没有保留任何排队顶点的路径信息 - 它只保留了它访问的节点列表。

例如，您可以使用单独的队列来存储当前路径，并在下一个要搜索的顶点出队时恢复它。

- thkala

---

这个有用的解释非常有帮助。请在此处查看我的实现。 - c0der

Answer 4

你需要将当前节点推入一个栈中，在到达目的地时才打印整个栈。

- regularfry

---

这个方法返回了与我的先前方法完全相同的结果，您能否再详细解释一下？ - bjrnt

你在备份时是否弹出了它？ - regularfry