Breadth-first Search
Pengertian Breadth First Search
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 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.
0 komentar:
Posting Komentar