Algoritmo de búsqueda primero en amplitud en Java

Programación

1. Información general

En este tutorial, aprenderemos sobre el algoritmo Breadth-First Search, que nos permite buscar un nodo en un árbol o un gráfico viajando a través de sus nodos primero en amplitud en lugar de en profundidad.

Primero, repasaremos un poco de teoría sobre este algoritmo para árboles y gráficos. Después de eso, nos sumergiremos en las implementaciones de los algoritmos en Java. Finalmente, cubriremos su complejidad de tiempo.

2. Algoritmo de búsqueda en amplitud primero

El enfoque básico del algoritmo Breadth-First Search (BFS) es buscar un nodo en una estructura de árbol o gráfico explorando los vecinos antes que los niños.

Primero, veremos cómo funciona este algoritmo para árboles. Después de eso, lo adaptaremos a los gráficos, que tienen la restricción específica de contener a veces ciclos. Finalmente, discutiremos el rendimiento de este algoritmo.

2.1. Árboles

La idea detrás del algoritmo BFS para árboles es mantener una cola de nodos que asegurará el orden de recorrido. Al comienzo del algoritmo, la cola contiene solo el nodo raíz. Repetiremos estos pasos siempre que la cola aún contenga uno o más nodos:

  • Pop el primer nodo de la cola
  • Si ese nodo es el que estamos buscando, entonces la búsqueda ha terminado.
  • De lo contrario, agregue los hijos de este nodo al final de la cola y repita los pasos

La terminación de la ejecución está asegurada por la ausencia de ciclos. Veremos cómo gestionar los ciclos en la siguiente sección.

2.2. Gráficos

En el caso de los gráficos, debemos pensar en posibles ciclos en la estructura. Si simplemente aplicamos el algoritmo anterior en un gráfico con un ciclo, se repetirá para siempre. Por lo tanto, necesitaremos mantener una colección de los nodos visitados y asegurarnos de no visitarlos dos veces :

  • Pop el primer nodo de la cola
  • Compruebe si el nodo ya ha sido visitado, si es así, omítalo
  • Si ese nodo es el que estamos buscando, entonces la búsqueda ha terminado.
  • De lo contrario, agréguelo a los nodos visitados
  • Agregue los hijos de este nodo a la cola y repita estos pasos

3. Implementación en Java

Ahora que se ha cubierto la teoría, ¡pongámonos las manos en el código e implementemos estos algoritmos en Java!

3.1. Árboles

Primero, implementaremos el algoritmo del árbol. Diseñemos nuestra clase Tree , que consta de un valor y elementos secundarios representados por una lista de otros árboles :

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; } }

Para evitar la creación de ciclos, los niños son creados por la propia clase, basándose en un valor dado.

Después de eso, proporcionemos un método de búsqueda () :

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

Como mencionamos anteriormente, el algoritmo BFS usa una cola para atravesar los nodos . En primer lugar, agregamos nuestro nodo raíz a esta cola:

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

Luego, tenemos que hacer un bucle mientras la cola no está vacía, y cada vez que sacamos un nodo de la cola:

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

Si ese nodo es el que estamos buscando, lo devolvemos, de lo contrario agregamos sus hijos a la cola :

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

Finally, if we visited all the nodes without finding the one we're searching for, we return an empty result:

return Optional.empty();

Let's now imagine an example tree structure:

Which translates into the Java code:

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

Then, if searching for the value 4, we expect the algorithm to traverse nodes with values 10, 2 and 4, in that order:

BreadthFirstSearchAlgorithm.search(4, root)

We can verify that with logging the value of the visited nodes:

[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. Graphs

That concludes the case of trees. Let's now see how to deal with graphs. Contrarily to trees, graphs can contain cycles. That means, as we've seen in the previous section, we have to remember the nodes we visited to avoid an infinite loop. We'll see in a moment how to update the algorithm to consider this problem, but first, let's define our graph structure:

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); } }

Now, we can see that, in opposition to trees, we can freely connect a node with another one, giving us the possibility to create cycles. The only exception is that a node can't connect to itself.

It's also worth noting that with this representation, there is no root node. This is not a problem, as we also made the connections between nodes bidirectional. That means we'll be able to search through the graph starting at any node.

First of all, let's reuse the algorithm from above, adapted to the new structure:

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(); }

We can't run the algorithm like this, or any cycle will make it run forever. So, we must add instructions to take care of the already visited nodes:

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();

As we can see, we first initialize a Set that'll contain the visited nodes.

Set
    
      alreadyVisited = new HashSet();

Then, when the comparison of values fails, we add the node to the visited ones:

alreadyVisited.add(currentNode);

Finally, after adding the node's neighbors to the queue, we remove from it the already visited nodes (which is an alternative way of checking the current node's presence in that set):

queue.removeAll(alreadyVisited);

By doing this, we make sure that the algorithm won't fall into an infinite loop.

Let's see how it works through an example. First of all, we'll define a graph, with a cycle:

And the same in Java code:

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);

Let's again say we want to search for the value 4. As there is no root node, we can begin the search with any node we want, and we'll choose firstNeighborNeighbor:

BreadthFirstSearchAlgorithm.search(4, firstNeighborNeighbor);

Again, we'll add a log to see which nodes are visited, and we expect them to be 3, 2, 10 and 4, only once each in that order:

[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. Complexity

Now that we've covered both algorithms in Java, let's talk about their time complexity. We'll use the Big-O notation to express them.

Let's start with the tree algorithm. It adds a node to the queue at most once, therefore visiting it at most once also. Thus, if n is the number of nodes in the tree, the time complexity of the algorithm will be O(n).

Now, for the graph algorithm, things are a little bit more complicated. We'll go through each node at most once, but to do so we'll make use of operations having linear-complexity such as addAll() and removeAll().

Let's consider n the number of nodes and c the number of connections of the graph. Then, in the worst case (being no node found), we might use addAll() and removeAll() methods to add and remove nodes up to the number of connections, giving us O(c) complexity for these operations. So, provided that c > n, the complexity of the overall algorithm will be O(c). Otherwise, it'll be O(n). This is generally noted O(n + c), which can be interpreted as a complexity depending on the greatest number between n and c.

¿Por qué no tuvimos este problema para la búsqueda del árbol? Porque el número de conexiones en un árbol está limitado por el número de nodos. El número de conexiones en un árbol de n nodos es n - 1 .

4. Conclusión

En este artículo, aprendimos sobre el algoritmo Breadth-First Search y cómo implementarlo en Java.

Después de analizar un poco de teoría, vimos las implementaciones de Java del algoritmo y discutimos su complejidad.

Como de costumbre, el código está disponible en GitHub.