Pencarian mendalam (DFS)
Menjelajahi graf dengan mengikuti satu jalur sedalam mungkin, lalu kembali ke percabangan terakhir. Tumpukan di layar adalah jalur itu.
- waktu O(V + E)
- memori O(V)
- memakai tumpukan
Apa artinya?
- Simpul: titik pada graf, di sini digambar sebagai lingkaran berhuruf.
- Sisi: garis yang menghubungkan dua simpul. Di sini sisi bisa dilalui ke dua arah.
- Tetangga: simpul-simpul yang terhubung ke suatu simpul lewat sisi. Tetangga diperiksa menurut urutan abjad.
- Antrean: yang pertama masuk, pertama keluar. BFS selalu mengambil simpul yang paling lama menunggu.
- Tumpukan: yang terakhir masuk, pertama keluar. DFS selalu melanjutkan dari simpul yang terakhir dicapainya.
- V dan E: jumlah simpul dan sisi. O(V + E) berarti setiap simpul dan setiap sisi diproses dalam jumlah kali yang tetap.
- di tumpukan
- saat ini
- tuntas
- sisi pohon pencarian
- sisi yang diabaikan
Mulai dari A. Tekan putar atau jalankan langkah demi langkah.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih graf dengan siklus. Setiap sisi putus-putus mengarah kembali ke simpul yang sudah ada di tumpukan atau sudah tuntas: sisi itu menutup sebuah siklus.
Cara kerjanya
DFS memanggil dirinya sendiri pada tetangga pertama yang belum dilihat, lalu pada tetangga baru pertama dari simpul itu, dan seterusnya. Saat sebuah simpul tidak punya tetangga baru lagi, panggilannya selesai dan DFS mundur satu langkah untuk mencoba tetangga berikutnya di sana. Panggilan yang masih terbuka membentuk tumpukan, yang selalu berupa jalur dari awal ke simpul saat ini. Angka di samping simpul adalah urutan kunjungannya.
Kapan ini pilihan yang tepat
Gunakan DFS untuk mengetahui apa saja yang bisa dicapai, menemukan siklus, menelusuri labirin, atau mengurutkan tugas yang saling bergantung. DFS tidak menemukan jalur terpendek.