Apa arti 'luasnya' dalam pencarian pertama yang luas?

Saya belajar tentang pencarian pertama yang luas dan sebuah pertanyaan muncul di benak saya mengapa BFS disebut demikian. Dalam buku Pengantar Algoritma oleh CLRS , saya membaca alasan berikut ini:

Pencarian Breadth-first dinamai demikian karena memperluas perbatasan antara simpul-simpul yang ditemukan dan yang belum ditemukan secara seragam melintasi luasnya perbatasan.

Namun, saya tidak dapat memahami arti dari pernyataan ini. Saya bingung tentang kata "perbatasan" dan luasnya perbatasan itu.

Jadi, bisakah seseorang tolong jawab pertanyaan ini dengan cara yang mudah dimengerti untuk pemula seperti saya?

Pertimbangkan struktur data yang digunakan untuk mewakili pencarian. Di BFS, Anda menggunakan antrian. Jika Anda menemukan simpul yang tidak terlihat, Anda menambahkannya ke antrian.

"Perbatasan" adalah himpunan semua node dalam struktur data pencarian. Antrian akan beriterasi melalui semua node di perbatasan secara berurutan, dengan demikian iterasi melintasi luas perbatasan. DFS akan selalu memunculkan status terakhir yang ditemukan dari tumpukan, sehingga selalu beralih ke bagian terdalam perbatasan.

Perhatikan gambar di bawah ini. Perhatikan bagaimana DFS langsung menuju ke bagian terdalam dari pohon sedangkan BFS berulang pada luasnya setiap tingkat.

Gambar di sini

Kutipan yang Anda berikan mengatakan "perbatasan antara simpul yang ditemukan dan yang belum ditemukan". Jadi itulah perbatasan yang penulis bicarakan: perbatasan antara simpul yang ditemukan dan yang belum ditemukan. Anda memiliki beberapa simpul yang belum Anda lihat sama sekali. Anda juga memiliki beberapa simpul yang untuknya Anda telah melihat segalanya. Dan kemudian Anda memiliki simpul di antaranya. Ini adalah simpul yang telah Anda lihat, tetapi Anda belum memuat semua anak mereka. Ini perbatasan.

Membahas ini lebih lanjut tentang:

Untuk melacak kemajuan warna BFS setiap titik putih, abu-abu, atau hitam. Semua simpul mulai putih dan kemudian menjadi abu-abu dan kemudian hitam. Vertex ditemukan saat pertama kali ditemukan selama pencarian, di mana saat itu menjadi non-putih. Oleh karena itu, simpul abu-abu dan hitam telah ditemukan, tetapi BFS membedakannya untuk memastikan bahwa pencarian berlangsung dengan cara BF.
...
setiap titik awalnya berwarna putih, berwarna abu-abu ketika ditemukan dalam pencarian, dan dihitamkan ketika selesai, yaitu, ketika daftar kedekatannya telah diperiksa sepenuhnya.

Jadi semua simpul mulai putih (belum ditemukan). Ketika sebuah simpul ditemukan, warnanya abu-abu (perbatasan). Ketika semua yang ditunjukkannya telah ditemukan, warnanya hitam (sepenuhnya ditemukan). Perbatasan adalah himpunan poin yang telah ditemukan, tetapi memiliki anak-anak yang belum ditemukan.

Misalkan Anda mencari sesuatu di situs web. Anda pertama kali pergi ke halaman utama. Misalkan itu berlabel "binatang". Batas saat ini adalah {"binatang"}. Anda melihat melalui halaman utama dan tidak melihat apa yang Anda cari. Tetapi Anda perhatikan bahwa ia memiliki tautan ke dua halaman lagi, "berkaki empat" dan "cacing". Jadi, Anda mengeklik tautan ke "berkaki empat". Sekarang batasnya adalah {"binatang", "berkaki empat"}. Anda melihat melalui "berkaki empat" dan tidak menemukan apa yang Anda cari. Apa yang kamu lakukan selanjutnya? Anda dapat mencari tautan pada "binatang berkaki empat" dan mengikuti itu, atau kembali ke "binatang" dan mengklik tautan ke "cacing". Yang pertama adalah pencarian mendalam-pertama, dan yang kedua adalah pencarian luas pertama.

"depth" mengacu pada berapa banyak tautan dari simpul akar yang diperlukan untuk sampai ke suatu simpul, sementara "keluasan" mengacu pada simpul-simpul sebagai kedalaman yang sama. Pada contoh di atas, BFS dimulai dari "animals" dan pertama-tama melihat semua node satu, jadi ia melihat "quadrupeds" dan "worm" terlebih dahulu. Setelah melihat semua kedalaman-1 node, itu memperluas perbatasan di semua node; yaitu, ia melihat anak-anak dari semua node kedalaman-1 sebelum melihat salah satu dari anak-anak node kedalaman-2. Jadi, misalnya, jika salah satu tautan pada halaman "berkaki empat" adalah "primata", ia akan melihat semua tautan pada halaman "cacing" sebelum ia melihat salah satu tautan pada halaman "primata".

Misalkan algoritma BFS dijalankan mulai dari vertex . Bayangkan gelombang yang dikirim keluar dari (seperti air gelombang atau tsunami). Setelah satu langkah waktu, gelombang akan mencapai semua tetangga . Setelah dua langkah waktu, gelombang akan mencapai (atau "dikunjungi") semua simpul yang paling jauh dari . Dan seterusnya. $a$$a$$a$$2$$a$

Pada waktu tertentu, batas gelombang adalah tepat simpul yang disimpan dalam struktur data antrian (simpul-simpul ini telah dikunjungi tetapi belum dieksplorasi lebih lanjut).

Dengan demikian, gelombang awalnya mencapai seluruh "luasnya" dari semua simpul yang berjarak 1 dari . Setelah beberapa langkah waktu, gelombang akan menutupi seluruh lebar hingga jarak tertentu dari titik awal . $a$$a$

Himpunan simpul pada jarak dari disebut lapisan di partisi jarak grafik sehubungan dengan simpul . Set vertex adalah penyatuan terputus-putus dari lapisan-lapisan ini . Lapisan adalah , lapisan pertama adalah himpunan tetangga dari , lapisan kedua adalah himpunan simpul yang jaraknya ke adalah dua, dan seterusnya. Algoritma BFS mengunjungi simpul grafik dalam urutan tertentu - lapis demi lapis. Setiap lapisan menutupi seluruh luasnya, tetapi lapisan yang berbeda berada pada kedalaman yang berbeda.$k$$a$$k$$a$$(k \ge 0)$$0$$\{a\}$$a$$a$

Di sisi lain, algoritma DFS akan mengeksplorasi sedalam mungkin dalam satu arah (yaitu mengunjungi 's tetangga pertama, kemudian tetangganya, kemudian tetangganya, dan sebagainya) sebelum kembali kembali ke dan mengunjungi tetangga yang belum dijelajahi berikutnya . Algoritma ini masuk lebih dulu, daripada mengunjungi tetangga secara luas. $a$$a$$a$

Dengan demikian, DFS dan BFS berbeda dalam urutan di mana mereka mengunjungi simpul.