Algoritma Pencarian Luas-Pertama di Java

1. Ikhtisar

Dalam tutorial ini, kita akan belajar tentang algoritma Breadth-First Search, yang memungkinkan kita untuk mencari node di pohon atau grafik dengan melakukan perjalanan melalui node-nya lebih dulu daripada depth-first.

Pertama, kita akan membahas sedikit teori tentang algoritma ini untuk pohon dan grafik. Setelah itu, kita akan mendalami implementasi algoritma di Java. Terakhir, kami akan membahas kompleksitas waktu mereka.

2. Algoritma Pencarian Luas-Pertama

Pendekatan dasar algoritme Breadth-First Search (BFS) adalah mencari node ke dalam struktur pohon atau grafik dengan menjelajahi tetangga sebelum turunan.

Pertama, kita akan melihat bagaimana algoritma ini bekerja untuk pohon. Setelah itu, kami akan menyesuaikannya dengan grafik, yang memiliki batasan khusus terkadang berisi siklus. Terakhir, kita akan membahas performa algoritma ini.

2.1. Pohon

Ide di balik algoritma BFS untuk pohon adalah untuk menjaga antrian node yang akan memastikan urutan traversal. Di awal algoritme, antrean hanya berisi node root. Kami akan mengulangi langkah-langkah ini selama antrian masih berisi satu atau lebih node:

  • Munculkan node pertama dari antrean
  • Jika node itu adalah yang kita cari, maka pencarian selesai
  • Jika tidak, tambahkan anak node ini ke akhir antrian dan ulangi langkah-langkahnya

Penghentian eksekusi dipastikan dengan tidak adanya siklus. Kita akan melihat bagaimana mengelola siklus di bagian selanjutnya.

2.2. Grafik

Dalam kasus grafik, kita harus memikirkan kemungkinan siklus dalam struktur. Jika kita hanya menerapkan algoritma sebelumnya pada grafik dengan siklus, itu akan berulang selamanya. Oleh karena itu, kita perlu menyimpan kumpulan node yang dikunjungi dan memastikan kita tidak mengunjunginya dua kali :

  • Munculkan node pertama dari antrean
  • Periksa apakah node telah dikunjungi, jika demikian lewati saja
  • Jika node itu adalah yang kita cari, maka pencarian selesai
  • Jika tidak, tambahkan ke node yang dikunjungi
  • Tambahkan anak node ini ke antrean dan ulangi langkah-langkah ini

3. Implementasi di Jawa

Sekarang teori telah dibahas, mari kita tangani kode dan menerapkan algoritma ini di Java!

3.1. Pohon

Pertama, kami akan menerapkan algoritma pohon. Mari kita desain kelas Tree kita , yang terdiri dari nilai dan anak-anak yang diwakili oleh daftar Tree lainnya :

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 menghindari pembuatan siklus, anak dibuat oleh kelas itu sendiri, berdasarkan nilai yang diberikan.

Setelah itu, mari berikan metode search () :

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

Seperti yang kami sebutkan sebelumnya, algoritma BFS menggunakan antrian untuk melintasi node . Pertama-tama, kami menambahkan node root kami ke antrian ini:

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

Kemudian, kita harus melakukan perulangan saat antrian tidak kosong, dan setiap kali kita mengeluarkan simpul dari antrian:

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

Jika simpul itu adalah yang kita cari, kita kembalikan, kalau tidak kita tambahkan anaknya ke antrian :

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

Akhirnya, jika kami mengunjungi semua node tanpa menemukan yang kami cari, kami mengembalikan hasil kosong:

return Optional.empty();

Sekarang mari kita bayangkan contoh struktur pohon:

Yang diterjemahkan ke dalam kode 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 mengharapkan algoritme untuk melintasi node dengan nilai 10, 2 dan 4, dengan urutan sebagai berikut:

BreadthFirstSearchAlgorithm.search(4, root)

Kami dapat memverifikasi bahwa dengan mencatat nilai node 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 kasus pohon. Sekarang mari kita lihat bagaimana menangani grafik. Berlawanan dengan pohon, grafik dapat berisi siklus. Artinya, seperti yang kita lihat di bagian sebelumnya, kita harus mengingat node yang kita kunjungi untuk menghindari loop tanpa batas . Kita akan segera melihat bagaimana memperbarui algoritma untuk mempertimbangkan masalah ini, tapi pertama-tama, mari kita tentukan struktur grafik kita:

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 memiliki masalah ini untuk pencarian pohon? Karena jumlah koneksi dalam sebuah pohon dibatasi oleh jumlah node. Jumlah koneksi dalam pohon dengan n node adalah n - 1 .

4. Kesimpulan

Di artikel ini, kita belajar tentang algoritma Breadth-First Search dan bagaimana menerapkannya di Java.

Setelah melalui sedikit teori, kami melihat implementasi algoritma Java dan membahas kompleksitasnya.

Seperti biasa, kode tersedia di GitHub.