Breitensuchalgorithmus in Java

1. Übersicht

In diesem Tutorial lernen wir den Algorithmus für die Breitensuche kennen, mit dem wir nach einem Knoten in einem Baum oder einer Grafik suchen können, indem wir die Knoten mit der Breite zuerst und nicht mit der Tiefe zuerst durchlaufen.

Zunächst werden wir ein wenig Theorie über diesen Algorithmus für Bäume und Grafiken durchgehen. Danach werden wir uns mit den Implementierungen der Algorithmen in Java befassen. Schließlich werden wir ihre zeitliche Komplexität behandeln.

2. Breitensuchalgorithmus

Der grundlegende Ansatz des BFS-Algorithmus (Breadth-First Search) besteht darin, nach einem Knoten in einer Baum- oder Diagrammstruktur zu suchen, indem Nachbarn vor Kindern untersucht werden.

Zuerst werden wir sehen, wie dieser Algorithmus für Bäume funktioniert. Danach passen wir es an Diagramme an, die die spezifische Einschränkung haben, manchmal Zyklen zu enthalten. Abschließend werden wir die Leistung dieses Algorithmus diskutieren.

2.1. Bäume

Die Idee hinter dem BFS-Algorithmus für Bäume besteht darin , eine Warteschlange von Knoten zu verwalten, die die Reihenfolge des Durchlaufs sicherstellt. Zu Beginn des Algorithmus enthält die Warteschlange nur den Stammknoten. Wir werden diese Schritte wiederholen, solange die Warteschlange noch einen oder mehrere Knoten enthält:

  • Pop den ersten Knoten aus der Warteschlange
  • Wenn dieser Knoten derjenige ist, nach dem wir suchen, ist die Suche beendet
  • Fügen Sie andernfalls die untergeordneten Elemente dieses Knotens am Ende der Warteschlange hinzu und wiederholen Sie die Schritte

Die Beendigung der Ausführung wird durch das Fehlen von Zyklen sichergestellt. Wir werden im nächsten Abschnitt sehen, wie man Zyklen verwaltet.

2.2. Grafiken

Bei Graphen müssen wir an mögliche Zyklen in der Struktur denken. Wenn wir den vorherigen Algorithmus einfach auf ein Diagramm mit einem Zyklus anwenden, wird er für immer wiederholt. Daher müssen wir eine Sammlung der besuchten Knoten aufbewahren und sicherstellen, dass wir sie nicht zweimal besuchen :

  • Pop den ersten Knoten aus der Warteschlange
  • Überprüfen Sie, ob der Knoten bereits besucht wurde. Wenn ja, überspringen Sie ihn
  • Wenn dieser Knoten derjenige ist, nach dem wir suchen, ist die Suche beendet
  • Andernfalls fügen Sie es den besuchten Knoten hinzu
  • Fügen Sie die untergeordneten Elemente dieses Knotens zur Warteschlange hinzu und wiederholen Sie diese Schritte

3. Implementierung in Java

Nachdem die Theorie behandelt wurde, wollen wir uns mit dem Code befassen und diese Algorithmen in Java implementieren!

3.1. Bäume

Zuerst implementieren wir den Baumalgorithmus. Entwerfen wir unsere Tree- Klasse, die aus einem Wert und untergeordneten Elementen besteht, die durch eine Liste anderer Tree- Klassen dargestellt werden :

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

Um das Erstellen von Zyklen zu vermeiden, werden untergeordnete Elemente von der Klasse selbst basierend auf einem bestimmten Wert erstellt.

Lassen Sie uns danach eine search () -Methode bereitstellen :

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

Wie bereits erwähnt, verwendet der BFS-Algorithmus eine Warteschlange, um die Knoten zu durchlaufen . Zunächst einmal haben wir unsere hinzufügen Wurzelknoten in diese Warteschlange:

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

Dann müssen wir eine Schleife ausführen, während die Warteschlange nicht leer ist, und jedes Mal, wenn wir einen Knoten aus der Warteschlange entfernen:

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

Wenn dieser Knoten derjenige ist, nach dem wir suchen, geben wir ihn zurück, andernfalls fügen wir seine untergeordneten Elemente zur Warteschlange hinzu :

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

Wenn wir schließlich alle Knoten besucht haben, ohne den gesuchten zu finden, geben wir ein leeres Ergebnis zurück:

return Optional.empty();

Stellen wir uns nun eine beispielhafte Baumstruktur vor:

Was sich in den Java-Code übersetzt:

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

Wenn wir dann nach dem Wert 4 suchen, erwarten wir, dass der Algorithmus Knoten mit den Werten 10, 2 und 4 in dieser Reihenfolge durchläuft:

BreadthFirstSearchAlgorithm.search(4, root)

Wir können dies überprüfen, indem wir den Wert der besuchten Knoten protokollieren:

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

Damit ist der Fall der Bäume abgeschlossen. Lassen Sie uns nun sehen, wie Sie mit Grafiken umgehen. Im Gegensatz zu Bäumen können Diagramme Zyklen enthalten. Das heißt, wie wir im vorherigen Abschnitt gesehen haben, müssen wir uns an die Knoten erinnern, die wir besucht haben, um eine Endlosschleife zu vermeiden . Wir werden gleich sehen, wie der Algorithmus aktualisiert wird, um dieses Problem zu berücksichtigen, aber zuerst definieren wir unsere Diagrammstruktur:

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.

Warum hatten wir dieses Problem bei der Baumsuche nicht? Weil die Anzahl der Verbindungen in einem Baum durch die Anzahl der Knoten begrenzt ist. Die Anzahl der Verbindungen in einem Baum von n Knoten beträgt n - 1 .

4. Fazit

In diesem Artikel haben wir etwas über den Breadth-First Search-Algorithmus und dessen Implementierung in Java gelernt.

Nachdem wir ein bisschen Theorie durchgearbeitet hatten, sahen wir Java-Implementierungen des Algorithmus und diskutierten seine Komplexität.

Wie üblich ist der Code auf GitHub verfügbar.