Motivasi

DFS menjelajahi graph dengan berkomitmen pada suatu jalur dan mengikutinya sejauh mungkin, lalu melakukan backtracking ke vertex terakhir yang masih memiliki tetangga yang belum dijelajahi.

Mengapa perlu mempelajari DFS?

• Dasar: DFS menjadi dasar deteksi siklus, pengurutan topologis, komponen terhubung, dan banyak algoritma lainnya.
• Sederhana dan hemat: DFS berjalan dalam waktu O(V + E) dengan menggunakan stack (atau rekursi) dan penanda kunjungan.
• Serbaguna: traversal yang sama menjawab pertanyaan seperti "apakah kedua vertex ini terhubung?" dan "berapa banyak bagian terpisah yang dimiliki graph ini?"

Agar hasilnya tetap konsisten, kita selalu mengunjungi tetangga suatu vertex dalam urutan menaik.