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

Question

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

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

Answer 1

如果你真的想用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);
    }
}

Answer 2

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