- Saat ini
- Dalam tumpukan
- Selesai
- Jalur
Depth-First Search (DFS)
Depth-First Search menjelajahi graf seperti orang yang menyusuri labirin dengan satu tangan di dinding: mengikuti satu jalur sejauh mungkin, dan baru mundur ketika tidak ada tempat baru untuk dituju. Caranya dengan tumpukan. Klik simpul untuk memulai dari sana, pilih tujuan jika mau, lalu jalankan pencarian langkah demi langkah untuk melihat tumpukan bertambah dan berkurang, tiap simpul mendapat nomor kunjungannya, dan sisi yang menutup siklus. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Klik simpul untuk menjadikannya awal; ubah klik ke Tujuan lalu klik simpul lain untuk mencari jalur ke sana. Angka di tiap simpul adalah urutan kunjungannya, dan baris di bawah graf adalah tumpukan, dari awal sampai simpul di puncak. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Klik simpul untuk menjadikannya awal. Untuk mencari jalur, ubah klik ke Tujuan lalu klik simpul lain.
- Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
- Perhatikan tumpukan di bawah graf dan nomor kunjungan di tiap simpul. Graf baru membuat graf lain untuk dicoba.
Cara kerja DFS
Masukkan simpul awal ke tumpukan. Lalu ulangi: lihat tetangga berikutnya dari simpul di puncak tumpukan. Tetangga yang belum pernah dilihat mendapat nomor kunjungan berikutnya, mengingat simpul asalnya, dan masuk ke puncak tumpukan, sehingga pencarian berlanjut dari sana. Ketika simpul di puncak tidak punya tetangga lagi untuk diperiksa, simpul itu selesai dan keluar dari tumpukan, lalu pencarian mundur ke simpul di bawahnya. Ketika tumpukan kosong, setiap simpul yang bisa dicapai sudah dikunjungi.
Apa yang ditunjukkan tumpukan
Karena pencarian selalu berlanjut dari simpul terbaru, tumpukan selalu merupakan jalur dari awal ke simpul yang sedang dilihat. Saat tujuan tercapai, tumpukan adalah jalur ke sana, meski biasanya bukan yang terpendek: jalur terpendek ditemukan oleh BFS. Pada graf tanpa arah, sisi ke simpul yang masih ada di tumpukan, selain simpul asal yang baru saja ditinggalkan, menutup sebuah siklus. Simpul asal yang diingat membentuk pohon, yaitu pohon DFS, dan urutan simpul selesai adalah kunci pengurutan topologis.
Pertanyaan yang sering diajukan
Apa itu Depth-First Search?
Cara menjelajahi graf dari simpul awal dengan mengikuti satu jalur sedalam mungkin, dan baru mundur untuk mencoba cabang lain ketika tidak ada tempat baru untuk dituju. DFS memakai tumpukan, atau rekursi, untuk mengingat jalan kembali.
Apakah Depth-First Search menemukan jalur terpendek?
Tidak. DFS menemukan jalur ke tujuan jika ada, tetapi jalur itu bisa jauh lebih panjang dari yang perlu, karena DFS terus mengikuti cabang pertama yang dicobanya. Pakai BFS untuk sisi paling sedikit, atau algoritma Dijkstra jika sisi punya panjang.
Apa bedanya DFS dan BFS?
DFS memakai tumpukan dan masuk dalam di sepanjang satu jalur sebelum mundur. BFS memakai antrean dan menyebar merata, lingkaran demi lingkaran. Keduanya mengunjungi setiap simpul yang bisa dicapai dalam waktu yang bertambah sesuai jumlah simpul ditambah sisi; BFS menemukan jalur terpendek, sedangkan DFS pilihan alami untuk siklus, labirin, dan pengurutan topologis.
Bagaimana DFS menemukan siklus?
Pada graf tanpa arah, jika pencarian bertemu sisi ke simpul yang masih ada di tumpukan, dan simpul itu bukan simpul asal yang baru saja ditinggalkan, sisi itu menutup sebuah putaran. Di aplikasi, baris status memberi tahu saat itu terjadi.
Apakah graf saya dikirim ke mana pun?
Tidak. Graf dibuat dan dicari di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor