Kedalaman Pencarian Pertama di Jawa

1. Ikhtisar

Dalam tutorial ini, kita akan menjelajahi pencarian Depth-first di Java.

Depth-first search (DFS) adalah algoritma traversal yang digunakan untuk struktur data Pohon dan Grafik. Pencarian kedalaman-pertama dilakukan jauh di setiap cabang sebelum pindah untuk menjelajahi cabang lain .

Di bagian selanjutnya, pertama-tama kita akan melihat implementasi untuk Pohon dan kemudian Grafik.

Untuk melihat bagaimana mengimplementasikan struktur ini di Java, lihat tutorial kami sebelumnya tentang Binary Tree dan Grafik.

2. Tree Depth-first Search

Ada tiga urutan berbeda untuk melintasi pohon menggunakan DFS:

  1. Preorder Traversal
  2. Inorder Traversal
  3. Penjelajahan Pasca Pesanan

2.1. Preorder Traversal

Dalam preorder traversal, kita melintasi akar terlebih dahulu, kemudian subpohon kiri dan kanan.

Kita cukup mengimplementasikan preorder traversal menggunakan rekursi :

  • Kunjungi node saat ini
  • Lintasi subpohon kiri
  • Lintasi subpohon kanan
public void traversePreOrder(Node node) { if (node != null) { visit(node.value); traversePreOrder(node.left); traversePreOrder(node.right); } }

Kami juga dapat mengimplementasikan preorder traversal tanpa rekursi.

Untuk mengimplementasikan preorder traversal berulang, kita memerlukan Stack , dan kita akan melalui langkah-langkah berikut:

  • Dorong root di taktik kami
  • Sedangkan stack tidak kosong
    • Pop node saat ini
    • Kunjungi node saat ini
    • Dorong anak kanan , lalu anak kiri untuk menumpuk
public void traversePreOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(!stack.isEmpty()) { current = stack.pop(); visit(current.value); if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } }

2.2. Inorder Traversal

Untuk inorder traversal, kita melintasi subpohon kiri terlebih dahulu, lalu akar, kemudian subpohon kanan .

Inorder traversal untuk pohon pencarian biner berarti melintasi node dalam meningkatkan urutan nilainya.

Kita cukup mengimplementasikan inorder traversal menggunakan rekursi:

public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); visit(node.value); traverseInOrder(node.right); } }

Kami juga dapat mengimplementasikan inorder traversal tanpa rekursi juga:

  • Mendorong akar node s taktik
  • Sementara paku tidak kosong
    • Terus dorong anak kiri ke tumpukan, sampai kita mencapai anak paling kiri node saat ini
    • Kunjungi node saat ini
    • Dorong anak kanan ke atas tumpukan
public void traverseInOrderWithoutRecursion() { Stack stack = new Stack(); Node current = root; stack.push(root); while(! stack.isEmpty()) { while(current.left != null) { current = current.left; stack.push(current); } current = stack.pop(); visit(current.value); if(current.right != null) { current = current.right; stack.push(current); } } }

2.3. Penjelajahan Pasca Pesanan

Akhirnya, dalam traversal postorder, kita melintasi subtree kiri dan kanan sebelum melintasi root .

Kami dapat mengikuti solusi rekursif kami sebelumnya :

public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); visit(node.value); } }

Atau, kita juga dapat mengimplementasikan traversal postorder tanpa rekursi :

  • Mendorong akar simpul di s taktik
  • Sementara paku tidak kosong
    • Periksa apakah kita sudah melintasi subpohon kiri dan kanan
    • Jika tidak, maka dorong anak kanan dan anak kiri ke atas tumpukan
public void traversePostOrderWithoutRecursion() { Stack stack = new Stack(); Node prev = root; Node current = root; stack.push(root); while (!stack.isEmpty()) { current = stack.peek(); boolean hasChild = (current.left != null || current.right != null); boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null)); if (!hasChild || isPrevLastChild) { current = stack.pop(); visit(current.value); prev = current; } else { if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } } }

3. Grafik Pencarian Kedalaman-pertama

Perbedaan utama antara grafik dan pohon adalah grafik dapat berisi siklus .

Jadi untuk menghindari pencarian dalam siklus, kami akan menandai setiap node saat kami mengunjunginya.

Kita akan melihat dua implementasi untuk grafik DFS, dengan rekursi, dan tanpa rekursi.

3.1. Grafik DFS dengan Rekursi

Pertama, mari kita mulai dengan rekursi:

  • Kami akan mulai dari node tertentu
  • Tandai node saat ini sebagai telah dikunjungi
  • Kunjungi node saat ini
  • Lintasi simpul berdekatan yang belum dikunjungi
public void dfs(int start) { boolean[] isVisited = new boolean[adjVertices.size()]; dfsRecursive(start, isVisited); } private void dfsRecursive(int current, boolean[] isVisited) { isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) dfsRecursive(dest, isVisited); } }

3.2. Grafik DFS Tanpa Rekursi

Kami juga dapat mengimplementasikan DFS grafik tanpa rekursi. Kami hanya akan menggunakan Stack :

  • Kami akan mulai dari node tertentu
  • Dorong node awal ke dalam tumpukan
  • Sedangkan Stack tidak kosong
    • Tandai node saat ini sebagai telah dikunjungi
    • Kunjungi node saat ini
    • Dorong simpul berdekatan yang belum dikunjungi
public void dfsWithoutRecursion(int start) { Stack stack = new Stack(); boolean[] isVisited = new boolean[adjVertices.size()]; stack.push(start); while (!stack.isEmpty()) { int current = stack.pop(); isVisited[current] = true; visit(current); for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) stack.push(dest); } } }

3.4. Urutan Topologis

Ada banyak aplikasi untuk pencarian pertama kedalaman grafik. Salah satu aplikasi terkenal untuk DFS adalah Topological Sort.

Topological Sort untuk graf berarah adalah pengurutan linear dari simpul-simpulnya sehingga untuk setiap sisi simpul sumber muncul sebelum tujuan.

Untuk mengurutkan secara topologis, kita memerlukan tambahan sederhana ke DFS yang baru saja kita terapkan:

  • Kita perlu menyimpan simpul yang dikunjungi dalam tumpukan karena jenis topologi adalah simpul yang dikunjungi dalam urutan terbalik
  • Kami mendorong node yang dikunjungi ke tumpukan hanya setelah melintasi semua tetangganya
public List topologicalSort(int start) { LinkedList result = new LinkedList(); boolean[] isVisited = new boolean[adjVertices.size()]; topologicalSortRecursive(start, isVisited, result); return result; } private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList result) { isVisited[current] = true; for (int dest : adjVertices.get(current)) { if (!isVisited[dest]) topologicalSortRecursive(dest, isVisited, result); } result.addFirst(current); }

4. Kesimpulan

Dalam artikel ini, kita membahas pencarian pertama kedalaman untuk struktur data Pohon dan Grafik.

Kode sumber lengkap tersedia di GitHub.