Metode Graph Traversal selalu membuat saya terpesona. Dari melakukan komunikasi peer to peer yang efektif hingga menemukan restoran dan kafe terdekat menggunakan GPS, metode traversal memiliki serangkaian aplikasi yang bervariasi dalam skenario dunia nyata. Dalam blog Breadth-First Search Algorithm ini, kita akan membahas logika di balik metode traversal grafik dan menggunakan contoh untuk memahami cara kerja algoritma Breadth-First Search.
bagaimana menemukan nomor terbesar dalam array java
Untuk mendapatkan pengetahuan mendalam tentang Kecerdasan Buatan dan Pembelajaran Mesin, Anda dapat mendaftar secara langsung oleh Edureka dengan dukungan 24/7 dan akses seumur hidup.
Berikut daftar topik yang akan dibahas tercakup dalam blog ini:
- Pengantar Traversal Grafik
- Apa itu Breadth-First Search?
- Memahami algoritma Breadth-First Search dengan sebuah contoh
- Kode Pseudo Algoritme Penelusuran Luas-Pertama
- Aplikasi Pencarian Luas-Pertama
Pengantar Traversal Grafik
Proses mengunjungi dan menjelajahi grafik untuk diproses disebut traversal grafik. Untuk lebih spesifiknya, ini semua tentang mengunjungi dan menjelajahi setiap simpul dan tepi dalam sebuah grafik sehingga semua simpul dieksplorasi tepat satu kali.
Kedengarannya sederhana! Tapi ada batasannya.
Ada beberapa teknik traversal grafik seperti Breadth-First Search, Depth First Search dan lain sebagainya. Tantangannya adalah menggunakan grafik teknik traversal yang paling cocok untuk memecahkan masalah tertentu. Ini membawa kita ke teknik Pencarian Luas-Pertama.
Apa itu Algoritma Breadth-First Search?
Algoritme Breadth-First Search adalah teknik traverse grafik, di mana Anda memilih node awal acak (node sumber atau root) dan mulai melintasi lapisan grafik sedemikian rupa sehingga semua node dan node turunannya masing-masing dikunjungi dan dieksplorasi.
Sebelum kita melangkah lebih jauh dan memahami Pencarian Luas-Pertama dengan sebuah contoh, mari kita pelajari dua istilah penting yang terkait dengan traversal grafik:
- Mengunjungi node: Seperti namanya, mengunjungi node berarti mengunjungi atau memilih node.
- Menjelajahi node: Menjelajahi node yang berdekatan (node anak) dari node yang dipilih.
Lihat gambar di atas untuk lebih memahami ini.
Memahami Algoritma Breadth-First Search dengan sebuah contoh
Algoritme Breadth-First Search mengikuti pendekatan sederhana berbasis level untuk memecahkan masalah. Pertimbangkan pohon biner di bawah ini (yang merupakan grafik). Tujuan kami adalah melintasi grafik dengan menggunakan Algoritma Breadth-First Search.
Sebelum kita mulai, Anda harus terbiasa dengan struktur data utama yang terlibat dalam algoritma Breadth-First Search.
Antrian adalah struktur data abstrak yang mengikuti metodologi First-In-First-Out (data yang dimasukkan terlebih dahulu akan diakses terlebih dahulu). Ini terbuka di kedua ujungnya, di mana satu ujung selalu digunakan untuk memasukkan data (enqueue) dan yang lainnya digunakan untuk menghapus data (dequeue).
Sekarang mari kita lihat langkah-langkah yang terlibat dalam melintasi grafik dengan menggunakan Pencarian Luas-Pertama:
Langkah 1: Ambil Antrian Kosong.
Langkah 2: Pilih node awal (mengunjungi node) dan masukkan ke dalam Antrian.
Langkah 3: Asalkan Queue tidak kosong, ekstrak node dari Queue dan masukkan node anaknya (menjelajahi node) ke dalam Queue.
Langkah 4: Cetak node yang diekstrak.
Jangan khawatir jika Anda bingung, kami akan memahaminya dengan sebuah contoh.
Lihatlah grafik di bawah ini, kami akan menggunakan algoritma Breadth-First Search untuk melintasi grafik.
Dalam kasus kami, kami akan menetapkan node 'a' sebagai node root dan mulai melintasi ke bawah dan mengikuti langkah-langkah yang disebutkan di atas.
Gambar di atas menggambarkan proses end-to-end dari Algoritma Breadth-First Search. Izinkan saya menjelaskan ini lebih dalam.
- Tetapkan 'a' sebagai node root dan masukkan ke dalam Queue.
- Ekstrak simpul 'a' dari antrian dan masukkan simpul anak dari 'a', yaitu, 'b' dan 'c'.
- Cetak node 'a'.
- Antrian tidak kosong dan memiliki node 'b' dan 'c'. Karena 'b' adalah simpul pertama dalam antrian, mari kita ekstrak dan masukkan simpul anak dari 'b', yaitu simpul 'd' dan 'e'.
- Ulangi langkah-langkah ini sampai antrian kosong. Perhatikan bahwa node yang sudah dikunjungi tidak boleh ditambahkan ke antrian lagi.
Sekarang mari kita lihat pseudocode dari algoritme Breadth-First Search.
Kode Pseudo Algoritme Penelusuran Luas-Pertama
Berikut adalah pseudocode untuk menerapkan Algoritme Penelusuran Luas-Pertama:
Input: s sebagai node sumber BFS (G, s) biarkan Q menjadi antrian. Q. tanda antrian s sudah dikunjungi sementara (Q tidak kosong) v = Q. dequeue () untuk semua tetangga w dari v di Grafik G jika w tidak dikunjungi Q. tanda antrian (w) w sebagai dikunjungi
Pada kode di atas, langkah-langkah berikut dijalankan:
- (G, s) adalah masukan, di sini G adalah graf dan s adalah simpul akar
- Sebuah antrian 'Q' dibuat dan diinisialisasi dengan source node 's'
- Semua simpul anak 's' ditandai
- Ekstrak 's' dari antrian dan kunjungi simpul anak
- Proses semua simpul anak dari v
- Menyimpan w (simpul anak) di Q untuk mengunjungi simpul anaknya lebih jauh
- Lanjutkan sampai 'Q' kosong
Sebelum kita menutup blog, mari kita lihat beberapa aplikasi algoritma Breadth-First Search.
Aplikasi Algoritma Pencarian Breadth-First
Breadth-first Search adalah metode traversal grafik sederhana yang memiliki berbagai aplikasi yang mengejutkan. Berikut adalah beberapa cara menarik di mana Bread-First Search digunakan:
Crawler di Mesin Pencari: Breadth-First Search adalah salah satu algoritme utama yang digunakan untuk mengindeks halaman web. Algoritme mulai melintasi dari halaman sumber dan mengikuti semua link yang terkait dengan halaman tersebut. Di sini setiap halaman web akan dianggap sebagai node dalam grafik.
Sistem Navigasi GPS: Breadth-First Search adalah salah satu algoritma terbaik yang digunakan untuk menemukan lokasi tetangga dengan menggunakan sistem GPS.
Temukan Jalur Terpendek & Pohon Rentang Minimum untuk grafik tak berbobot: Dalam hal grafik tidak berbobot, menghitung jalur terpendek cukup sederhana karena ide di balik jalur terpendek adalah memilih jalur dengan jumlah sisi paling sedikit. Breadth-First Search dapat memungkinkan ini dengan melintasi jumlah minimum node yang dimulai dari node sumber. Demikian pula, untuk pohon bentang, kita dapat menggunakan salah satu dari keduanya, metode Breadth-First Search atau Depth-first traversal untuk menemukan pohon bentang.
Penyiaran: Jaringan memanfaatkan apa yang kita sebut sebagai paket untuk komunikasi. Paket-paket ini mengikuti metode traversal untuk menjangkau berbagai node jaringan. Salah satu metode traversal yang paling umum digunakan adalah Breadth-First Search. Ini digunakan sebagai algoritma yang digunakan untuk mengkomunikasikan paket yang disiarkan di semua node dalam jaringan.
Jaringan Peer to Peer: Breadth-First Search dapat digunakan sebagai metode traversal untuk menemukan semua node yang bertetangga di Jaringan Peer to Peer. Misalnya, BitTorrent menggunakan Breadth-First Search untuk komunikasi peer to peer.
c ++ stl sort
Jadi itu semua tentang cara kerja algoritma Breadth-First Search. Sekarang setelah Anda mengetahui cara melintasi grafik, saya yakin Anda penasaran untuk mempelajari lebih lanjut. Berikut beberapa blog yang relevan untuk membuat Anda tetap tertarik:
Dengan ini, kita sampai pada bagian akhir blog ini. Jika Anda memiliki pertanyaan tentang topik ini, silakan tinggalkan komentar di bawah dan kami akan menghubungi Anda kembali.
Jika Anda ingin mendaftar untuk kursus lengkap tentang Kecerdasan Buatan dan Pembelajaran Mesin, Edureka memiliki kurasi khusus yang akan membuat Anda mahir dalam teknik seperti Supervised Learning, Unsupervised Learning, dan Natural Language Processing. Ini mencakup pelatihan tentang kemajuan terbaru dan pendekatan teknis dalam Kecerdasan Buatan & Pembelajaran Mesin seperti Pembelajaran Mendalam, Model Grafis, dan Pembelajaran Penguatan.