Pengertian Breadth First Search
merupakan pencarian yang dilakukan dengan mengunjungi tiap tiap node secara
sistematis pada setiap level hingga keadaan tujuan ditemukan. Penelususran yang
dilakukan dengan mengunjungi node node pada level yang sama hingga ditemukan
tujuan (goal state) nya.
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 simpul-simpul yang tadi
dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media
representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam
persoalan-persoalan teori graf.
Pengimplementasian Breath First Search dapat ditelusuri dengan menggunakan
daftar list open dan closed, untuk menelusuri gerakan pencarian di dalam ruang
keadaan. Pada algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam
suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan
bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.
Pengertian Depth-First Search
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).
MATA KULIAH : pengantar teknologi sistem cerdas#
