Алгоритм поиска по ширине в Java

Автор оригинала: François Dupire.

1. Обзор

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

Сначала мы рассмотрим немного теории об этом алгоритме для деревьев и графиков. После этого мы погрузимся в реализацию алгоритмов на Java. Наконец, мы рассмотрим их временную сложность.

2. Алгоритм Поиска По Ширине

Основной подход алгоритма поиска по ширине (BFS) заключается в поиске узла в структуре дерева или графика путем изучения соседей до детей.

Сначала мы посмотрим, как этот алгоритм работает для деревьев. После этого мы адаптируем его к графикам, которые имеют определенное ограничение, иногда содержащее циклы. Наконец, мы обсудим производительность этого алгоритма.

2.1. Деревья

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

• Выберите первый узел из очереди
• Если этот узел-тот, который мы ищем, то поиск окончен
• В противном случае добавьте дочерние элементы этого узла в конец очереди и повторите действия

Завершение выполнения обеспечивается отсутствием циклов. Мы увидим, как управлять циклами в следующем разделе.

2.2. Графики

В случае графиков мы должны подумать о возможных циклах в структуре. Если мы просто применим предыдущий алгоритм к графику с циклом, он будет зацикливаться вечно. Поэтому нам нужно будет сохранить коллекцию посещенных узлов и убедиться, что мы не посещаем их дважды :

• Выберите первый узел из очереди
• Проверьте, был ли узел уже посещен, если да, пропустите его
• Если этот узел-тот, который мы ищем, то поиск окончен
• В противном случае добавьте его в посещенные узлы
• Добавьте дочерние элементы этого узла в очередь и повторите следующие действия

3. Реализация на Java

Теперь, когда теория рассмотрена, давайте возьмемся за код и реализуем эти алгоритмы на Java!

3.1. Деревья

Сначала мы реализуем древовидный алгоритм. Давайте создадим наш Дерево класс, который состоит из значения и дочерних элементов, представленных списком других Деревьев :

public class Tree {
    private T value;
    private List> children;

