BREADTH FIRAST SEARCH

Breadth-first search

Dalam teori grafik ,-pertama pencarian luas (BFS) adalah algoritma pencarian grafik yang dimulai pada root node dan mengeksplorasi semua node tetangga. Lalu untuk masing-masing node terdekat, itu belum dijelajahi mereka mengeksplorasi node tetangga, dan seterusnya, sampai menemukan tujuan.

Breadth-first search

Urutan node diperluas Kelas Algoritma pencarian Data structure Grafik performance Kasus terburuk kinerja kasus terburuk ruang kompleksitas O ( | V | + | E | ) = O ( b ^d ) O (| V | + | E |) = O (b ^d)

Bagaimana cara kerjanya

BFS adalah sebuah pencarian uninformed metode yang bert

ujuan untuk memperluas dan memeriksa semua node dari sebuah grafik atau kombinasi urutan dengan sistematis mencari melalui setiap solusi. Dengan kata lain, secara mendalam akan mencari seluruh grafik atau urutan tanpa mempertimbangkan tujuan sampai menemukannya. Ia tidak menggunakan heuristik algoritma.

Dari sudut pandang algoritma , anak semua

node diperoleh dengan memperluas simpul ditambahkan ke FIFO antrian . Dalam implementasi khas, node yang belum diperiksa untuk tetangga mereka ditempatkan dalam beberapa wadah (seperti antrian atau daftar link ) yang disebut "terbuka" dan kemudian setelah diperiksa ditempatkan dalam wadah "tertutup".

Peta contoh Jerman dengan beberapa hubungan antara kota

Pohon yang pertama kali luas diperoleh saat menjalankan BFS pada peta yang diberikan dan mulai di Frankfurt

Contoh animasi pencarian luas-pertama

Algoritma (informal)

1. Enqueue node root.
2. Dequeue node dan memeriksanya.
• Jika elemen yang dicari ditemukan di node ini, berhenti mencari dan mengembalikan hasilnya.
• Jika tidak ada penerus enqueue (kelenjar anak langsung) yang belum ditemukan.
3. Jika antrian kosong, setiap node pada grafik telah diselidiki - berhenti pencarian dan kembali "tidak ditemukan".
4. Ulangi dari Langkah 2.

. Catatan: Menggunakan tumpukan bukan antrian itu akan mengubah algoritma ini menjadi pertama pencarian mendalam .

Fitur

Kompleksitas Space

Karena semua node satu tingkat harus disimpan sampai anak mereka simpul pada tingkat berikutnya telah dihasilkan, kompleksitas ruang sebanding dengan jumlah node pada tingkat terdalam. Dengan adanya faktor percabangan b dan kedalaman grafik d ruang kompleksitas asimtotik adalah jumlah node pada tingkat terdalam, O (b ^d). Ketika jumlah vertex dan tepi dalam grafik dikenal sebelumnya, kompleksitas ruang juga dapat dinyatakan sebagai O (| E | + | V |) dimana | E | adalah kardinalitas dari himpunan sisi (jumlah tepi), dan | V | adalah kardinalitas dari himpunan vertex. In the worst case the Dalam kasus terburuk grafik memiliki kedalaman 1 dan semua titik harus disimpan. Karena eksponensial di kedalaman grafik, cari luas-yang pertama sering tidak praktis untuk masalah-masalah besar pada sistem dengan ruang terbatas.

Kompleksitas Waktu

Sejak dalam pencarian kasus terburuk luas-pertama harus mempertimbangkan semua jalur ke semua node memungkinkan kompleksitas waktu pencarian luasnya-pertama yaitu O (b ^d). Kompleksitas juga waktu dapat dinyatakan sebagai O (| E | + | V |) karena setiap node dan setiap tepi akan dibahas dalam kasus terburuk.

Kelengkapan

pencarian Breadth-pertama selesai. Ini berarti bahwa jika ada solusi, cari luas-pertama akan menemukannya tanpa jenis grafik. Namun, jika grafik yang terbatas dan tidak ada solusi pencarian luas-pertama akan berbeda.

Bukti kelengkapan

Jika node tujuan dangkal adalah beberapa kedalaman hingga mengatakan d,-pertama pencarian luas akhirnya akan menemukannya setelah memperluas semua node dangkal (asalkan b faktor percabangan ada batasnya).

optimalitas

Dalam pencarian luas-umum pertama tidak optimal karena selalu kembali hasil dengan ujung paling sedikit antara node awal dan node tujuan. Jika grafik adalah grafik tertimbang, dan karenanya memiliki biaya yang terkait dengan setiap langkah, sebuah tujuan berikutnya untuk memulai tidak harus menjadi tujuan termurah yang tersedia. masalah ini diselesaikan dengan meningkatkan-luasnya untuk mencari pertama -biaya pencari yang seragam yang mempertimbangkan biaya jalan. Namun demikian, jika grafik tidak berbobot, dan karena itu semua biaya tahap adalah sama, cari luas-pertama akan menemukan terdekat dan solusi yang terbaik.

Aplikasi

Breadth-pertama dapat digunakan untuk memecahkan berbagai masalah dalam teori graph, misalnya:

• Menemukan semua node yang terhubung dalam satu komponen
• Menyalin Koleksi, Algoritma Cheney
• Menemukan jalur terpendek antara dua simpul u dan v (dalam grafik tertimbang )
• Pengujian grafik untuk bipartiteness
• (Reverse) Cuthill-McKee mesh penomoran
• Ford-Fulkerson metode untuk menghitung arus maksimum dalam jaringan aliran
• Serialisasi / Deserialization dari serialisasi vs pohon biner untuk disortir, memungkinkan pohon yang akan dibangun kembali dengan cara yang efisien.

Mencari komponen terhubung

Himpunan node dicapai melalui BFS (pencarian-luasnya pertama) membentuk komponen terhubung yang berisi node awal.

bipartiteness Pengujian

BFS dapat digunakan untuk menguji bipartiteness , dengan memulai pencarian di titik manapun dan bolak memberikan label ke node dikunjungi selama pencarian. Artinya, memberi label 0 ke node awal, 1 untuk semua tetangga, 0 untuk tetangga mereka tetangga ', dan seterusnya. Jika pada setiap langkah sebuah node memiliki (dikunjungi) tetangga dengan label yang sama seperti dirinya sendiri, maka grafik tidak bipartit. Jika pencarian berakhir tanpa situasi seperti ini terjadi, maka grafik adalah bipartit.