Блог

Главная - Вопросы по программированию - Проблема с расстоянием между двумя узлами в алгоритме дерева

Проблема с расстоянием между двумя узлами в алгоритме дерева

#java #algorithm #tree #nodes

#java #алгоритм #дерево #узлы

Вопрос:

Мне нужно вычислить расстояние между двумя узлами в дереве. Я реализовал общую формулу:

 Dist(n1,n2) = Dist(root,n1), Dist(root,n2) - 2*Dist(root,lca)

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

 public static int distance(Tree t, Node<String> node1, Node<String> node2)
{
    Node<String> lca = lca(node1, node2);
    //This if statement is when the input contains the root itself
    //this means that the distance is simply from the node and the root
    if(lca==null)
    {
        // the function getNumberOfAncestors returns exactly the distance between a generic node and the root, since I count parent by parent and so on.
        return node1.getNumberOfAncestors()   node2.getNumberOfAncestors();
    }

    return node1.getNumberOfAncestors()   node2.getNumberOfAncestors() - 2*distance(t, t.getRoot(), lca);
}

Для простого дерева:

    A
 B   C
D E F G

Мы знаем, что Dist(C,G) = 1, но мой алгоритм возвращает 3.
Есть идеи?

Комментарии:

1. Попробуйте BFS. Это очень просто, хорошо документировано, а также предоставит вам кратчайший путь между начальным узлом и любым другим узлом.

2. Для отладки вам следует в первую очередь вывести node1.getNumberOfAncestors(), node2.getNumberOfAncestors() и distance(t, t.getRoot(), lca). Чтобы убедиться, что все 3 значения верны. Редактировать: Также есть причина, по которой вы не используете getNumberOfAncestors() в lca?

Ответ №1:

Пожалуйста, предоставьте реализацию метода lca, чтобы мы могли проверить, правильно ли он работает. Я почти уверен, что distance возвращает 3, потому что lca(node1, node2) равно нулю. В этом случае lca == null имеет значение true, и метод возвращает

node1.getNumberOfAncestors() node2.getNumberOfAncestors()

что в основном

node1.getNumberOfAncestors() = 1 для C

node2.getNumberOfAncestors() = 2 для G = 3