Algoritma Breadth-First Search di Java

Pengaturcaraan

1. Gambaran keseluruhan

Dalam tutorial ini, kita akan belajar mengenai algoritma Breadth-First Search, yang membolehkan kita mencari simpul di pokok atau grafik dengan melalui simpul mereka lebar pertama dan bukan kedalaman pertama.

Pertama, kita akan mengkaji sedikit teori mengenai algoritma ini untuk pokok dan grafik. Selepas itu, kami akan menyelami implementasi algoritma di Java. Akhirnya, kita akan merangkumi kerumitan masa mereka.

2. Algoritma Carian Breadth-First

Pendekatan asas algoritma Breadth-First Search (BFS) adalah mencari simpul ke struktur pokok atau grafik dengan meneroka jiran sebelum anak-anak.

Pertama, kita akan melihat bagaimana algoritma ini berfungsi untuk pokok. Selepas itu, kami akan menyesuaikannya dengan grafik, yang mempunyai kekangan khusus kadangkala mengandungi kitaran. Akhirnya, kita akan membincangkan prestasi algoritma ini.

2.1. Pokok

Idea di sebalik algoritma BFS untuk pokok adalah mengekalkan barisan nod yang akan memastikan urutan melintang. Pada permulaan algoritma, barisan hanya mengandungi simpul akar. Kami akan mengulangi langkah-langkah ini selagi barisan masih mengandungi satu atau lebih nod:

  • Munculkan nod pertama dari barisan
  • Sekiranya simpul itu adalah yang kita cari, maka carian sudah berakhir
  • Jika tidak, tambahkan anak simpul ini ke hujung barisan dan ulangi langkahnya

Penamatan pelaksanaan dijamin oleh ketiadaan kitaran. Kami akan melihat bagaimana menguruskan kitaran di bahagian seterusnya.

2.2. Grafik

Dalam kes grafik, kita mesti memikirkan kemungkinan kitaran dalam struktur. Sekiranya kita hanya menggunakan algoritma sebelumnya pada grafik dengan satu kitaran, ia akan berubah selamanya. Oleh itu, kami perlu menyimpan koleksi nod yang dikunjungi dan memastikan kami tidak mengunjunginya dua kali :

  • Munculkan nod pertama dari barisan
  • Periksa sama ada simpul sudah dilawati, jika tidak, langkau
  • Sekiranya simpul itu adalah yang kita cari, maka carian sudah berakhir
  • Jika tidak, tambahkannya ke nod yang dikunjungi
  • Tambahkan anak-anak simpul ini ke barisan dan ulangi langkah-langkah ini

3. Pelaksanaan di Jawa

Sekarang bahawa teori telah dibahas, mari kita memahami kod dan menerapkan algoritma ini di Java!

3.1. Pokok

Pertama, kami akan melaksanakan algoritma pokok. Mari merancang kelas Pokok kami , yang terdiri daripada nilai dan anak-anak yang diwakili oleh senarai Pokok lain :

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

Untuk mengelakkan membuat kitaran, kanak-kanak dibuat oleh kelas itu sendiri, berdasarkan nilai yang diberikan.

Selepas itu, mari berikan kaedah carian () :

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

Seperti yang telah kami sebutkan sebelumnya, algoritma BFS menggunakan antrian untuk melintasi nod . Pertama sekali, kami menambahkan simpul akar kami ke barisan ini:

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

Kemudian, kita mesti berpusing sementara barisan tidak kosong, dan setiap kali kita keluar nod dari barisan:

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

Sekiranya nod itu adalah yang kami cari, kami mengembalikannya, jika tidak, kami menambahkan anak-anaknya ke dalam barisan :

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

Akhirnya, jika kita melawat semua node tanpa mencari yang kita cari, kita akan memberikan hasil kosong:

return Optional.empty();

Sekarang mari kita bayangkan struktur pokok contoh:

Yang diterjemahkan ke dalam kod Java:

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

Kemudian, jika mencari nilai 4, kami menjangkakan algoritma akan melintasi nod dengan nilai 10, 2 dan 4, mengikut urutan:

BreadthFirstSearchAlgorithm.search(4, root)

Kami dapat mengesahkan bahawa dengan mencatat nilai nod yang dikunjungi:

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

Itu menyimpulkan kes pokok. Sekarang mari kita lihat bagaimana menangani grafik. Sebaliknya pada pokok, grafik boleh mengandungi kitaran. Ini bermaksud, seperti yang telah kita lihat di bahagian sebelumnya, kita harus ingat simpul yang kita kunjungi untuk mengelakkan gelung yang tidak terhingga . Kami akan melihat sebentar bagaimana mengemas kini algoritma untuk mempertimbangkan masalah ini, tetapi pertama, mari kita tentukan struktur grafik kami:

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.

Mengapa kita tidak menghadapi masalah ini untuk mencari pokok? Kerana bilangan sambungan dalam pokok dibatasi oleh bilangan nod. Bilangan sambungan di pohon n nod adalah n - 1 .

4. Kesimpulan

Dalam artikel ini, kami belajar mengenai algoritma Breadth-First Search dan bagaimana menerapkannya di Java.

Setelah melalui sedikit teori, kami melihat pelaksanaan algoritma Java dan membincangkan kerumitannya.

Seperti biasa, kodnya tersedia di GitHub.