Как найти путь между 2 узлами в дереве? - PullRequest
Новая
       29

Как найти путь между 2 узлами в дереве?

1 голос
/ 13 апреля 2020

Я пытаюсь найти путь между 2 узлами дерева, используя java, но я получаю неправильный ответ

'' '

public static void dfs(int source ,int destination ,ArrayList<Integer> path ,ArrayList<Integer> graph[] ,boolean vis[]){
    path.add(x);
    if(source == destination)
    return ;
    vis[source] = true;
    flag = 0;
    if(graph[source].size()!=0){
        for (int j : graph[source]){
            if(vis[j] == false){
                dfs(j,destination,path,graph,vis)
                flag = 1;
            }
        }
    }
    if(flag == 0){
        path.remove(path.size()-1);
    }
}

' ''

для дерева из 11 узлов, ребра которого заданы
1 2
2 3
2 4
2 8
4 5
4 6
4 7
8 9
8 10
8 11
путь между узлами 1 и 8 должен быть: 1-> 2-> 8, но с этим кодом результат будет 1-> 2- > 4-> 8
Аналогично, путь между узлами 3 и 6 должен быть: 3-> 2-> 4-> 6, но этот код выдает: 3-> 2-> 4-> 6-> 8. Почему это происходит?

1 Ответ

1 голос
/ 13 апреля 2020

У вас есть некоторые переменные, не объявленные в методе dfs. Особенно в рекурсивных вызовах вы должны быть осторожны с тем, что должно быть объявлено как локальная переменная, что должно передаваться через параметры и что может быть объявлено как глобальная переменная stati c.

Ваша реализация отслеживания возврата dfs неверна. Вы накапливаете все узлы, которые вы прошли в path, а не путь к цели.

Вам необходимо изменить дизайн кода. Например, вместо возврата void ваша функция может возвращать логическое значение, если поиск будет успешным. Тогда вы можете решить не изменять path больше. В качестве альтернативы ваша функция может вернуть path цели.

Лучшая реализация для этого dfs может быть: 

public static boolean dfs(int source, int destination, 
                          List<Integer> path, 
                          List<Integer> graph[], 
                          boolean vis[]) {
    path.add(source);
    if (source == destination) {
        return true;
    }
    vis[source] = true;
    if (!graph[source].isEmpty()) {
        for (int j : graph[source]) {
            if (!vis[j]) {
                if (dfs(j, destination, path, graph, vis)) {
                    return true;
                }
            }
        }
    }
    path.remove(path.size() - 1);
    return false;
}
...