Широко-първи алгоритъм за търсене в Java

Програмиране

1. Общ преглед

В този урок ще научим за алгоритъма за първо търсене на ширина, който ни позволява да търсим възел в дърво или графика, като пътуваме през техните възли първо на ширина, а не на дълбочина.

Първо, ще преминем през малко теория за този алгоритъм за дървета и графики. След това ще се потопим в реализациите на алгоритмите в Java. Накрая ще разгледаме тяхната сложност във времето.

2. Алгоритъм за първо търсене на широчина

Основният подход на алгоритъма за първоначално търсене (BFS) е да се търси възел в дървовидна или графична структура чрез изследване на съседи преди деца.

Първо ще видим как работи този алгоритъм за дървета. След това ще го адаптираме към графики, които имат специфичното ограничение за понякога съдържащи цикли. Накрая ще обсъдим работата на този алгоритъм.

2.1. Дървета

Идеята зад алгоритъма на BFS за дървета е да се поддържа опашка от възли, които да осигурят реда на обхождане. В началото на алгоритъма опашката съдържа само коренния възел. Ще повторим тези стъпки, докато опашката все още съдържа един или повече възли:

  • Изкачете първия възел от опашката
  • Ако този възел е този, който търсим, тогава търсенето е приключило
  • В противен случай добавете децата на този възел в края на опашката и повторете стъпките

Прекратяването на изпълнението се осигурява от липсата на цикли. Ще видим как да управляваме цикли в следващия раздел.

2.2. Графики

В случай на графики, трябва да мислим за възможни цикли в структурата. Ако просто приложим предишния алгоритъм върху графика с цикъл, той ще се върти завинаги. Затова ще трябва да съхраняваме колекция от посетените възли и да гарантираме, че няма да ги посещаваме два пъти :

  • Изкачете първия възел от опашката
  • Проверете дали възелът вече е посетен, ако е така, пропуснете го
  • Ако този възел е този, който търсим, тогава търсенето е приключило
  • В противен случай го добавете към посетените възли
  • Добавете децата на този възел към опашката и повторете тези стъпки

3. Внедряване в Java

Сега, след като теорията беше разгледана, нека влезем в кода и да приложим тези алгоритми в Java!

3.1. Дървета

Първо ще приложим дървесния алгоритъм. Нека да проектираме нашия клас Tree , който се състои от стойност и деца, представени от списък на други 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; } }

За да се избегне създаването на цикли, децата се създават от самия клас въз основа на дадена стойност.

След това нека предоставим метод за търсене () :

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

Както споменахме по-рано, алгоритъмът BFS използва опашка за пресичане на възлите . На първо място, ние добавяме нашия корен възел към тази опашка:

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

След това трябва да циклираме, докато опашката не е празна и всеки път, когато извадим възел от опашката:

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

Ако този възел е този, който търсим, ние го връщаме, в противен случай добавяме неговите деца в опашката :

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.

Защо нямахме този проблем при търсенето на дърво? Тъй като броят на връзките в едно дърво е ограничен от броя на възлите. Броят на връзките в дърво от n възли е n - 1 .

4. Заключение

В тази статия научихме за алгоритъма за първоначално търсене на ширина и как да го приложим в Java.

След като преминахме през малко теория, видяхме Java реализации на алгоритъма и обсъдихме неговата сложност.

Както обикновено, кодът е достъпен в GitHub.