Artikel ini menunjukkan prosedur untuk melaksanakan DFS untuk pokok atau graf yang disediakan.
Bagaimana untuk Melaksanakan Carian Pertama Kedalaman atau DFS untuk Graf di Java?
DFS digunakan terutamanya untuk mencari graf dengan melawati setiap cawangan/puncak tepat sekali. Ia boleh mengesan atau mengenal pasti kitaran dalam graf yang membantu dalam mencegah kebuntuan. Ia boleh digunakan untuk menyelesaikan teka-teki atau masalah maze. DFS boleh dilaksanakan/digunakan dalam algoritma graf, rangkak web dan reka bentuk pengkompil.
Untuk penjelasan, lawati kod Depth First Search atau DFS di bawah:
kelas Graf {
persendirian LinkedList addNode [ ] ;
persendirian boolean Dilalui [ ] ;
Graf ( int bucu ) {
addNode = baru LinkedList [ bucu ] ;
Dilalui = baru boolean [ bucu ] ;
untuk ( int i = 0 ; i < bucu ; i ++ )
addNode [ i ] = baru LinkedList ( ) ;
}
batal addEdge ( int src, int mulakan ) {
addNode [ src ] . Tambah ( mulakan ) ;
}
Penerangan kod di atas:
- Pertama, kelas bernama ' Graf ” dicipta. Di dalamnya, mengisytiharkan ' LinkedList ” bernama “ addNode[] ” dan tatasusunan jenis boolean bernama “ Dilalui[] ”.
- Seterusnya, luluskan bucu untuk pembina ' Graf ” kelas sebagai parameter.
- Selepas itu, ' untuk gelung ” dicipta untuk bergerak melalui setiap nod cawangan yang dipilih.
- Pada akhirnya, jenis kekosongan ' addEdge() ” digunakan untuk menambah tepi antara bucu. Fungsi ini mengambil dua parameter: sumber bucu ' src 'dan puncak destinasi' mulakan ”.
Selepas penciptaan graf, sekarang mari kita tambah kod carian pertama mendalam atau DFS untuk graf yang dibuat di atas:
batal DFS ( int puncak ) {
Dilalui [ puncak ] = benar ;
Sistem . keluar . cetak ( puncak + ' ' ) ;
Iterator ini = addNode [ puncak ] . listIterator ( ) ;
sementara ( ini. mempunyaiSeterusnya ( ) ) {
int adj = ini. seterusnya ( ) ;
jika ( ! Dilalui [ adj ] )
DFS ( adj ) ;
}
}
Dalam blok kod di atas:
- Pertama, ' DFS() fungsi ' dicipta yang mendapat ' puncak ” sebagai parameter. Puncak itu ditandakan sebagai dilawati.
- Seterusnya, cetak puncak yang dilawati menggunakan ' out.print() ” kaedah.
- Kemudian, buat contoh ' Iterator ” yang berulang di atas bucu bersebelahan bucu semasa.
- Jika bucu tidak dilawati, maka ia melepasi bucu tersebut ke “ DFS() ” fungsi.
Sekarang, mari kita buat ' utama() ” bahagian fungsi untuk mencipta graf dan kemudian menggunakan DFS untuk itu:
awam statik batal utama ( Tali args [ ] ) {
Graf k = baru Graf ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Sistem . keluar . println ( 'Berikut ialah Depth First Traversal' ) ;
k. DFS ( 1 ) ;
}
}
Penjelasan kod di atas:
- Pertama, buat objek ' k 'untuk' Graf() ” kaedah.
- Seterusnya, ' addEdge() ” kaedah digunakan untuk menambah tepi antara berbilang bucu. Ini mencipta struktur graf kami.
- Pada akhirnya, hantarkan sebarang nilai bucu sebagai hujah kepada “ yang telah dibuat DFS() ” fungsi. Untuk mencari laluan bucu dari punca, gunakan algoritma carian mendalam-pertama. Sebagai contoh, nilai ' 1 ” diserahkan kepada “ DFS() ” fungsi.
Selepas tamat fasa penyusunan:
Output menunjukkan carian depth-first telah berjaya dilaksanakan.
Kesimpulan
Depth First Search ialah algoritma lintasan graf yang menjadi asas bagi banyak algoritma graf seperti mencari laluan terpendek, pepohon merentang dan analisis ketersambungan. Ia bermula dari nod akar dan kemudian bergerak sedalam mungkin sehingga nod tinggalkan atau nod terakhir cawangan itu sebelum menjejak ke belakang. Artikel ini telah menunjukkan prosedur untuk melaksanakan carian depth-first atau DFS untuk graf dalam Java.