Получение самой длинной подпути древовидной структуры - PullRequest
Новая
       16

Получение самой длинной подпути древовидной структуры

0 голосов
/ 16 декабря 2018

Я пишу функцию, которая поможет мне вычислить самый длинный подпуть древовидной структуры данных.То, что я написал до сих пор, использует рекурсивный метод, чтобы «копаться» в каждой подотрасли - в основном поиск в глубину.У меня нет большого контроля над tree, который является просто Map, где каждый ключ - это узел, а значение для каждого ключа - это список узлов, на которые указывает ключ.

Например, карта tree может иметь: 

"start" => ["1"]
"1" => ["2"]
"2" => ["3", "4"]
"3" => ["5"]
"4" => ["end"]
"5" => ["end"]

Я считаю, что код, который я написал ниже, решает мою проблему, заполняя список subLengths длинами всех подпутей вдерево.Все, что мне нужно сделать, это уменьшить subLengths, чтобы получить максимальную длину.

private void calculateAllSubPathLengths(String start, Map<String, List<String>> tree, int pathLength, List<Integer> subLengths){
    pathLength++;
    for(String connectedNode: tree.get(start)) {
        if(connectedNode.equals("end")) {
            subLengths.add(pathLength);
            return;
        }

        calculateAllSubPathLengths(connectedNode, tree, pathLength, subLengths);
    }
}

Я называю эту функцию следующим образом: 

int pathLength = 0;
List<Integer> subLengths = new ArrayList<>();
calculateAllSubPathLengths("start", tree, pathLength, subLengths);
// Get max from the subLengths list and move on with the rest of my logic

Я не имею большого контроля над данными внутри карты tree, и у нее нет традиционного дерева, такого каксвойства, как у бинарного дерева.Узлы в дереве могут иметь много ветвей, и оно может быть вложенным на много уровней глубиной.Но это очень маловероятно, учитывая мою проблемную область.Однако я хотел бы убедиться, что мой код может обрабатывать более сложные деревья, если они станут более вероятными в будущем.

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

  1. Есть ли способ избежать использования списка subLengths?
  2. Есть ли способ превратить эту рекурсивную функцию в интерактивную?Если нет, я, вероятно, добавлю какое-то условие, которое останавливает функцию, как только мы достигнем определенной «глубины».
  3. Существуют ли какие-либо другие "лучшие практики" рекурсии, которые я нарушаю?

1 Ответ

0 голосов
/ 16 декабря 2018

В вашем коде есть некоторые неопределенные переменные: links должно быть tree и subPathLengths должно быть subLengths.

Кроме этих проблем, код работает в этом случае (самый длинныйпуть 5), поэтому я отвечу на ваши вопросы и укажу случай, когда ваш код не работает.Везде, я предполагаю, что ваше дерево на самом деле является деревом (то есть ациклическим).

  1. Это кажется приемлемым методом.Ваше имя функции - calculateAllSubPathLengths, поэтому список выглядит подходящим для хранения всех путей.Если вы хотите только самое длинное (что имеет место), добавьте возвращаемое значение для вашей функции и передайте лучший результат в качестве параметра вместо subLengths.Вы также можете передать «по ссылке», используя один элемент int[] best, который избегает некоторых сравнений, но вызывает семантические проблемы.

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

    class Pair<K, V> {
    K first;
    V second;

    public Pair(K first, V second) {
        this.first = first;
        this.second = second;
    }
}

private static int longestPath(HashMap<String, List<String>> tree) {
    Stack<Pair<String, Integer>> stack = new Stack<>();
    stack.push(new Pair<String, Integer>("start", 0));
    int best = 0;

    while (!stack.isEmpty()) {
        Pair<String, Integer> current = stack.pop();

        if (current.first.equals("end")) {
            best = Math.max(current.second, best);
        }
        else {
            for (String child : tree.get(current.first)) {
                stack.push(
                    new Pair<String, Integer>(child, current.second + 1)
                );
            }
        }
    }

    return best;
}

    Попробуйте!

  3. Вот несколько советов по рекомендациям для рекурсивных функций:

    • Ваша реализация заставляет вызывающую программу отвечать за ряд переменных, которые по существу являются локальными для рекурсивной функции.Напишите вспомогательный метод для инкапсуляции этих переменных, чтобы предложить вызывающей стороне чистую опцию calculateAllSubPathLengths(tree);.

    • Увеличение pathLength в верхней части функции и тестирование connectedNode.equals("end") кажется нелогичным длярассматривая каждый узел или состояние как единый объект.Ваша функция спрашивает: "Является ли этот сосед текущего узла концом?"и «увеличить путь, затем проанализировать текущий узел», когда кажется более семантическим задавать вопрос: «Является ли этот узел концом?»и «проанализировать текущий узел, а затем увеличить путь при переходе к соседу», соответственно.Это также имеет логическое значение;например, если начальный узел является конечным узлом, ваш код потерпит неудачу.

    Соедините эти элементы вместе, вот возможный рефакторинг: 

    private static int longestPath(Map<String, List<String>> tree) {
    return longestPath("start", tree, 0, 0);
}

private static int longestPath(
    String current, Map<String, List<String>> tree, 
    int pathLength, int best
) {
    if (current.equals("end")) {
        return Math.max(pathLength, best);
    }

    for (String child : tree.get(current)) {
        best = Math.max(
            best, longestPath(child, tree, pathLength + 1, best)
        );
    }

    return best;
}

    Попробуйте!

    Даже здесь есть много областей для улучшения и обобщения.Например, жесткое кодирование состояний "start" и "end" подрывает возможность повторного использования.

...