Algorithme de recherche étendue en premier en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons en apprendre davantage sur l'algorithme de recherche en largeur d'abord, qui nous permet de rechercher un nœud dans un arbre ou un graphique en parcourant leurs nœuds en commençant par la largeur plutôt que par la profondeur.

Tout d'abord, nous allons passer en revue un peu de théorie sur cet algorithme pour les arbres et les graphiques. Après cela, nous plongerons dans les implémentations des algorithmes en Java. Enfin, nous aborderons leur complexité temporelle.

2. Algorithme de recherche en largeur d'abord

L'approche de base de l'algorithme BFS (Breadth-First Search) consiste à rechercher un nœud dans une structure arborescente ou graphique en explorant les voisins avant les enfants.

Tout d'abord, nous verrons comment cet algorithme fonctionne pour les arbres. Après cela, nous l'adapterons aux graphes, qui ont la contrainte spécifique de contenir parfois des cycles. Enfin, nous discuterons des performances de cet algorithme.

2.1. Des arbres

L'idée derrière l'algorithme BFS pour les arbres est de maintenir une file d'attente de nœuds qui garantira l'ordre de traversée. Au début de l'algorithme, la file d'attente ne contient que le nœud racine. Nous allons répéter ces étapes tant que la file d'attente contient encore un ou plusieurs nœuds:

  • Pop le premier nœud de la file d'attente
  • Si ce nœud est celui que nous recherchons, la recherche est terminée
  • Sinon, ajoutez les enfants de ce nœud à la fin de la file d'attente et répétez les étapes

La fin de l'exécution est assurée par l'absence de cycles. Nous verrons comment gérer les cycles dans la section suivante.

2.2. Graphiques

Dans le cas des graphes, il faut penser à des cycles possibles dans la structure. Si nous appliquons simplement l'algorithme précédent sur un graphique avec un cycle, il bouclera pour toujours. Par conséquent, nous devrons conserver une collection des nœuds visités et nous assurer de ne pas les visiter deux fois :

  • Pop le premier nœud de la file d'attente
  • Vérifiez si le nœud a déjà été visité, si c'est le cas, ignorez-le
  • Si ce nœud est celui que nous recherchons, la recherche est terminée
  • Sinon, ajoutez-le aux nœuds visités
  • Ajoutez les enfants de ce nœud à la file d'attente et répétez ces étapes

3. Implémentation en Java

Maintenant que la théorie a été couverte, mettons la main sur le code et implémentons ces algorithmes en Java!

3.1. Des arbres

Tout d'abord, nous allons implémenter l'algorithme d'arborescence. Concevons notre classe Tree , qui se compose d'une valeur et d'enfants représentés par une liste d'autres Tree s:

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

Pour éviter de créer des cycles, les enfants sont créés par la classe elle-même, en fonction d'une valeur donnée.

Après cela, fournissons une méthode search () :

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

Comme nous l'avons mentionné précédemment, l'algorithme BFS utilise une file d'attente pour traverser les nœuds . Tout d'abord, nous ajoutons notre nœud racine à cette file d'attente:

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

Ensuite, nous devons boucler pendant que la file d'attente n'est pas vide, et chaque fois que nous sortons un nœud de la file d'attente:

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

Si ce nœud est celui que nous recherchons, nous le renvoyons, sinon nous ajoutons ses enfants à la file d'attente :

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

Enfin, si nous visitons tous les nœuds sans trouver celui que nous recherchons, nous retournons un résultat vide:

return Optional.empty();

Imaginons maintenant un exemple d'arborescence:

Ce qui se traduit par le code Java:

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

Ensuite, si vous recherchez la valeur 4, nous nous attendons à ce que l'algorithme traverse les nœuds avec les valeurs 10, 2 et 4, dans cet ordre:

BreadthFirstSearchAlgorithm.search(4, root)

Nous pouvons vérifier qu'avec la journalisation la valeur des nœuds visités:

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

Cela conclut le cas des arbres. Voyons maintenant comment gérer les graphiques. Contrairement aux arbres, les graphiques peuvent contenir des cycles. Cela signifie que, comme nous l'avons vu dans la section précédente, nous devons nous souvenir des nœuds que nous avons visités pour éviter une boucle infinie . Nous verrons dans un instant comment mettre à jour l'algorithme pour prendre en compte ce problème, mais d'abord, définissons notre structure graphique:

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.

Pourquoi n'avons-nous pas eu ce problème pour la recherche arborescente? Parce que le nombre de connexions dans une arborescence est limité par le nombre de nœuds. Le nombre de connexions dans un arbre de n nœuds est n - 1 .

4. Conclusion

Dans cet article, nous avons découvert l'algorithme Breadth-First Search et comment l'implémenter en Java.

Après avoir parcouru un peu de théorie, nous avons vu les implémentations Java de l'algorithme et discuté de sa complexité.

Comme d'habitude, le code est disponible sur sur GitHub.