BFS dan DFS adalah metode melintasi yang digunakan dalam mencari grafik. Grafik traversal adalah proses mengunjungi semua node grafik. Grafik adalah sekelompok Vertikal 'V' dan Tepi 'E' yang menghubungkan ke simpul.
Grafik perbandingan
| Dasar untuk perbandingan | BFS | DFS |
|---|---|---|
| Dasar | Algoritma berbasis vertex | Algoritma berbasis tepi |
| Struktur data digunakan untuk menyimpan node | Antre | Tumpukan |
| Konsumsi memori | Tidak efisien | Efisien |
| Struktur pohon yang dibangun | Lebar dan pendek | Sempit dan panjang |
| Melintasi mode | Verteks yang belum dikunjungi tertua dieksplorasi pada awalnya. | Verteks di sepanjang tepi dieksplorasi di awal. |
| Optimalitas | Optimal untuk menemukan jarak terdekat, bukan biaya. | Tidak maksimal |
| Aplikasi | Memeriksa grafik bipartit, komponen yang terhubung, dan jalur terpendek yang ada dalam grafik. | Memeriksa grafik terhubung dua sisi, grafik terhubung kuat, grafik asiklik dan urutan topologi. |
Definisi BFS
Breadth First Search (BFS) adalah metode traversing yang digunakan dalam grafik. Ini menggunakan antrian untuk menyimpan simpul yang dikunjungi. Dalam metode ini yang ditekankan adalah pada simpul grafik, satu simpul dipilih pada awalnya kemudian dikunjungi dan ditandai. Verteks yang berdekatan dengan verteks yang dikunjungi kemudian dikunjungi dan disimpan dalam antrian berurutan. Demikian pula, simpul yang disimpan kemudian diperlakukan satu per satu, dan simpul yang berdekatan dikunjungi. Sebuah node sepenuhnya dieksplorasi sebelum mengunjungi node lain dalam grafik, dengan kata lain, node tersebut melintasi node yang belum dieksplorasi paling dangkal terlebih dahulu.
Contoh
Kami memiliki grafik yang simpulnya adalah A, B, C, D, E, F, G. Mempertimbangkan A sebagai titik awal. Langkah-langkah yang terlibat dalam proses ini adalah:
- Vertex A diperluas dan disimpan dalam antrian.
- Verteks B, D dan G penerus A, diperluas dan disimpan dalam antrian sementara Vertex A dihapus.
- Sekarang B di ujung depan antrian dihapus bersama dengan menyimpan simpul penggantinya E dan F.
- Vertex D di ujung depan antrian dihapus, dan simpul yang terhubung F sudah dikunjungi.
- Vertex G dihapus dari antrian, dan memiliki penerus E yang sudah dikunjungi.
- Sekarang E dan F dihapus dari antrian, dan simpul penggantinya C dilalui dan disimpan dalam antrian.
- Akhirnya C juga dihapus dan antrian kosong yang berarti kita selesai.
- Output yang dihasilkan adalah - A, B, D, G, E, F, C.
BFS dapat berguna dalam menemukan apakah grafik memiliki komponen yang terhubung atau tidak. Dan itu juga dapat digunakan dalam mendeteksi grafik bipartit .
Grafik adalah bipartit ketika simpul grafik dibagi menjadi dua set yang terpisah; tidak ada dua simpul yang berdekatan yang berada di set yang sama. Metode lain untuk memeriksa grafik bipartit adalah untuk memeriksa terjadinya siklus aneh dalam grafik. Grafik bipartit tidak boleh mengandung siklus ganjil.
BFS juga lebih baik dalam menemukan jalur terpendek dalam grafik yang dapat dilihat sebagai jaringan.
Definisi DFS
Metode traverse Depth First Search (DFS) menggunakan stack untuk menyimpan simpul yang dikunjungi. DFS adalah metode berbasis tepi dan bekerja secara rekursif di mana simpul dieksplorasi di sepanjang jalur (tepi). Eksplorasi sebuah node ditangguhkan segera setelah simpul lain yang belum dijelajahi ditemukan dan simpul-simpul yang belum dijelajahi yang terdalam ditelusuri pada titik terdepan. DFS melintasi / mengunjungi setiap simpul tepat sekali dan setiap tepi diperiksa tepat dua kali.
Contoh
Mirip dengan BFS, mari kita ambil grafik yang sama untuk melakukan operasi DFS, dan langkah-langkah yang terlibat adalah:
- Mempertimbangkan A sebagai titik awal yang dieksplorasi dan disimpan dalam tumpukan.
- B simpul penerus A disimpan dalam tumpukan.
- Vertex B memiliki dua penerus E dan F, di antaranya secara alfabetis E dieksplorasi terlebih dahulu dan disimpan dalam tumpukan.
- Penerus dari vertex E, yaitu, G disimpan dalam tumpukan.
- Vertex G memiliki dua simpul yang terhubung, dan keduanya sudah dikunjungi, sehingga G dikeluarkan dari tumpukan.
- Demikian pula, E juga dihapus.
- Sekarang, titik B berada di bagian atas tumpukan, simpulnya yang lain (titik) F dieksplorasi dan disimpan dalam tumpukan.
- Vertex F memiliki dua penerus C dan D, di antara mereka C dilalui terlebih dahulu dan disimpan dalam tumpukan.
- Vertex C hanya memiliki satu pendahulu yang sudah dikunjungi, sehingga dihapus dari tumpukan.
- Sekarang simpul D yang terhubung ke F dikunjungi dan disimpan dalam tumpukan.
- Karena simpul D tidak memiliki simpul yang belum dikunjungi, maka D dihapus.
- Demikian pula, F, B dan A juga muncul.
- Output yang dihasilkan adalah - A, B, E, G, F, C, D.
Aplikasi DFS mencakup pemeriksaan dua graf yang terhubung ke tepi, graf yang terhubung kuat, grafik asiklik, dan urutan topologi .
Grafik disebut dua sisi yang terhubung jika dan hanya jika tetap terhubung meskipun salah satu ujungnya dihilangkan. Aplikasi ini sangat berguna, di jaringan komputer di mana kegagalan satu tautan di jaringan tidak akan mempengaruhi jaringan yang tersisa, dan itu akan tetap terhubung.
Grafik yang terhubung dengan kuat adalah grafik yang harus ada jalur antara sepasang simpul yang dipesan. DFS digunakan dalam grafik berarah untuk mencari jalur antara setiap pasangan simpul yang dipesan. DFS dapat dengan mudah menyelesaikan masalah konektivitas.
Perbedaan Utama Antara BFS dan DFS
- BFS adalah algoritma berbasis vertex sedangkan DFS adalah algoritma berbasis tepi.
- Struktur data antrian digunakan dalam BFS. Di sisi lain, DFS menggunakan stack atau rekursi.
- Ruang memori digunakan secara efisien dalam DFS sedangkan pemanfaatan ruang di BFS tidak efektif.
- BFS adalah algoritma optimal sedangkan DFS tidak optimal.
- DFS membangun pohon yang sempit dan panjang. Sebaliknya, BFS membangun pohon lebar dan pendek.
Kesimpulan
BFS dan DFS, kedua teknik pencarian grafik memiliki waktu berjalan yang sama tetapi konsumsi ruang yang berbeda, DFS mengambil ruang linier karena kita harus mengingat jalur tunggal dengan node yang belum dijelajahi, sementara BFS menyimpan setiap node dalam memori.
DFS menghasilkan solusi yang lebih dalam dan tidak optimal, tetapi bekerja dengan baik ketika solusinya padat sedangkan BFS optimal yang mencari tujuan optimal pada awalnya.
