Преобразование поиска в ширину в поиск в глубину в Java

Question

прошло много времени с тех пор, как я коснулся Java, поэтому это может показаться странным вопросом. В настоящее время у меня есть этот код поиска в ширину, который я нашел здесь в StackOverflow, у меня он изменен на моем конце, но я опубликую оригинальный код здесь.

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                        q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
}
return directions;
}

Мне известны другие алгоритмы поиска в глубину, но мне также сказали, что можно легко преобразовать поиск в ширину в поиск в глубину, и я бы лучше понял, если бы это было сделано с этим кодом вместо 2 совершенно разные коды.

Как мне изменить это на поиск в глубину?

Answer 1

Основное различие между первой глубиной и кулаком ширины - это порядок, в котором вы исследуете узлы на своей "границе" (список узлов, которые вам еще предстоит исследовать).

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

Если, с другой стороны, вы исследуете вновь добавленные узлы (исходящие узлы из вашей текущей позиции), до узлов, которые вы добавили ранее (которые принадлежат к «верхним» уровням дерева), то сначала вы будете исследовать глубину дерева.

С точки зрения структур данных вам нужен стек вместо очереди, но я думаю,объяснение может пригодиться.

Answer 2

Вам нужно заменить q.add(node) (который добавляет в конец списка) на q.add(0, node) (добавить в начале). В основном, используйте stack вместо queue.

Очевидно, вам придется использовать интерфейс List вместо Queue для доступа к LinkedList.

Answer 3

Deque<Node> q = new LinkedList<Node>();

и используйте pop и push вместо remove и add

в основном удаляет с той же стороны, которую вы добавили (обычные remove и add - базовые операции очереди LIFO) глубина сначала использует стек FIFO

и другие алгоритмы поиска, по сути, одинаковы, но используют разные типы очередей (например, для активного поиска используется самый простой следующий шаг)

Answer 4

Заменить Queue и LinkedList на Stack, add на push и remove на pop