Поиск в глубину в Java

23 мая 2022 г. · 5 мин. чтения

1. Обзор

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

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

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

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

2. Поиск в глубину дерева

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

Обход предзаказа
Неупорядоченный обход
Почтовый обход

2.1. Обход предзаказа

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

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

Посетить текущий узел
Обход левого поддерева
Обход правого поддерева

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

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

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

Вставьте root в наш стек
Пока стек не пуст
Вытолкнуть текущий узел
Посетить текущий узел
Нажмите правый дочерний элемент, затем левый дочерний элемент, чтобы сложить

public void traversePreOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    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);
    }
}

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

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

public void traverseInOrderWithoutRecursion() {
    Stack stack = new Stack<>();
    Node current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        Node top = stack.pop();
        visit(top.value);
        current = top.right;
    }
}

2.3. Почтовый обход

Наконец, при обходе в обратном порядке мы проходим левое и правое поддерево до того, как проходим корень .

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

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

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

Поместить корневой узел в стек ``
Пока стек не пуст
Проверяем, прошли ли мы уже левое и правое поддерево
Если нет, то поместите правый дочерний элемент и левый дочерний элемент в стек

public void traversePostOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    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<Integer> stack = new Stack<Integer>();
    boolean[] isVisited = new boolean[adjVertices.size()];
    stack.push(start);
    while (!stack.isEmpty()) {
        int current = stack.pop();
        if(!isVisited[current]){
            isVisited[current] = true;
            visit(current);
            for (int dest : adjVertices.get(current)) {
                if (!isVisited[dest])
                    stack.push(dest);
            }
    }
}

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

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

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

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

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

public List<Integer> topologicalSort(int start) {
    LinkedList<Integer> result = new LinkedList<Integer>();
    boolean[] isVisited = new boolean[adjVertices.size()];
    topologicalSortRecursive(start, isVisited, result);
    return result;
}

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

4. Вывод

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

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

1. Обзор​

2. Поиск в глубину дерева​

2.1. Обход предзаказа​

2.2. Неупорядоченный обход​

2.3. Почтовый обход​

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

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

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

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

4. Вывод​