дает ограничение времени выполнения, которое является полиномиальным по длине кодирования графа; это означает, что поиск в ширину, в общем, не может генерировать все возможные пути от данного источника к данному терминалу. Кроме того, если граф содержит цикл, число путей может быть бесконечным посредством повторения цикла.

тоящее время я пытаюсь пройти все пути от источника до места назначения в графе, который использует матрицу смежности. Я пытался сделать это способом BFS. Спасибо за помощь. Я получаю только один путь. Как мне распечатать другие пути?

public class AllPossiblePaths {
    static int v;
    static ArrayList<Integer> adj[];

    public AllPossiblePaths(int v) {
        this.v = v;
        adj = new ArrayList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    // add edge from u to v
    public static void addEdge(int u, int v) {
        adj[u].add(v);
    }

    public static void findpaths(int source, int destination) {
        LinkedList<ArrayList<Integer>> q = new LinkedList<>();
        boolean visited[] = new boolean[v];

        LinkedList<Integer> queue = new LinkedList<Integer>();

        queue.add(source);
        visited[source] = true;
        ArrayList<Integer> localPath = new ArrayList<>();
        while (!queue.isEmpty()) {
            // Dequeue a vertex from queue and print it
            int src = queue.poll();
            if (!localPath.contains(src)) {
                localPath.add(src);
            }
            if (src == destination) {
                System.out.println(localPath);
                localPath.remove(localPath.size() - 1);
                visited[src] = false;
            }

            Iterator<Integer> i = adj[src].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    queue.add(n);
                }
            }
        }
    }
}

Ответы на вопрос(2)

Ваш ответ на вопрос