相关疑难解决方法(0)

我做了一些研究,我似乎错过了这个算法的一小部分.我明白了一个广度优先搜索是如何工作的,但我不明白它究竟是如何让我到一个特定的路径,而不是仅仅告诉我,每个单独的节点可以走了.我想解释我困惑的最简单方法是提供一个例子:

例如,假设我有一个这样的图形:

我的目标是从A到E(所有边缘都没有加权).

我从A开始,因为那是我的起源.我排队A,然后立即将A排队并探索它.这产生B和D,因为A连接到B和D.因此我将B和D排队.

我将B排队并探索它,并发现它导致A(已经探索过)和C,所以我排队C.然后我排队D,并发现它导致E,我的目标.然后我将C排队,并发现它也导致E,我的目标.

我逻辑上知道最快的路径是A-> D-> E,但我不确定广度优先搜索有多精确 - 我应该如何记录路径,这样当我完成时,我可以分析结果并查看最短的路径是A-> D-> E？

另外,请注意我实际上并没有使用树,因此没有"父"节点,只有子节点.

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

我正在做的事情:

使用文本文件中的图形,找到并打印从顶点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; …