Автор оригинала: 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 staticOptional > search(T value, Tree root) { //... }
Как мы упоминали ранее, алгоритм BFS использует очередь для обхода узлов . Прежде всего, мы добавляем наш корневой узел в эту очередь:
Queue> queue = new ArrayDeque<>(); queue.add(root);
Затем мы должны зацикливаться, пока очередь не пуста, и каждый раз, когда мы вытаскиваем узел из очереди:
while(!queue.isEmpty()) { TreecurrentNode = queue.remove(); }
Если этот узел является тем, который мы ищем, мы возвращаем его, в противном случае мы добавляем его дочерние элементы в очередь :
if (currentNode.getValue().equals(value)) { return Optional.of(currentNode); } else { queue.addAll(currentNode.getChildren()); }
Наконец, если мы посетили все узлы, не найдя тот, который мы ищем, мы вернем пустой результат:
return Optional.empty();
Давайте теперь представим пример древовидной структуры:
Что переводится в Java-код:
Treeroot = 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 staticOptional > 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:
Nodestart = 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 .