Implementasi Depth First Search (DFS) dan Breadth First Search (BFS) pada Python

Depth First Search (DFS) adalah salah satu algoritma penelusuran struktur graf/pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya (misalnya prioritas penelusuran berdasrakan anak pertama [simpul sebelah kiri]), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam. Setelah sampai level terdalam, penulusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua ada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dst.

Cara Kerja Algoritma Depth First Search (DFS)

1. proses pencarian pada algoritma DFS akan dilakukan pada semua anaknya terlebih dahulu, sebelum dilakukan pencarian ke node-node yang selevel
2. Algoritma DFS melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya, sampai pada titik pertama
3. pencarian tersebut dimulai dari node akar ke level yang lebih tinggi. proses ini diulangi terus hingga ditemukannya solusi.

Contoh Implementasi Depth First Search (DFS)

Search Tree A to F

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam antrian.

Antrian:

1. A (Cek A : A bukan solusi maka simpan di Output)
2. B, C (Cek B : B bukan solusi maka simpan di Output)
3. D, C(Cek D : D bukan solusi maka simpan di Output)
4. F, C(Cek F : F merupakan solusi maka simpan di Output dan proses selesai)

Output : A> B> D> F

Berdasarkan langkah-langkah diatas, dapat disimpulkan dengan Depth First Search (DFS) didapat jalur yang paling optimal adalah jalur A> B> D> F

Berikut implementasi penyelesaian dalam bahasa pemrograman Python :

DFS Search A to F

Breadth First Search (BFS) adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.

Algoritma ini memerluka-n sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

Search Tree A to F

Atrian :

1. A (Cek A : A bukan solusi maka simpan di Output)
2. B,C. (Cek B : B bukan solusi maka simpan di Output)
3. C, D (Cek C : C bukan solusi maka simpan di Output)
4. E, D (Cek E : E bukan solusi maka simpan di Output)
5. D, F (Cek D : D bukan solusi maka simpan di Output)
6. F (Cek F : F merupakan solusi maka simpan di Output dan proses selesai)

Output :

A> B> C> E> D> F

Berdasarkan langkah-langkah diatas, dapat disimpulkan dengan Breadth First Search (BFS) didapat jalur yang paling optimal adalah jalur A> B> C> E> D> F.

Berikut implementasi penyelesaian dalam bahasa pemrograman Python :

BFS search A to F

Sekian penjelasan dari saya. Terimakasih atas kunjungannya, apabila ada kritik atau saran bisa email melalui email saya rinagustiana55@gmail.com

Pustaka

1. How to implement a depth-first Search in Python. https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python.

2. How to implement a breadth-first Search in Python. https://www.educative.io/edpresso/how-to-implement-a-breadth-first-search-in-python

3. Pengertian Metode Pencarian BFS dan DFS, beserta contohnya. http://michaeljulius11.blogspot.com/2017/10/pengertian-metode-pencarian-bfs-dan-dfs.html