    private Tree(T value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public static  Tree of(T value) {
        return new Tree<>(value);
    }

    public Tree addChild(T value) {
        Tree newChild = new Tree<>(value);
        children.add(newChild);
        return newChild;
    }
}

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

После этого давайте предоставим метод search() :

public static  Optional> search(T value, Tree root) {
    //...
}

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

Queue> queue = new ArrayDeque<>();
queue.add(root);

Затем мы должны зацикливаться, пока очередь не пуста, и каждый раз, когда мы вытаскиваем узел из очереди:

while(!queue.isEmpty()) {
    Tree currentNode = queue.remove();
}

Если этот узел является тем, который мы ищем, мы возвращаем его, в противном случае мы добавляем его дочерние элементы в очередь :

if (currentNode.getValue().equals(value)) {
    return Optional.of(currentNode);
} else {
    queue.addAll(currentNode.getChildren());
}

Наконец, если мы посетили все узлы, не найдя тот, который мы ищем, мы вернем пустой результат:

return Optional.empty();

Давайте теперь представим пример древовидной структуры:

Что переводится в Java-код:

Tree root = Tree.of(10);
Tree rootFirstChild = root.addChild(2);
Tree depthMostChild = rootFirstChild.addChild(3);
Tree rootSecondChild = root.addChild(4);

Затем, при поиске значения 4, мы ожидаем, что алгоритм будет пересекать узлы со значениями 10, 2 и 4 в таком порядке:

BreadthFirstSearchAlgorithm.search(4, root)

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

[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 10
[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 2 
[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 4

3.2. Графики

На этом заканчивается случай с деревьями. Давайте теперь посмотрим, как работать с графиками. В отличие от деревьев, графики могут содержать циклы. Это означает, как мы видели в предыдущем разделе, мы должны помнить узлы, которые мы посетили, чтобы избежать бесконечного цикла . Через мгновение мы увидим, как обновить алгоритм для рассмотрения этой проблемы, но сначала давайте определим структуру нашего графика:

public class Node {
    private T value;
    private Set> neighbors;

    public Node(T value) {
        this.value = value;
        this.neighbors = new HashSet<>();
    }

    public void connect(Node node) {
        if (this == node) throw new IllegalArgumentException("Can't connect node to itself");
        this.neighbors.add(node);
        node.neighbors.add(this);
    }
}

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

Также стоит отметить, что в этом представлении нет корневого узла. Это не проблема, так как мы также сделали соединения между узлами двунаправленными. Это означает, что мы сможем выполнять поиск по графику, начиная с любого узла.

Прежде всего, давайте повторно используем алгоритм сверху, адаптированный к новой структуре:

public static  Optional> search(T value, Node start) {
    Queue> queue = new ArrayDeque<>();
    queue.add(start);

    Node currentNode;

    while (!queue.isEmpty()) {
        currentNode = queue.remove();

        if (currentNode.getValue().equals(value)) {
            return Optional.of(currentNode);
        } else {
            queue.addAll(currentNode.getNeighbors());
        }
    }

    return Optional.empty();
}

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

while (!queue.isEmpty()) {
    currentNode = queue.remove();
    LOGGER.info("Visited node with value: {}", currentNode.getValue());

    if (currentNode.getValue().equals(value)) {
        return Optional.of(currentNode);
    } else {
        alreadyVisited.add(currentNode);
        queue.addAll(currentNode.getNeighbors());
        queue.removeAll(alreadyVisited);
    }
}

return Optional.empty();

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

Set> alreadyVisited = new HashSet<>();

Затем, когда сравнение значений не удается, мы добавляем узел к посещенным :

alreadyVisited.add(currentNode);

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

queue.removeAll(alreadyVisited);

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

Давайте посмотрим, как это работает на примере. Прежде всего, мы определим график с циклом:

И то же самое в коде Java:

Node start = new Node<>(10);
Node firstNeighbor = new Node<>(2);
start.connect(firstNeighbor);

Node firstNeighborNeighbor = new Node<>(3);
firstNeighbor.connect(firstNeighborNeighbor);
firstNeighborNeighbor.connect(start);

Node secondNeighbor = new Node<>(4);
start.connect(secondNeighbor);

Давайте еще раз скажем, что мы хотим найти значение 4. Поскольку корневого узла нет, мы можем начать поиск с любого нужного нам узла и выберем firstNeighborNeighbor :

BreadthFirstSearchAlgorithm.search(4, firstNeighborNeighbor);

Опять же, мы добавим журнал, чтобы увидеть, какие узлы посещены, и мы ожидаем, что их будет 3, 2, 10 и 4, только по одному разу в этом порядке:

[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 3
[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 2
[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 10
[main] INFO  c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 4

3.3. Сложность

Теперь, когда мы рассмотрели оба алгоритма на Java, давайте поговорим об их временной сложности. Мы будем использовать обозначение “Большой О”, чтобы выразить их.

Давайте начнем с древовидного алгоритма. Он добавляет узел в очередь не более одного раза, поэтому также посещает его не более одного раза. Таким образом, если n – это количество узлов в дереве, временная сложность алгоритма будет O(n) .

Теперь, для графического алгоритма, все немного сложнее. Мы пройдем через каждый узел не более одного раза, но для этого мы будем использовать операции линейной сложности, такие как addAll() и removeAll() .

Давайте рассмотрим n количество узлов и c количество соединений графа. Затем, в худшем случае (если узел не найден), мы могли бы использовать addAll() и removeAll() методы для добавления и удаления узлов до количества соединений, что дает нам O(c) сложность для этих операций. Итак, при условии, что c > n , сложность общего алгоритма будет O(c) . В противном случае это будет O(n) . Это , как правило, отмечено O(n + c) , что может быть интерпретировано как сложность в зависимости от наибольшего числа между n и c .

Почему у нас не было этой проблемы при поиске по дереву? Потому что количество соединений в дереве ограничено количеством узлов. Количество соединений в дереве n узлов равно n – 1 .

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

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

После небольшого теоретического изучения мы увидели реализации алгоритма на Java и обсудили его сложность.

Как обычно, код доступен на GitHub .