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

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的邻居的普通迭代器

谢谢阅读！

Answer 1

每个顶点必须具有特定的路径字段。这样，您可以跟踪所选的路径，因此可以找到较短的路径。我将使用String数组，就像您使用Boolean数组来存储访问的顶点一样。

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;
}