4

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

我正在尝试做的事情：

使用在文本文件中找到的图，找到并打印从顶点 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 的邻居的普通迭代器

谢谢阅读！

4

4 回答 4

10

您必须为每个顶点提供特定的路径字段。这样您就可以跟踪您选择的路径，从而找到短路径。我将使用一个字符串数组，就像您使用布尔数组来存储访问的顶点一样。

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;
}
于 2011-03-28T20:03:18.963 回答
6

我们的助手建议并且不使用 O(n^2) 存储空间的另一个紧凑（空间方面）解决方案是让每个节点只存储它来自哪个节点。这可以通过将访问列表更改为整数数组 ( int[] visited) 来完成。

第 1 步：初始化访问列表，以便每个元素都是'-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，最后以相反的顺序打印它们。（这可以使用堆栈或递归打印方法完成。）

希望这是有道理的。:)

于 2011-03-31T15:20:10.310 回答
3

当您在 BFS 队列中存储一个顶点时，您还需要存储一个到达该顶点的路径的副本，以便在该顶点出队时可用。就像现在一样，您的代码不会在排队的顶点上保留任何类型的路径信息 - 它只保留它访问的节点的列表。

例如，您可以使用将并行处理的单独队列，您将在其中存储当前路径，然后在将下一个要搜索的顶点出列后将其恢复。

于 2011-03-28T20:09:33.263 回答
1

您需要将当前节点推送到堆栈上，并且只有在到达目的地后才将整个堆栈打印出来。

于 2011-03-28T18:45:39.463 回答