首页 文章

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

提问于
浏览 次
4

我知道 Headers 有点乱，但我不知道如何更好地解释它 .

What I'm trying to do:

使用文本文件中的图形，找到并打印从顶点A到顶点B的最短路径（最小顶点数量） .

注意：使用广度优先搜索，而不是Dijkstra .

What I've got:

一种在图上应用BFS的工作算法，但没有实际打印出最短路径的好方法 .

我很难 distinguishing a vertex in the shortest path from one that is simply run through the algorithm, but not in the shortest path.

例如：找到0到4之间的最短路径.0连接到1,2和3. 1连接到4.我的路径原来是[0,1,2,3,4]而不是[0,1， 4] .

我不确定't been able to find any threads asking the same question, or any walk-through of BFS that includes this, so I'我不确定我是不是要让它变得比它更难？

Edit: 为那些可能感兴趣的人的代码（如果我避开圈子，根本不确定？）

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

Thanks for reading!

java shortest-path breadth-first-search graph-traversal

4 回答

  • 1

    您必须为每个顶点指定特定的路径字段 . 通过这种方式，您可以跟踪您选择的路径，从而找到短路径 . 我将使用一个String数组，就像您使用布尔数组存储访问顶点一样 .

    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;
}
    回复于
  • 5

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

    第1步：初始化访问列表，以便每个元素都是 '-1' 或"unvisited"

    第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可以访问，则visit [w]将存储它来自哪个节点，从该节点，您可以一直回溯到v，最后以相反的顺序打印它们 . （这可以使用堆栈或递归打印方法完成 . ）

    希望有道理 . :)

    回复于
  • 3

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

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

    回复于
  • 10

    您需要将当前节点推送到堆栈，并且只有在到达目标时才打印整个堆栈 .

    回复于

相关问题