Implementasi Algoritma Breadth First Search

 

ㅤSebuah web crawler (juga dikenal sebagai robot atau spider) adalah sistem untuk melakukan download sebagian besar halaman web. Web crawler digunakan untuk berbagai tujuan. Tujuan yang paling sering digunakan adalah menjadikan web crawler sebagai salah satu komponen utama dari web search engine (mesin pencari web). Selain sebagai komponen utama dari web search engine, web crawler juga bisa digunakan pada aplikasi web pengarsipan, dimana halaman web dengan skala yang besar secara berkala dikumpulkan dan diarsipkan. 

ㅤAlgoritma Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah sebuah teknik umum yang digunakan untuk melakukan traversal pada graf. Secara ringkas, algoritma ini memiliki prosedur: traversal dimulai dari simpul, kunjungi semua simpul, kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu, kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul – simpul yang tadi dikunjungi, demikian seterusnya. 

ㅤPencarian dalam algoritma BFS dilakukan secara sistematis, artinya biasanya dikunjungi dalam satu arah, misalnya dari simpul paling kiri ke simpul paling kanan. Penelusuran simpul juga dilakukan dalam satu arah terlebih dahulu sebelum mengunjungi simpul pada arah yang lebih tinggi. Dalam implementasinya, algoritma BFS memerlukan matriks ketetanggaan A = [aij] yang berukuran n × n , antrean q untuk menyimpan simpul yang telah dikunjungi, dan tabel boolean dikunjungi. Pseudo-code dari algoritma BFS adalah sebagai berikut: 

prosedur BFS (input v:integer) 

ㅤDeklarasi 

ㅤㅤw : integer 

ㅤㅤq : antrean 

ㅤㅤprosedur BuatAntrean(input/output q : antrean) 

ㅤㅤprosedur MasukAntrean(input/output q:antrean, input v:integer) 

ㅤㅤprosedur HapusAntrean(input/output q:antrean, output v:integer) 

ㅤㅤfunction AntreanKosong(input q:antrean) -> boolean 

ㅤ

ㅤAlgoritma 

ㅤㅤBuatAntrean(q) 

ㅤㅤwrite(v) 

ㅤㅤdikunjungi[v] <- true 

ㅤ

ㅤㅤMasukAntrean(q, v) 

ㅤㅤwhile not AntreanKosong(q) do 

ㅤㅤㅤHapusAntrean(q, v) 

ㅤㅤㅤfor tiap simpul w yang bertetangga dengan simpul v do 

ㅤㅤㅤㅤif not dikunjungi[w] then 

ㅤㅤㅤㅤㅤwrite(w) 

ㅤㅤㅤㅤㅤMasukAntrean(q,w) 

ㅤㅤㅤㅤㅤdikunjungi[w] <- true 

ㅤㅤㅤㅤendif 

ㅤㅤㅤendfor 

ㅤㅤendwhile 

ㅤ

ㅤ

ㅤ

ㅤ

Referensi:

- Shita, Rizky Tahara. Subandi. 2017. IMPLEMENTASI ALGORITMA BFS (BREADTH-FIRST SEARCH) PADA APLIKASI WEB CRAWLER. Jurnal TELEMATIKA MKOM Vol.8 No.2 September 2016. hal. 127-132. 

ㅤ

ㅤ

Ditulis oleh Clifansi Remi Siwi Hati - 21312004 - Informatika '21 A, Universitas Teknokrat Indonesia