Algoritma Depth First Search (BFS) dengan Source Code Python

Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya. Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.

Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).

Pada Postingan kali ini saya akan membagikan source code Algoritma DFS dengan menggunakan bahasa pemrograman Python, Berikut adalah source codenya :

#contoh peta 
Peta =  {'A':set(['B','H']),
         'B':set(['A','C','H']),
         'C':set(['B','D','E']),
         'D':set(['C','E','F','G','H']),

Algoritma Breadth First Search (BFS) dengan Source Code Python

Breadth First Search (BFS)

Breadth-first search 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 memerlukan 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.

Pada Postingan kali ini saya akan membagikan source code Algoritma BFS dengan menggunakan bahasa pemrograman Python, Berikut adalah source codenya :

#contoh Peta

Peta =  {'A':set(['B','H']),

         'B':set(['A','C','H']),

         'C':set(['B','D','E']),