Algoritmo di ricerca in ampiezza in Java

1. Panoramica

In questo tutorial, impareremo l'algoritmo di ricerca Breadth-First, che ci consente di cercare un nodo in un albero o in un grafico viaggiando attraverso i loro nodi in larghezza anziché in profondità.

Per prima cosa, esamineremo un po 'di teoria su questo algoritmo per alberi e grafici. Successivamente, ci immergeremo nelle implementazioni degli algoritmi in Java. Infine, tratteremo la loro complessità temporale.

2. Algoritmo di ricerca in base alla larghezza

L'approccio di base dell'algoritmo BFS (Breadth-First Search) consiste nel cercare un nodo in una struttura ad albero o grafo esplorando i vicini prima dei figli.

Per prima cosa, vedremo come funziona questo algoritmo per gli alberi. Dopodiché, lo adatteremo ai grafici, che hanno il vincolo specifico di contenere a volte i cicli. Infine, discuteremo le prestazioni di questo algoritmo.

2.1. Alberi

L'idea alla base dell'algoritmo BFS per gli alberi è di mantenere una coda di nodi che garantirà l'ordine di attraversamento. All'inizio dell'algoritmo, la coda contiene solo il nodo radice. Ripeteremo questi passaggi finché la coda contiene ancora uno o più nodi:

  • Apri il primo nodo dalla coda
  • Se quel nodo è quello che stiamo cercando, la ricerca è finita
  • Altrimenti, aggiungi i figli di questo nodo alla fine della coda e ripeti i passaggi

La terminazione dell'esecuzione è assicurata dall'assenza di cicli. Vedremo come gestire i cicli nella prossima sezione.

2.2. Grafici

Nel caso dei grafici, dobbiamo pensare a possibili cicli nella struttura. Se applichiamo semplicemente l'algoritmo precedente su un grafico con un ciclo, verrà ripetuto per sempre. Pertanto, dovremo mantenere una raccolta dei nodi visitati e assicurarci di non visitarli due volte :

  • Apri il primo nodo dalla coda
  • Controlla se il nodo è già stato visitato, in tal caso saltalo
  • Se quel nodo è quello che stiamo cercando, la ricerca è finita
  • Altrimenti, aggiungilo ai nodi visitati
  • Aggiungi i figli di questo nodo alla coda e ripeti questi passaggi

3. Implementazione in Java

Ora che la teoria è stata trattata, mettiamo le mani nel codice e implementiamo questi algoritmi in Java!

3.1. Alberi

Innanzitutto, implementeremo l'algoritmo ad albero. Progettiamo la nostra classe Tree , che consiste in un valore e figli rappresentati da un elenco di altri Tree :

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

Per evitare di creare cicli, i bambini vengono creati dalla classe stessa, in base a un dato valore.

Successivamente, forniamo un metodo search () :

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

Come accennato in precedenza, l'algoritmo BFS utilizza una coda per attraversare i nodi . Prima di tutto, aggiungiamo il nostro nodo radice a questa coda:

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

Quindi, dobbiamo eseguire il ciclo finché la coda non è vuota, e ogni volta che estraiamo un nodo dalla coda:

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

Se quel nodo è quello che stiamo cercando, lo restituiamo, altrimenti aggiungiamo i suoi figli alla coda :

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.

Perché non abbiamo avuto questo problema per la ricerca dell'albero? Perché il numero di connessioni in un albero è limitato dal numero di nodi. Il numero di connessioni in un albero di n nodi è n - 1 .

4. Conclusione

In questo articolo, abbiamo appreso l'algoritmo di ricerca Breadth-First e come implementarlo in Java.

Dopo aver approfondito un po 'di teoria, abbiamo visto le implementazioni Java dell'algoritmo e ne abbiamo discusso la complessità.

Come al solito, il codice è disponibile su GitHub.