Algoritma pencarian graf merupakan teknik penting dalam ilmu komputer yang digunakan untuk menemukan jalur atau simpul tertentu dalam struktur graf. Dua algoritma pencarian graf yang umum digunakan adalah Breadth First Search (BFS) dan Depth First Search (DFS). Dalam artikel ini, kita akan mengeksplorasi konsep, contoh soal, perbedaan, dan aplikasi dari BFS dan DFS.

BFS dan DFS memiliki pendekatan yang berbeda dalam menelusuri graf. BFS mengutamakan pencarian pada level yang sama sebelum melanjutkan ke level berikutnya, sedangkan DFS mengutamakan pencarian sedalam mungkin pada satu jalur sebelum kembali ke jalur lain.

Pengertian Breadth First Search (BFS)

Breadth First Search (BFS) adalah algoritma pencarian grafik yang mengeksplorasi semua simpul pada tingkat yang sama sebelum melanjutkan ke tingkat berikutnya. Ini mengikuti pendekatan level-by-level, mengunjungi semua simpul pada tingkat saat ini sebelum pindah ke tingkat berikutnya.

Dalam BFS, kita memulai dari simpul awal dan menambahkan semua simpul yang berdekatan dengan simpul awal ke antrian. Kemudian, kita mengeluarkan simpul dari antrian dan menambahkan semua simpul yang berdekatan dengannya yang belum dikunjungi. Proses ini diulangi sampai antrian kosong atau kita mencapai simpul tujuan.

Ilustrasi Cara Kerja BFS

Berikut adalah ilustrasi cara kerja BFS pada grafik:

• Mulai dari simpul awal (A).
• Tambahkan semua simpul yang berdekatan dengan A (B, C) ke antrian.
• Keluarkan simpul B dari antrian.
• Tambahkan semua simpul yang berdekatan dengan B (D, E) ke antrian.
• Keluarkan simpul C dari antrian.
• Tambahkan simpul yang berdekatan dengan C (F) ke antrian.
• Teruskan proses ini sampai antrian kosong atau kita mencapai simpul tujuan.

Contoh Soal BFS

Breadth-First Search (BFS) adalah algoritma pencarian grafik yang mengunjungi simpul pada setiap level sebelum beralih ke level berikutnya. Berikut adalah contoh soal BFS:

Diberikan sebuah graf dengan simpul A, B, C, D, E, dan F, dan tepinya sebagai berikut:

• A → B
• A → C
• B → D
• B → E
• C → F

Urutan kunjungan simpul BFS dimulai dari simpul A adalah:

1. A
2. B
3. C
4. D
5. E
6. F

Pengertian Depth First Search (DFS)

DFS (Depth First Search) adalah algoritma pencarian yang mengeksplorasi grafik atau pohon secara mendalam. Algoritma ini memulai dari node awal dan mengeksplorasi semua jalur yang memungkinkan dari node tersebut sebelum beralih ke node lain.

Konsep DFS

Konsep DFS adalah mengeksplorasi satu jalur hingga mencapai ujungnya sebelum beralih ke jalur lain. Algoritma ini menggunakan stack untuk menyimpan jalur yang sedang dieksplorasi. Ketika node baru ditemukan, node tersebut ditambahkan ke stack dan dieksplorasi. Jika tidak ada jalur lain yang dapat dieksplorasi dari node tersebut, maka node tersebut dikeluarkan dari stack dan eksplorasi beralih ke node sebelumnya dalam stack.

Cara Kerja DFS

Berikut ilustrasi cara kerja DFS pada grafik:

• Algoritma dimulai dari node awal (misalnya A).
• Node A dieksplorasi dan node yang terhubung dengannya (B, C) ditambahkan ke stack.
• Node B dieksplorasi, tetapi tidak memiliki node yang terhubung.
• Node B dikeluarkan dari stack dan node C dieksplorasi.
• Node C memiliki node terhubung (D), yang ditambahkan ke stack.
• Node D dieksplorasi, tetapi tidak memiliki node yang terhubung.
• Node D dikeluarkan dari stack dan node C dikeluarkan dari stack.
• Node A dikeluarkan dari stack, yang menandakan bahwa semua jalur telah dieksplorasi.

Proses ini terus berulang hingga semua node dalam grafik telah dieksplorasi.

