Tujuan dari grey node dalam pencarian graph depth-first

Dalam banyak implementasi pencarian kedalaman-pertama yang saya lihat (misalnya: di sini ), kode membedakan antara simpul abu-abu (ditemukan, tetapi tidak semua tetangganya dikunjungi) dan simpul hitam (ditemukan dan semua tetangganya dikunjungi) . Apa tujuan dari perbedaan ini? Tampaknya algoritma DFS tidak akan pernah mengunjungi verteks yang dikunjungi terlepas dari apakah itu abu-abu atau hitam.

Ketika melakukan DFS, sembarang simpul ada di salah satu dari tiga negara bagian - sebelum dikunjungi, selama secara rekursif mengunjungi turunannya, dan setelah semua turunannya dikunjungi (kembali ke induknya, yaitu, fase penutup). Tiga warna sesuai dengan masing-masing dari tiga negara. Salah satu alasan untuk menyebutkan warna dan waktu kunjungan dan kembali adalah untuk secara eksplisit membuat perbedaan ini untuk pemahaman yang lebih baik.

Tentu saja, ada kegunaan sebenarnya dari warna-warna ini. Pertimbangkan grafik diarahkan . Misalkan Anda ingin memeriksa G untuk keberadaan siklus. Dalam grafik tidak terarah, jika simpul yang dipertimbangkan memiliki tetangga hitam atau abu-abu, ini menunjukkan siklus (dan DFS tidak mengunjunginya seperti yang Anda sebutkan). Namun, dalam kasus grafik yang diarahkan , tetangga hitam tidak berarti siklus. Sebagai contoh, perhatikan grafik dengan 3 simpul - A , B , dan C , dengan tepi diarahkan sebagai A → B , B → C , A → C . Misalkan DFS dimulai pada $G$$G$$A, B,$$C$$A \to B$$B \to C$$A \to C$$A$, Maka kunjungan , maka C . Ketika telah kembali ke A , itu kemudian memeriksa bahwa C telah dikunjungi dan berwarna hitam. Tetapi tidak ada siklus dalam grafik.$B$$C$$A$$C$

Dalam grafik terarah, sebuah siklus hadir jika dan hanya jika sebuah simpul terlihat lagi sebelum semua turunannya dikunjungi. Dengan kata lain, jika sebuah simpul memiliki tetangga yang berwarna abu-abu, maka ada siklus (dan bukan ketika tetangga itu berwarna hitam). Node abu-abu berarti kita sedang mengeksplorasi keturunannya - dan jika salah satu keturunan tersebut memiliki keunggulan untuk simpul abu-abu ini, maka ada sebuah siklus. Jadi, untuk deteksi siklus dalam grafik terarah, Anda harus memiliki 3 warna. Mungkin ada contoh lain juga, tetapi Anda harus mendapatkan idenya.

Ini adalah latihan di CLRS bahwa Anda dapat menghapus warna abu-abu atau hitam dan algoritma berfungsi dengan baik hanya dengan dua warna, dengan kata lain itu tidak benar-benar diperlukan. Tujuan utama menandai simpul adalah untuk memastikan kami tidak mengalami loop tak terbatas dengan berulang kali mengunjungi simpul yang sudah dikunjungi.

Alasan untuk menggunakan 3 warna dalam algoritma DFS terutama pedagogis: lebih jelas secara konsep, ini membantu siswa melihat apa yang terjadi selama eksekusi untuk setiap node.

Vertex abu-abu menyatakan bahwa Anda telah mengunjungi simpul itu dan pindah ke salah satu tetangganya dalam beberapa urutan, tetapi mungkin ada lebih banyak simpul yang berdekatan dengan simpul itu. Ini sementara berguna saat mundur untuk menjelajahi simpul yang belum dikunjungi.

Katakanlah Vertex A memiliki dua tetangga B dan C dan B memiliki satu tetangga D .

mulai dari titik A yang berwarna putih dan membuatnya abu - abu dan melintasi ke tetangganya.

Katakanlah dengan memilih urutan abjad mengunjungi vertex B yang berwarna putih dan menandai sebagai abu-abu.

Kemudian mengunjungi D putih -> abu-abu D -> tidak ada tetangga lagi. karenanya menandai D-> hitam .

Sekarang, backtracks ke B in Grey dan tidak ada lagi nieghbors. Karenanya tanda B-> hitam .

AGAIN backtracks A berwarna abu-abu dan kunjungi tanda c untuk c-> Gray tidak ada lagi tanda tetangga C sebagai hitam

akhirnya, kembali ke A dan menandai simpul A hitam karena tidak ada lagi simpul putih dan semuanya hitam.

Dalam DFS kami mengklasifikasikan tepi sebagai tepi-depan, tepi-belakang, tepi-silang dan tepi-pohon.

Kami menggunakan 3 warna untuk mengklasifikasikan tepi. dan warna-warna ini mewakili keadaan titik yaitu v. putih: titik v belum ditemukan.

grey: v telah ditemukan, tetapi semua simpul yang dapat dijangkau dari v belum ditemukan. jadi vertex v masih ada di stack.

black: v sudah keluar dari stack.discovered dan selesai.

Dalam melakukan DFS jika Anda menemukan titik abu-abu melalui ujung e maka itu adalah tepi belakang. Jika Anda menemukan titik hitam melalui ujung e maka itu adalah tepi silang / tepi depan. jika Anda menemukan titik putih maka Anda akan memanggil DFS secara rekursif.