Metode Pencarian Melebar (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 BFS:
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
4. Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
Metode Pencarian Mendalam (DFS)
Metode strictly depth-first srategy berarti pengguna mengamati tiap link hasil dari mesin pencari mulai
dari atas, dan memutuskan segera untuk membuka dokumen atau tidak.
Algoritma DFS:
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka Stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3.Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2.
4.Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
Metode Binary Search Tree (BST)
• Sebuah binary tree dimana subtree sebelah kiri lebih kecil dari subtree sebelah kanan.
• Operasi BST : penambahan, penghapusan, pencarian node tertentu, pencarian niai terkecil dan pencarian nilai terbesar.
• Properti Binary Search Tree :
• Untuk setiap node X, semua elemen di subpohon kirinya bernilai lebih kecil dari nilai X dan semua elemen di subpohon kanannya bernilai lebih besar dari nilai X.
Algoritma BST
-Menambah elemen X pada binary search tree:
◦mulai dari root.
◦Jika X lebih kecil dari root, maka X harus diletakkan pada sub-tree sebelah kiri.
◦jika X lebih besar dari root, then X harus diletakkan pada sub-tree sebelah kanan.
-Ingat bahwa: sebuah sub tree adalah juga sebuah tree. Maka, proses penambahan elemen pada sub tree adalah sama dengan penambahan pada seluruh tree. (melalui root tadi)
◦Apa hubungannya?
◦permasalahan ini cocok diselesaikan secara rekursif.
Contoh program:
program Binary_Search;
uses win;
const
x = 10;
Var
arr : array [1..x] of integer;
i, kiri,tengah,kanan,cari :integer;
ketemu :boolean;
Begin
clrscr;
writeln('List Angka : ');
for i := 1 to x do
begin
arr[i] := i;
write(arr[i],' ');
end;
writeln;
write('Masukan data yang dicari (dgn Binary Serach) : ');
readln(cari);
kiri:=x;
kanan:=1;
ketemu:=false;
while not(ketemu) do
begin
tengah:=(kiri + kanan) div 2;
If arr[tengah]=cari then
begin
ketemu:=true;
writeln('Kunci yang di cari berada pada index ke ',tengah);
end
else if (cari < arr[tengah]) then
kiri := tengah - 1
else
kanan:= tengah+1;
if (kanan > kiri) then
begin
ketemu:=true;
writeln('Data yang Anda cari tidak ada !');
end;
end;
readln;
end.
