Struktur Data - Kedalaman Traversal Pertama
Algoritma Depth First Search (DFS) melintasi grafik dalam gerakan mendalam dan menggunakan tumpukan untuk mengingat untuk mendapatkan simpul berikutnya untuk memulai pencarian, ketika jalan buntu terjadi dalam iterasi apa pun.
Seperti pada contoh yang diberikan di atas, algoritme DFS melintasi dari S ke A ke D ke G ke E ke B pertama, lalu ke F dan terakhir ke C. Algoritme ini menggunakan aturan berikut.
Rule 1- Kunjungi simpul yang belum dikunjungi yang berdekatan. Tandai sebagai telah dikunjungi. Tampilkan itu. Dorong dalam tumpukan.
Rule 2- Jika tidak ada simpul yang berdekatan ditemukan, munculkan simpul dari tumpukan. (Ini akan memunculkan semua simpul dari tumpukan, yang tidak memiliki simpul yang berdekatan.)
Rule 3 - Ulangi Aturan 1 dan Aturan 2 hingga tumpukan kosong.
| Langkah | Traversal | Deskripsi |
|---|---|---|
| 1 |
|
Inisialisasi tumpukan. |
| 2 |
|
Menandai Ssaat dikunjungi dan menaruhnya di tumpukan. Jelajahi simpul berdekatan yang belum dikunjungi dariS. Kami memiliki tiga node dan kami dapat memilih salah satunya. Untuk contoh ini, kita akan mengambil node dalam urutan abjad. |
| 3 |
|
Menandai Asaat dikunjungi dan menaruhnya di tumpukan. Jelajahi setiap node berdekatan yang belum dikunjungi dari A. KeduanyaS dan D berbatasan dengan A tapi kami prihatin hanya untuk node yang belum dikunjungi. |
| 4 |
|
Mengunjungi Ddan tandai sebagai telah dikunjungi dan dimasukkan ke dalam tumpukan. Di sini, kami punyaB dan C node, yang berdekatan dengan Ddan keduanya belum dikunjungi. Namun, kita akan memilih lagi dalam urutan abjad. |
| 5 |
|
Kami memilih B, tandai sebagai telah dikunjungi dan taruh di tumpukan. SiniBtidak memiliki simpul yang berdekatan yang belum dikunjungi. Jadi, kami meletusB dari tumpukan. |
| 6 |
|
Kami memeriksa tumpukan atas untuk kembali ke node sebelumnya dan memeriksa apakah itu memiliki node yang belum dikunjungi. Di sini, kami temukanD untuk berada di atas tumpukan. |
| 7 |
|
Hanya simpul bersebelahan yang belum dikunjungi berasal dari D adalah Csekarang. Jadi kami mengunjungiC, tandai sebagai telah dikunjungi dan taruh di tumpukan. |
Sebagai Ctidak memiliki node yang berdekatan yang belum dikunjungi jadi kami terus memunculkan tumpukan sampai kami menemukan node yang memiliki node yang berdekatan yang belum dikunjungi. Dalam hal ini, tidak ada dan kami terus bermunculan hingga tumpukan kosong.
Untuk mengetahui tentang implementasi algoritma ini dalam bahasa pemrograman C, klik disini .