Perbedaan yang menonjol antara BFS dan DFS adalah BFS atau Breadth First Search melanjutkan level demi level sementara DFS atau Depth First Search mengikuti jalur dari node awal hingga akhir dan kemudian berpindah ke jalur lain dari awal hingga akhir dan seterusnya, hingga mengunjungi semua node.
Grafik adalah struktur data nonlinier yang mengatur unsur data sebagai model jaringan. Node dalam graf disebut vertex, dan edge menghubungkan node-node tersebut. Dimungkinkan untuk menyelesaikan sebagian besar masalah grafik menggunakan metode pencarian. Breadth First Search (BFS) dan Depth First Search (DFS) adalah metode pencarian yang umum digunakan. Singkatnya, BFS menggunakan antrian sementara DFS menggunakan stack .
Topik bahasan kami tentang:
- Apa itu BFS – Definisi, Fungsi 2. Apa itu DFS – Definisi, Fungsi 3. Apa Perbedaan Antara BFS dan DFS – Perbandingan Perbedaan Utama
Istilah Utama
BFS, DFS
Yang perlu anda ketahui tentang BFS?
BFS adalah singkatan dari Breath First Search . Ini menggunakan antrian. Prosesnya adalah sebagai berikut.
- Kunjungi titik awal dan tempatkan unsur itu dalam antrian.
- Hapus sebuah simpul berulang kali dari antrian yang mengunjungi simpul-simpul berdekatan yang belum dikunjungi.
- Masukkan simpul yang baru dikunjungi ke antrian.
Contohnya adalah sebagai berikut.
Gambar 1: BFS
Asumsikan bahwa simpul awal pada gambar di atas adalah 1. Node yang terhubung ke 1 adalah 2 dan 4. Jadi kita dapat menempatkan 1, 2 dan 4 dalam antrian. Outputnya adalah 1, 2, 4. Untuk 1, tidak ada simpul yang tersisa. Maka dari itu, kita dapat menghapus 1 dari antrian. Sekarang kita dapat pindah ke 2. Titik-titik yang berdekatan dari 2 adalah 3, 5 dan 6. Dengan demikian, kita dapat menempatkan, 3, 5 dan 6 dalam antrian. Outputnya adalah 1, 2, 4, 3, 6. Selain ketiga bilangan tersebut, tidak ada simpul berdekatan yang terhubung ke 2. Jadi, kita dapat menghapus 2 dari antrian. Sekarang, mari kita pindah ke 4. Satu-satunya node yang berdekatan dengan 4 adalah 6. Telah dikunjungi. Tidak ada lagi simpul untuk 4. Maka dari itu, kita dapat menghapus 4 dari antrian. Anda harus mengulangi proses ini sampai antrian kosong. Ini menunjukkan penghentian operasi pencarian.
Yang perlu anda ketahui tentang DFS?
DFS adalah singkatan dari Depth First Search . Prosesnya adalah sebagai berikut.
Kunjungi simpul terdekat yang belum dikunjungi dan tandai sebagai telah dikunjungi. Kemudian, tampilkan dalam output dan dorong ke dalam tumpukan.
Jika tidak ada simpul bertetangga yang ditemukan, munculkan simpul dari tumpukan.
Lanjutkan dengan dua langkah di atas sampai tumpukan kosong.
Gambar 2: DFS
Titik awal adalah A. Itu didorong ke dalam tumpukan. Titik yang berdekatan adalah B dan E. Pertimbangkan B. Kita dapat mendorong B ke tumpukan. Karena tidak ada node yang berdekatan dengan B, kita dapat mengeluarkan B dari tumpukan. Outputnya adalah A B. Node berdekatan yang tersisa ke A adalah E, jadi, kita bisa memasukkan E ke stack. Sekarang outputnya adalah AB E.
Karena tidak ada node yang berdekatan dengan A, kita dapat mengeluarkan ‘A’ dari tumpukan. Node yang berdekatan untuk E adalah C dan H. Sekarang, pertimbangkan C. Kita dapat mendorong C ke stack. Outputnya adalah ABE C. Proses berlanjut sampai tumpukan kosong. Ini menghentikan operasi pencarian.
Perbedaan Antara BFS dan DFS
Definisi
algoritma traversal graf yang mulai menelusuri graf dari simpul akar dan menjelajahi semua simpul tetangga. DFS (Depth first search) adalah algoritma yang dimulai dengan node awal dari grafik dan kemudian semakin dalam sampai menemukan node yang dibutuhkan atau node yang tidak memiliki anak. Jadi, inilah Perbedaan yang menonjol antara BFS dan DFS.
Bentuk panjang
Sementara BFS adalah singkatan dari Breadth First Search, DFS adalah singkatan dari Depth First Search.
Metode Menyimpan Node
Perbedaan utama lainnya antara BFS dan DFS adalah BFS menggunakan antrian sementara DFS menggunakan tumpukan.
Konsumsi Memori
Selain itu, BFS mengkonsumsi lebih banyak memori daripada DFS.
Metode Melintasi
Metode tranversing adalah perbedaan lain antara BFS dan DFS. BFS berfokus pada mengunjungi simpul tertua yang belum dikunjungi terlebih dahulu sementara DFS berfokus pada mengunjungi simpul di sepanjang tepi di awal.
Kata terakhir
BFS dan DFS adalah dua metode pencarian untuk menemukan unsur dalam grafik. Perbedaan yang menonjol antara BFS dan DFS adalah BFS melanjutkan level demi level sementara DFS mengikuti jalur dari node awal hingga akhir dan kemudian berpindah ke jalur lain dari awal hingga akhir dan seterusnya hingga mengunjungi semua node.
Sumber bacaan:
- Algoritma Pencarian Pertama yang Luas | Kode Semu | Pendahuluan, Pendidikan 4u, 22 Maret 2018, Tersedia di sini . 2. Pencarian Pertama Luas | Contoh BFS |, Pendidikan 4u, 22 Maret 2018, Tersedia di sini . 3. Algoritma Pencarian Kedalaman Pertama | Graph Traversal Algorithm |, Education 4u, 22 Mar. 2018, Tersedia di sini . 4. “Algoritma BFS – Javatpoint.” www.javatpoint.com, Tersedia di sini . 5. “Algoritma DFS – Javatpoint.” www.javatpoint.com, Tersedia di sini .
