如何使用广度优先搜索在树中找到从一个顶点到另一个顶点的路径？

Question

我正在尝试实现一个 BFS，它 return 是一条从 a 到 b 的路径，其形式为顶点列表。我在一棵树上实现这个 BFS，所以我知道如果我能找到的话，这将是最短的路径。然而，到目前为止，我的研究只让我找到了搜索和查找节点的 BSF 算法，而不是 return 路径。

我正在处理的输入是最小生成树的邻接矩阵。我必须采取这个并找到从一个点到另一个点的路径。

Answer 1

Dijkstra 或 A* 可能是您想要使用的。不过，这取决于。您描述的似乎是一种寻路算法，而不是节点搜索。

Answer 2

如果你真的想使用 BFS 来解决这个问题，要跟踪从源到目的地的路径，你需要存储访问的每个节点的父节点。这是一个没有优化的示例 BFS。

import java.util.*;

public class bfs {

    static class Node {
        Node parent;
        int x;

        Node (int x) {
            this (x, null);
        }

        Node (int x, Node parent) {
            this.parent = parent;
            this.x = x;
        }

        void trace () {
            if (parent == null) {
                System.out.print (x);
            } else {
                parent.trace ();
                System.out.print ("->" + x);
            }
        }
    }

    static void bfs (int start, int goal, int[][] adj) {
        List<Node> list = new ArrayList<> ();

        list.add (new Node (start));

        while (!list.isEmpty ()) {
            Node cur = list.remove (0);

            if (cur.x == goal) {
                cur.trace ();
                break;
            } else {
                for (int i = 0; i < adj[cur.x].length; i++) {
                    if (adj[cur.x][i] == 1) {
                        list.add (new Node (i, cur));
                    }
                }
            }
        }
    }

    public static void main (String[] args) {
        int[][] adjacency_matrix = {
            {0, 1, 1, 0, 0},
            {1, 0, 0, 1, 0},
            {1, 0, 0, 0, 0},
            {0, 1, 0, 0, 1},
            {0, 0, 0, 1, 0}
        };
        int start = 0;
        int goal = 4;

        bfs (start, goal, adjacency_matrix);
    }

}

如何使用广度优先搜索在树中找到从一个顶点到另一个顶点的路径？

How to find a path from one vertex to another in a tree using breadth first search?

java

breadth-first-search