Contoh Soal DFS

Depth-First Search (DFS) adalah algoritma pencarian graf yang menjelajahi graf secara mendalam, mengunjungi simpul-simpul yang berdekatan sebelum melanjutkan ke simpul yang belum dikunjungi.

Salah satu contoh soal DFS adalah mencari jalur terpendek dari simpul awal ke simpul tujuan dalam sebuah graf berarah berbobot.

Langkah-langkah Penyelesaian

Langkah	Penjelasan
1	Tandai simpul awal sebagai dikunjungi dan masukkan ke dalam tumpukan.
2	Sementara tumpukan tidak kosong, lakukan langkah-langkah berikut:
	– Keluarkan simpul teratas dari tumpukan.
	– Kunjungi simpul tersebut.
	– Untuk setiap simpul yang berdekatan dengan simpul yang dikunjungi, lakukan langkah-langkah berikut:
	— Jika simpul belum dikunjungi, tandai sebagai dikunjungi dan masukkan ke dalam tumpukan.

Perbedaan BFS dan DFS

Breadth-First Search (BFS) dan Depth-First Search (DFS) adalah dua algoritma pencarian grafik yang memiliki karakteristik dan aplikasi yang berbeda.

Berikut adalah perbedaan utama antara BFS dan DFS:

Struktur Pencarian

• BFS: Menjelajahi simpul secara mendatar, mengunjungi semua simpul pada level yang sama sebelum melanjutkan ke level berikutnya.
• DFS: Menjelajahi simpul secara vertikal, mengunjungi simpul sedalam mungkin sebelum kembali dan menjelajahi cabang lainnya.

Antrian dan Tumpukan

• BFS: Menggunakan antrian untuk menyimpan simpul yang akan dikunjungi, memastikan simpul dikunjungi sesuai urutan kedatangan.
• DFS: Menggunakan tumpukan untuk menyimpan simpul yang akan dikunjungi, memungkinkan eksplorasi mendalam dari setiap cabang.

Urutan Kunjungan

• BFS: Mengunjungi simpul dalam urutan level, dimulai dari level paling dangkal.
• DFS: Mengunjungi simpul dalam urutan kedalaman, mengeksplorasi satu cabang secara mendalam sebelum beralih ke cabang lainnya.

Aplikasi

• BFS: Cocok untuk pencarian jarak terpendek, pencarian jalur, dan deteksi siklus.
• DFS: Cocok untuk traversal pohon, pencarian komponen terhubung, dan pencarian pola.

Aplikasi BFS dan DFS

BFS dan DFS adalah algoritma pencarian graf yang memiliki berbagai aplikasi dalam dunia nyata. Kedua algoritma ini digunakan untuk menyelesaikan berbagai masalah yang melibatkan pencarian dan traversal graf.

Aplikasi BFS

• Pencarian jalur terpendek dalam graf
• Deteksi siklus dalam graf
• Pewarnaan graf
• Pemeriksaan keterhubungan graf

Aplikasi DFS

• Pencarian mendalam dalam graf
• Penemuan komponen terhubung dalam graf
• Deteksi jembatan dalam graf
• Pencarian topologi

Ringkasan Terakhir

BFS dan DFS merupakan algoritma pencarian graf yang sangat berguna dengan aplikasi yang luas dalam berbagai bidang. Pemahaman tentang konsep dan perbedaan keduanya sangat penting bagi pengembang perangkat lunak dan ilmuwan komputer. Algoritma ini menyediakan alat yang efektif untuk memecahkan berbagai masalah pencarian graf, sehingga memudahkan eksplorasi dan manipulasi struktur data yang kompleks.

Jawaban untuk Pertanyaan Umum

Apa kelebihan BFS dibandingkan DFS?

BFS lebih efisien untuk mencari simpul yang dekat dengan simpul awal.

Apa aplikasi BFS dalam dunia nyata?

BFS digunakan dalam pencarian jalur terpendek, deteksi siklus, dan traversal level demi level.

Bagaimana DFS berbeda dari BFS?

DFS mengutamakan kedalaman daripada keluasan, sedangkan BFS mengutamakan keluasan daripada kedalaman.

Apa kekurangan DFS?

DFS dapat menjadi tidak efisien untuk graf yang besar dan dalam karena dapat terjebak dalam jalur yang panjang.