Selamat siang.Saya mempersembahkan kepada Anda terjemahan dari artikel “Algoritma pada Grafik: Mari kita bicara Pencarian Kedalaman-Pertama (DFS) dan Pencarian Breadth-First (BFS)” oleh Try Khov.Apa itu traversal grafik?
Dengan kata sederhana, grafik traversal adalah transisi dari salah satu simpulnya ke simpul lain untuk mencari properti koneksi simpul tersebut. Tautan (garis yang menghubungkan simpul) disebut arah, jalur, wajah, atau tepi grafik. Verteks grafik juga disebut sebagai simpul.Dua algoritma traversal grafik utama adalah Depth-First Search, DFS dan Breadth-First Search, BFS.Terlepas dari kenyataan bahwa kedua algoritma digunakan untuk melintasi grafik, mereka memiliki beberapa perbedaan. Mari kita mulai dengan DFS.Pencarian Kedalaman
DFS mengikuti konsep "go deep, head first". Idenya adalah bahwa kita bergerak dari puncak mulai (titik, tempat) dalam arah tertentu (sepanjang jalur tertentu) sampai kita mencapai ujung jalur atau tujuan (puncak yang diinginkan). Jika kita telah mencapai ujung jalan, tetapi itu bukan tujuan, maka kita kembali (ke jalur bercabang atau menyimpang jalur) dan pergi di sepanjang rute yang berbeda.Mari kita lihat sebuah contoh. Misalkan kita memiliki grafik berarah yang terlihat seperti ini:
Kita berada pada titik "s" dan kita perlu menemukan simpul "t". Dengan menggunakan DFS, kami menyelidiki salah satu jalur yang mungkin, bergerak sepanjang hingga akhir dan, jika kami tidak menemukan t, kembali dan jelajahi jalur lain. Begini prosesnya:
Di sini kita bergerak di sepanjang jalan (p1) ke puncak terdekat dan melihat bahwa ini bukan akhir dari jalan. Karena itu, kami beralih ke puncak berikutnya.
Kami mencapai akhir p1, tetapi tidak menemukan t, jadi kami kembali ke s dan bergerak di sepanjang jalan kedua.
Setelah mencapai bagian atas jalur "p2" paling dekat dengan titik "s", kita melihat tiga kemungkinan arah untuk pergerakan lebih lanjut. Karena kami telah mengunjungi puncak yang memahkotai arah pertama, kami bergerak di sepanjang yang kedua.
Kami kembali mencapai ujung jalan, tetapi tidak menemukan t, jadi kami kembali. Kami mengikuti jalan ketiga dan, akhirnya, kami mencapai puncak yang diinginkan "t".
Inilah cara kerja DFS. Kami bergerak di sepanjang jalan tertentu sampai akhir. Jika ujung jalan adalah puncak yang diinginkan, kita selesai. Jika tidak, kembali dan pindah ke jalur yang berbeda hingga kami menjelajahi semua opsi.Kami mengikuti algoritma ini untuk setiap titik yang dikunjungi.Perlunya pengulangan prosedur berulang menunjukkan perlunya menggunakan rekursi untuk mengimplementasikan algoritma.Ini adalah kode JavaScript:
function dfs(adj, v, t) {
if(v === t) return true
if(v.visited) return false
v.visited = true
for(let neighbor of adj[v]) {
if(!neighbor.visited) {
let reached = dfs(adj, neighbor, t)
if(reached) return true
}
}
return false
}
Catatan: Algoritme DFS khusus ini memungkinkan Anda memeriksa apakah mungkin untuk berpindah dari satu tempat ke tempat lain. DFS dapat digunakan untuk berbagai keperluan. Sasaran ini akan menentukan bagaimana algoritma itu sendiri akan terlihat. Namun, konsep umum terlihat persis seperti itu.Analisis DFS
Mari kita menganalisis algoritma ini. Karena kita berkeliling setiap "tetangga" dari setiap node, mengabaikan mereka yang kita kunjungi sebelumnya, kita memiliki runtime yang sama dengan O (V + E).Penjelasan singkat tentang arti V + E:V adalah jumlah total simpul. E adalah jumlah total wajah (tepi).Mungkin tampak lebih tepat untuk menggunakan V * E, tetapi mari kita pikirkan apa arti V * E.V * E berarti bahwa sehubungan dengan masing-masing simpul, kita harus menyelidiki semua wajah grafik terlepas dari apakah wajah-wajah ini milik simpul tertentu.Di sisi lain, V + E berarti bahwa untuk setiap titik kami hanya mengevaluasi tepi yang berdekatan dengannya. Kembali ke contoh, setiap dhuwur memiliki sejumlah wajah dan, dalam kasus terburuk, kita berkeliling semua simpul (O (V)) dan memeriksa semua wajah (O (E)). Kami memiliki simpul V dan wajah E, jadi kami mendapatkan V + E.Lebih lanjut, karena kita menggunakan rekursi untuk melintasi setiap verteks, ini berarti bahwa stack digunakan (rekursi tak terbatas mengarah ke kesalahan stack overflow). Oleh karena itu, kompleksitas spasial adalah O (V).Sekarang pertimbangkan BFS.Pencarian luas
BFS mengikuti konsep "memperluas lebar, naik ke ketinggian penerbangan burung" ("melebar, pandangan mata burung"). Alih-alih bergerak di sepanjang jalan tertentu sampai akhir, BFS melibatkan bergerak maju satu tetangga pada satu waktu. Ini berarti yang berikut:Alih-alih mengikuti jalan, BFS berarti mengunjungi tetangga terdekat ke dalam satu tindakan (langkah), kemudian mengunjungi tetangga tetangga dan seterusnya sampai t terdeteksi.
Bagaimana DFS berbeda dari BFS? Saya suka berpikir bahwa DFS berjalan maju, dan BFS tidak terburu-buru, tetapi mempelajari segala sesuatu dalam satu langkah.Pertanyaan kemudian muncul: bagaimana Anda tahu tetangga mana yang harus dikunjungi terlebih dahulu?Untuk melakukan ini, kita dapat menggunakan konsep "first in, first out" (first-in-first-out, FIFO) dari antrian. Kami terlebih dahulu mengantri puncak yang paling dekat dengan kami, kemudian tetangga yang belum dikunjungi, dan melanjutkan proses ini sampai antrian kosong atau sampai kami menemukan titik yang kami cari.Ini kodenya:
function bfs(adj, s, t) {
let queue = []
queue.push(s)
s.visited = true
while(queue.length > 0) {
let v = queue.shift()
for(let neighbor of adj[v]) {
if(!neighbor.visited) {
queue.push(neighbor)
neighbor.visited = true
if(neighbor === t) return true
}
}
}
return false
}
Analisis BFS
Tampaknya BFS lebih lambat. Namun, jika Anda melihat secara dekat pada visualisasi, Anda dapat melihat bahwa mereka memiliki runtime yang sama.Antrian melibatkan pemrosesan setiap simpul sebelum mencapai tujuan. Ini berarti bahwa, dalam kasus terburuk, BFS mengeksplorasi semua simpul dan wajah.Terlepas dari kenyataan bahwa BFS mungkin tampak lebih lambat, sebenarnya lebih cepat, karena ketika bekerja dengan grafik besar ditemukan bahwa DFS menghabiskan banyak waktu mengikuti jalur yang akhirnya ternyata salah. BFS sering digunakan untuk menemukan jalur terpendek antara dua puncak.Jadi, runtime BFS juga O (V + E), dan karena kami menggunakan antrian yang berisi semua simpul, kompleksitas spasialnya adalah O (V).Analogi kehidupan nyata
Jika Anda memberikan analogi dari kehidupan nyata, maka ini adalah bagaimana saya membayangkan karya DFS dan BFS.Ketika saya memikirkan DFS, saya membayangkan seekor tikus dalam labirin mencari makanan. Untuk mencapai target, tikus dipaksa menemui jalan buntu berkali-kali, kembali dan bergerak dengan cara yang berbeda, dan seterusnya hingga menemukan jalan keluar dari labirin atau makanan.
Versi yang disederhanakan terlihat seperti ini:
Pada gilirannya, ketika saya berpikir tentang BFS, saya membayangkan lingkaran di atas air. Jatuhnya batu ke dalam air menyebabkan penyebaran gangguan (lingkaran) ke segala arah dari pusat.
Versi yang disederhanakan terlihat seperti ini:
temuan
- Pencarian mendalam dan luas digunakan untuk melintasi grafik.
- DFS bergerak sepanjang sisi bolak-balik, dan BFS menyebar di seluruh tetangga untuk mencari target.
- DFS menggunakan tumpukan, dan BFS antrian.
- Runtime keduanya adalah O (V + E), dan kompleksitas spasial adalah O (V).
- Algoritma ini memiliki filosofi yang berbeda, tetapi sama pentingnya untuk bekerja dengan grafik.
Catatan Per.: Saya bukan spesialis dalam algoritma dan struktur data, oleh karena itu, jika ditemukan kesalahan, ketidakakuratan, atau formulasi yang salah, silakan tulis dalam surat pribadi untuk koreksi dan klarifikasi. Saya akan berterima kasih.Terima kasih atas perhatian Anda.