Блог

Существует представление графика Map<Integer, List<Integer>> , где ключевым значением является вершина, и у него есть список других вершин, которые мы можем получить. Карта может быть больше, а списки могут быть n size . Число 1 представляет начальную вершину, а наибольшее ключевое число в карте представляет цель.

Есть ли способ перебирать и собирать пути всех комбинаций путей, доступных от цели до начала?

Пример:

 { 2=[1], 3=[1], 4=[1], 5=[4, 2], 6=[4], 7=[1], 8=[7, 2], 9=[7, 3, 8] }
 

цель равна 9, а начало равно 1, поэтому результат List<List<Integer>> должен выглядеть следующим образом:

 [ [9, 7, 1], [9, 3, 1], [9, 8, 7, 1], [9, 8, 2, 1] ]
 

или без включения 1

 [ [9, 7], [9, 3], [9, 8, 7], [9, 8, 2] ]
 

Мой подход использует только первый элемент из списка

Родительские узлы — это Map<Integer, List<Integer>>

 List<Integer> path = new ArrayList<>();
List<Integer> nodes = Collections.singletonList(goal);
while(nodes != null amp;amp; nodes.size() > 0) {
        if (nodes.size() > 1) {
            if (nodes.get(0) != goal || nodes.get(1) != goal) {
                shortestPath.add(nodes.get(0));
                System.out.println(shortestPath);
            }
        } else {
            path.add(nodes.get(0));
        }
        nodes = parentNodes.get(nodes.get(0));

    }
    Collections.reverse(path);
 

и выводом является List<Integer> [9, 7] or reverse [7, 9] , который является одним из кратчайших путей

Ваша цель достижима с помощью dfs из самой большой вершины. Вам нужно сохранить путь и не посещать ни одну вершину, которая уже находится в пути. Подробное объяснение здесь. Вам просто нужно перейти ArrayList<Integer>[] adjList; на Map<Integer, List<Integer>> adjList;