1. Обзор
В этом уроке мы узнаем об алгоритме поиска в ширину, который позволяет нам искать узел в дереве или графе, путешествуя по их узлам в ширину, а не в глубину.
Во-первых, мы рассмотрим немного теории об этом алгоритме для деревьев и графов. После этого мы углубимся в реализацию алгоритмов на Java. Наконец, мы рассмотрим их временную сложность.
2. Алгоритм поиска в ширину
Основной подход алгоритма поиска в ширину (BFS) заключается в поиске узла в структуре дерева или графа путем изучения соседей до потомков.
Во-первых, мы увидим, как этот алгоритм работает для деревьев. После этого мы адаптируем его к графам, которые имеют определенное ограничение, заключающееся в том, что иногда они содержат циклы. Наконец, мы обсудим производительность этого алгоритма.
2.1. Деревья
Идея алгоритма BFS для деревьев состоит в том, чтобы поддерживать очередь узлов, которая обеспечит порядок обхода. В начале алгоритма очередь содержит только корневой узел. Мы будем повторять эти шаги до тех пор, пока очередь содержит один или несколько узлов:
- Вытолкнуть первый узел из очереди
- Если это тот узел, который мы ищем, то поиск окончен.
- В противном случае добавьте дочерние элементы этого узла в конец очереди и повторите шаги.
Прекращение выполнения обеспечивается отсутствием циклов. Мы увидим, как управлять циклами в следующем разделе.
2.2. Графики
В случае графов мы должны думать о возможных циклах в структуре. Если мы просто применим предыдущий алгоритм к графу с циклом, он зациклится навсегда. Поэтому нам нужно сохранить коллекцию посещенных узлов и убедиться, что мы не посещаем их дважды :
- Вытолкнуть первый узел из очереди
- Проверьте, был ли узел уже посещен, если да, пропустите его.
- Если это тот узел, который мы ищем, то поиск окончен.
- В противном случае добавьте его в посещенные узлы
- Добавьте дочерние элементы этого узла в очередь и повторите эти шаги.
3. Реализация на Java
Теперь, когда теория изучена, давайте приступим к коду и реализуем эти алгоритмы на Java!
3.1. Деревья
Во-первых, мы реализуем алгоритм дерева. Давайте создадим наш класс Tree , который состоит из значения и дочерних элементов, представленных списком других Tree s:
public class Tree<T> {
private T value;
private List<Tree<T>> children;
private Tree(T value) {
this.value = value;
this.children = new ArrayList<>();
}
public static <T> Tree<T> of(T value) {
return new Tree<>(value);
}
public Tree<T> addChild(T value) {
Tree<T> newChild = new Tree<>(value);
children.add(newChild);
return newChild;
}
}
Чтобы избежать создания циклов, дочерние элементы создаются самим классом на основе заданного значения.
После этого давайте обеспечим метод search() :
public static <T> Optional<Tree<T>> search(T value, Tree<T> root) {
//...
}
Как мы упоминали ранее, алгоритм BFS использует очередь для обхода узлов . Прежде всего, мы добавляем нашу корневую ноду в эту очередь:
Queue<Tree<T>> queue = new ArrayDeque<>();
queue.add(root);
Затем мы должны зацикливаться, пока очередь не пуста, и каждый раз, когда мы извлекаем узел из очереди:
while(!queue.isEmpty()) {
Tree<T> currentNode = queue.remove();
}
Если это тот узел, который мы ищем, мы возвращаем его, в противном случае мы добавляем его дочерние элементы в очередь :
if (currentNode.getValue().equals(value)) {
return Optional.of(currentNode);
} else {
queue.addAll(currentNode.getChildren());
}
Наконец, если мы посетили все узлы, но не нашли искомый, мы вернем пустой результат:
return Optional.empty();
Давайте теперь представим пример древовидной структуры:
Что переводится в код Java:
Tree<Integer> root = Tree.of(10);
Tree<Integer> rootFirstChild = root.addChild(2);
Tree<Integer> depthMostChild = rootFirstChild.addChild(3);
Tree<Integer> rootSecondChild = root.addChild(4);
Затем, если мы ищем значение 4, мы ожидаем, что алгоритм будет проходить узлы со значениями 10, 2 и 4 в следующем порядке:
BreadthFirstSearchAlgorithm.search(4, root)
Мы можем убедиться в этом, зарегистрировав значение посещенных узлов:
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 10
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 2
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 4
3.2. Графики
На этом история с деревьями заканчивается. Давайте теперь посмотрим, как работать с графиками. В отличие от деревьев графы могут содержать циклы. Это означает, как мы видели в предыдущем разделе, мы должны помнить узлы, которые мы посетили, чтобы избежать бесконечного цикла . Через мгновение мы увидим, как обновить алгоритм для решения этой проблемы, но сначала давайте определим структуру нашего графа:
public class Node<T> {
private T value;
private Set<Node<T>> neighbors;
public Node(T value) {
this.value = value;
this.neighbors = new HashSet<>();
}
public void connect(Node<T> node) {
if (this == node) throw new IllegalArgumentException("Can't connect node to itself");
this.neighbors.add(node);
node.neighbors.add(this);
}
}
Теперь мы видим, что, в отличие от деревьев, мы можем свободно соединять узел с другим, что дает нам возможность создавать циклы. Единственным исключением является то, что узел не может соединиться сам с собой.
Также стоит отметить, что в этом представлении нет корневого узла. Это не проблема, так как мы также сделали соединения между узлами двунаправленными. Это означает, что мы сможем выполнять поиск по графу, начиная с любого узла.
Прежде всего, давайте повторно используем алгоритм выше, адаптированный к новой структуре:
public static <T> Optional<Node<T>> search(T value, Node<T> start) {
Queue<Node<T>> queue = new ArrayDeque<>();
queue.add(start);
Node<T> 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.debug("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<Node<T>> alreadyVisited = new HashSet<>();
Затем, когда сравнение значений не удается, мы добавляем узел в посещенные :
alreadyVisited.add(currentNode);
Наконец, после добавления соседей узла в очередь, мы удаляем из нее уже посещенные узлы (это альтернативный способ проверки присутствия текущего узла в этом наборе):
queue.removeAll(alreadyVisited);
Делая это, мы гарантируем, что алгоритм не попадет в бесконечный цикл.
Давайте посмотрим, как это работает на примере. Прежде всего, мы определим граф с циклом:
И то же самое в коде Java:
Node<Integer> start = new Node<>(10);
Node<Integer> firstNeighbor = new Node<>(2);
start.connect(firstNeighbor);
Node<Integer> firstNeighborNeighbor = new Node<>(3);
firstNeighbor.connect(firstNeighborNeighbor);
firstNeighborNeighbor.connect(start);
Node<Integer> secondNeighbor = new Node<>(4);
start.connect(secondNeighbor);
Давайте снова скажем, что мы хотим найти значение 4. Поскольку корневого узла нет, мы можем начать поиск с любого узла, который захотим, и мы выберем firstNeighborNeighbor :
BreadthFirstSearchAlgorithm.search(4, firstNeighborNeighbor);
Опять же, мы добавим журнал, чтобы увидеть, какие узлы посещены, и мы ожидаем, что их будет 3, 2, 10 и 4, только один раз каждый в этом порядке:
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 3
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 2
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 10
[main] DEBUG c.b.a.b.BreadthFirstSearchAlgorithm - Visited node with value: 4
3.3. Сложность
Теперь, когда мы рассмотрели оба алгоритма в Java, давайте поговорим об их временной сложности. Мы будем использовать нотацию Big-O, чтобы выразить их.
Начнем с алгоритма дерева. Он добавляет узел в очередь не более одного раза, поэтому также посещает его не более одного раза. Таким образом, если 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 .