Artikel ini menunjukkan prosedur untuk mengimplementasikan DFS untuk pohon atau grafik yang disediakan.
Bagaimana Menerapkan Pencarian Kedalaman Pertama atau DFS untuk Grafik di Jawa?
DFS terutama digunakan untuk mencari graf dengan mengunjungi setiap cabang/simpul tepat satu kali. Itu dapat mendeteksi atau mengidentifikasi siklus dalam grafik yang membantu mencegah kebuntuan. Ini dapat digunakan untuk menyelesaikan teka-teki atau masalah labirin. DFS dapat diimplementasikan/dimanfaatkan dalam algoritma grafik, perayapan web, dan desain kompiler.
Untuk penjelasan, kunjungi kode Depth First Search atau DFS di bawah ini:
kelas Grafik {
pribadi LinkedList addNode [ ] ;
pribadi boolean Dilintasi [ ] ;
Grafik ( int sudut ) {
addNode = baru LinkedList [ sudut ] ;
Dilintasi = baru boolean [ sudut ] ;
untuk ( int Saya = 0 ; Saya < sudut ; Saya ++ )
addNode [ Saya ] = baru LinkedList ( ) ;
}
ruang kosong addEdge ( int src, int awal ) {
addNode [ src ] . menambahkan ( awal ) ;
}
Deskripsi kode di atas:
- Pertama, kelas bernama “ Grafik ' dibuat. Di dalamnya, menyatakan ' LinkedList ' bernama ' tambahNode[] ” dan array tipe boolean bernama “ Dilintasi[] ”.
- Selanjutnya, berikan simpul untuk konstruktor dari “ Grafik ” kelas sebagai parameter.
- Setelah itu, “ untuk ” loop dibuat untuk bergerak melalui setiap node dari cabang yang dipilih.
- Pada akhirnya, tipe void “ addEdge() ” digunakan untuk menambahkan sisi di antara simpul. Fungsi ini membutuhkan dua parameter: sumber dari simpul “ src ” dan simpul tujuan “ awal ”.
Setelah membuat grafik, sekarang mari kita tambahkan kode pencarian kedalaman-pertama atau DFS untuk grafik yang dibuat di atas:
ruang kosong DFS ( int puncak ) {
Dilintasi [ puncak ] = BENAR ;
Sistem . keluar . mencetak ( puncak + ' ' ) ;
Iterator ini = addNode [ puncak ] . listIterator ( ) ;
ketika ( ini. hasNext ( ) ) {
int adj = ini. Berikutnya ( ) ;
jika ( ! Dilintasi [ adj ] )
DFS ( adj ) ;
}
}
Di blok kode di atas:
- Pertama, “ DFS() ” fungsi dibuat yang mendapatkan “ puncak ” sebagai parameter. Simpul itu ditandai sebagai dikunjungi.
- Selanjutnya, cetak simpul yang dikunjungi menggunakan ' keluar.print() ' metode.
- Kemudian, buat instance dari ' Iterator ” yang beriterasi pada simpul yang berdekatan dari simpul saat ini.
- Jika simpul tersebut tidak dikunjungi, maka simpul tersebut diteruskan ke “ DFS() ' fungsi.
Sekarang, mari kita buat ' utama() ” berfungsi bagian untuk membuat grafik dan kemudian menerapkan DFS untuk itu:
publik statis ruang kosong utama ( Rangkaian argumen [ ] ) {
Grafik k = baru Grafik ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Sistem . keluar . println ( 'Mengikuti adalah Depth First Traversal' ) ;
k. DFS ( 1 ) ;
}
}
Penjelasan dari kode di atas:
- Pertama, buat objek “ k ' Untuk ' Grafik() ' metode.
- Selanjutnya, “ addEdge() ” metode digunakan untuk menambahkan tepi antara beberapa simpul. Ini menciptakan struktur grafik kita.
- Pada akhirnya, berikan nilai simpul apa pun sebagai argumen ke “ DFS() ' fungsi. Untuk menemukan jalur simpul dari akar, gunakan algoritma pencarian kedalaman-pertama. Misalnya nilai “ 1 ” diteruskan ke “ DFS() ' fungsi.
Setelah akhir fase kompilasi:
Outputnya menunjukkan pencarian depth-first telah berhasil diterapkan.
Kesimpulan
Depth First Search adalah algoritma penjelajahan graf yang menjadi dasar bagi banyak algoritme graf seperti menemukan jalur terpendek, pohon rentang, dan analisis konektivitas. Ini dimulai dari root node dan kemudian bergerak sedalam mungkin sampai leave node atau node terakhir dari cabang tersebut sebelum melakukan backtracking. Artikel ini telah mendemonstrasikan prosedur penerapan depth-first search atau DFS untuk graf di Java.