Tugas 4 : Search mlm menggunakn 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 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.

Cara Kerja Algoritma BFS
       Dalam 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.
       Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

1. Masukkan simpul ujung (akar) ke dalam antrian
2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi
3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian
5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
6. Ulangi pencarian dari langkah kedua

Pseudocode

1 Prosedur Breadth First Search (G, v):
2 membuat antrian Q
3 masukkan antrian v ke Q
4 mark v
5 sedangkan Q tidak kosong:
6 t ← Q.keluarkan antrian ( )
7 jika t adalah apa yang kita cari:
8 kembali t
9 untuk semua tepi e di G.tepi yang berdekatan (t), maka lakukan
12 u ← G.puncak yang berdekatan (t, e)
13 jika u tidak ditandai:
14 maka tandai u
15 masukkan antrian u ke Q

 misalnya dari pohon mlm berikut :

mencari rendi dengan nomer 34