Как найти путь от одной вершины к другой в дереве, используя поиск в ширину?

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 *, вероятно, то, что вы хотите использовать. Это зависит, хотя. Похоже, вы описываете алгоритм поиска пути, а не поиск узлов.