Struktur Data - Breadth First Traversal

Algoritma Breadth First Search (BFS) melintasi grafik dalam gerakan luas dan menggunakan antrian untuk mengingat untuk mendapatkan simpul berikutnya untuk memulai pencarian, ketika jalan buntu terjadi dalam iterasi apa pun.

Seperti dalam contoh yang diberikan di atas, algoritma BFS melintasi dari A ke B ke E ke F terlebih dahulu kemudian ke C dan G terakhir ke D. Ini menggunakan aturan berikut.

• Rule 1- Kunjungi simpul yang belum dikunjungi yang berdekatan. Tandai sebagai telah dikunjungi. Tampilkan itu. Sisipkan dalam antrian.

• Rule 2 - Jika tidak ada simpul yang berdekatan ditemukan, hapus simpul pertama dari antrian.

• Rule 3 - Ulangi Aturan 1 dan Aturan 2 hingga antrian kosong.

Langkah	Traversal	Deskripsi
1		Inisialisasi antrian.
2		Kami mulai dari mengunjungi S (simpul awal), dan tandai sebagai telah dikunjungi.
3		Kami kemudian melihat simpul berdekatan yang belum dikunjungi dari S. Dalam contoh ini, kami memiliki tiga node tetapi menurut abjad kami memilihA, tandai sebagai telah dikunjungi dan mengantrekannya.
4		Selanjutnya, simpul berdekatan yang belum dikunjungi dari S adalah B. Kami menandainya sebagai telah dikunjungi dan mengantrekannya.
5		Selanjutnya, simpul berdekatan yang belum dikunjungi dari S adalah C. Kami menandainya sebagai telah dikunjungi dan mengantrekannya.
6		Sekarang, Sdibiarkan tanpa node berdekatan yang belum dikunjungi. Jadi, kami dequeue dan temukanA.
7		Dari A kita punya Dsebagai node berdekatan yang belum dikunjungi. Kami menandainya sebagai telah dikunjungi dan mengantrekannya.

Pada tahap ini, kita tidak memiliki node yang tidak ditandai (belum dikunjungi). Namun sesuai algoritme, kami terus melakukan dequeue untuk mendapatkan semua node yang belum dikunjungi. Saat antrian dikosongkan, program selesai.

Implementasi algoritma ini pada bahasa pemrograman C dapat dilihat disini .