Рубрики
Без рубрики

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

Руководство по алгоритму поиска в глубину на Java, использующему как древовидные, так и графические структуры данных.

Автор оригинала: baeldung.

1. Обзор

В этом уроке мы рассмотрим углубленный поиск на Java.

Поиск по глубине (DFS) -это алгоритм обхода, используемый как для древовидной, так и для графовой структур данных|/. Поиск по глубине сначала углубляется в каждую ветвь, прежде чем перейти к изучению другой ветви .

В следующих разделах мы сначала рассмотрим реализацию дерева, а затем Графика.

Чтобы узнать, как реализовать эти структуры в Java, ознакомьтесь с нашими предыдущими учебными пособиями по двоичному дереву и графику .

2. Глубина дерева-первый поиск

Существует три различных порядка обхода дерева с помощью DFS:

  1. Обход предварительного заказа
  2. Обход По Порядку
  3. Обход после заказа

2.1. Обход Предварительного Заказа

При обходе по предварительному заказу мы сначала проходим корень, затем левое и правое поддеревья.

Мы можем просто реализовать обход предварительного заказа с помощью рекурсии :

  • Посетите текущий узел
  • Пересечение влево поддерево
  • Пересечение вправо поддерево
public void traversePreOrder(Node node) {
    if (node != null) {
        visit(node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

Мы также можем реализовать обход предварительного заказа без рекурсии.

Для реализации итеративного обхода предварительного заказа нам понадобится Стек , и мы выполним следующие действия:

  • Нажмите root в нашем s tack

  • Пока стек не пуст

    • Pop текущий узел
    • Посетите текущий узел
    • Нажмите вправо дочерний элемент, затем влево дочерний элемент в стек
public void traversePreOrderWithoutRecursion() {
    Stack stack = new Stack();
    Node current = root;
    stack.push(root);
    while(!stack.isEmpty()) {
        current = stack.pop();
        visit(current.value);
        
        if(current.right != null) {
            stack.push(current.right);
        }    
        if(current.left != null) {
            stack.push(current.left);
        }
    }        
}

2.2. Обход По Порядку

Для обхода по порядку мы сначала проходим левое поддерево, затем корневое, затем, наконец, правое поддерево .

Обход по порядку для двоичного дерева поиска означает обход узлов в порядке возрастания их значений.

Мы можем просто реализовать обход по порядку, используя рекурсию:

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        visit(node.value);
        traverseInOrder(node.right);
    }
}

Мы также можем реализовать обход по порядку без рекурсии , тоже:

  • Нажмите корневой узел на s галс

  • В то время как s галс не пуст

    • Продолжайте нажимать влево дочерний элемент в стек, пока мы не достигнем текущего самого левого дочернего узла
    • Посетите текущий узел
    • Нажмите вправо дочерний элемент на стек
public void traverseInOrderWithoutRecursion() {
    Stack stack = new Stack();
    Node current = root;
    stack.push(root);
    while(! stack.isEmpty()) {
        while(current.left != null) {
            current = current.left;                
            stack.push(current);                
        }
        current = stack.pop();
        visit(current.value);
        if(current.right != null) {
            current = current.right;                
            stack.push(current);
        }
    }
}

2.3. Обход После Заказа

Наконец, при обходе после заказа мы проходим левое и правое поддерево, прежде чем перейдем к корню .

Мы можем следовать нашему предыдущему рекурсивному решению :

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        visit(node.value);
    }
}

Или мы также можем реализовать обход после заказа без рекурсии :

  • Нажмите корневой узел в s галс

  • В то время как s галс не пуст

    • Проверьте, прошли ли мы уже левое и правое поддерево
    • Если нет, то нажмите вправо дочерний элемент и влево дочерний элемент в стек
public void traversePostOrderWithoutRecursion() {
    Stack stack = new Stack();
    Node prev = root;
    Node current = root;
    stack.push(root);

    while (!stack.isEmpty()) {
        current = stack.peek();
        boolean hasChild = (current.left != null || current.right != null);
        boolean isPrevLastChild = (prev == current.right || 
          (prev == current.left && current.right == null));

        if (!hasChild || isPrevLastChild) {
            current = stack.pop();
            visit(current.value);
            prev = current;
        } else {
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }   
}

3. Глубина графика-первый поиск

Основное различие между графами и деревьями заключается в том, что графики могут содержать циклы .

Поэтому, чтобы избежать циклического поиска, мы будем отмечать каждый узел при его посещении.

Мы увидим две реализации для графовых DFS, с рекурсией и без рекурсии.

3.1. График DFS с рекурсией

Во-первых, давайте начнем просто с рекурсии:

  • Мы начнем с заданного узла
  • Отметьте текущий узел как посещенный
  • Посетите текущий узел
  • Пересеките не посещенные соседние вершины
public void dfs(int start) {
    boolean[] isVisited = new boolean[adjVertices.size()];
    dfsRecursive(start, isVisited);
}

private void dfsRecursive(int current, boolean[] isVisited) {
    isVisited[current] = true;
    visit(current);
    for (int dest : adjVertices.get(current)) {
        if (!isVisited[dest])
            dfsRecursive(dest, isVisited);
    }
}

3.2. График DFS без рекурсии

Мы также можем реализовать графовые DFS без рекурсии. Мы просто будем использовать Стек :

  • Мы начнем с заданного узла
  • Вставьте запуск узел в стек

  • В то время как Стек не пуст

    • Отметьте текущий узел как посещенный
    • Посетите текущий узел
    • Нажмите на не посещенные соседние вершины
public void dfsWithoutRecursion(int start) {
    Stack stack = new Stack();
    boolean[] isVisited = new boolean[adjVertices.size()];
    stack.push(start);
    while (!stack.isEmpty()) {
        int current = stack.pop();
        isVisited[current] = true;
        visit(current);
        for (int dest : adjVertices.get(current)) {
            if (!isVisited[dest])
                stack.push(dest);
        }
    }
}

3.4. Топологическая Сортировка

Существует множество приложений для поиска по глубине графика в первую очередь. Одним из известных приложений для DFS является топологическая сортировка.

Топологическая сортировка для ориентированного графа – это линейное упорядочение его вершин таким образом, чтобы для каждого ребра исходный узел находился перед конечным.

Чтобы получить топологическую сортировку, нам понадобится простое дополнение к DFS, которое мы только что реализовали:

  • Нам нужно сохранить посещенные вершины в стеке, потому что топологическая сортировка-это посещенные вершины в обратном порядке
  • Мы помещаем посещенный узел в стек только после обхода всех его соседей
public List topologicalSort(int start) {
    LinkedList result = new LinkedList();
    boolean[] isVisited = new boolean[adjVertices.size()];
    topologicalSortRecursive(start, isVisited, result);
    return result;
}

private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList result) {
    isVisited[current] = true;
    for (int dest : adjVertices.get(current)) {
        if (!isVisited[dest])
            topologicalSortRecursive(dest, isVisited, result);
    }
    result.addFirst(current);
}

4. Заключение

В этой статье мы обсудили углубленный поиск как для древовидной, так и для графовой структур данных.

Полный исходный код доступен на GitHub .

Читайте ещё по теме: