Как пройти через график?

Question

У меня есть следующее дерево

     1
    2 3
   4 5 6
  7 8 9 0

Теперь я хочу пройти через все возможные пути через дерево.Всегда можно перейти к соседним номерам из ряда ниже.Например,

1 2 4 7 или 1 2 5 8

Любые намеки, каков наилучший способ сделать это?Я ищу общий совет, но в моей реализации у меня есть ArrayList для каждой строки.

Answer 1

Я подозреваю, что использование рекурсии - самый простой способ.

что-то вроде

public static void visit(List<List<Integer>> tree, Visitor<List<Integer>> visitor) {
    visit0(tree, visitor, Collections.<Integer>emptyList());
}

private static void visit0(List<List<Integer>> tree, 
                           Visitor<List<Integer>> visitor, List<Integer> list) {
    if (tree.isEmpty()) {
       visitor.onList(list);
       return;
    }

    List<List<Integer>> tree2 = tree.subList(1, tree.size() - 1);
    List<Integer> ints = new ArrayList<Integer>(list);
    ints.add(0); // dummy entry.
    for(int n: tree.get(0)) {
        ints.set(ints.size()-1, n);
        visit0(tree2, visitor, ints);
    }
}

Answer 2

Я думаю, что решение для академической оценки, подобное представленному в этой статье:

"APAC: точный алгоритм для извлечения циклов и путей во всех видах графиков" от Ricardo Simões

Краткое описание алгоритма:

Утверждается, что:

(a) Алгоритм находит все простые пути.

(b) Алгоритм находитвсе циклы.

(c) Алгоритм завершается.

(d) Сложность алгоритма O (Cnpaths).«(...) сложность линейно возрастает с увеличением числа путей (...)»

Автор использует псевдокодовую нотацию - то есть, я считаю, одну из самых универсальных.