Kompleksitas waktu dan ruang

Kompleksitas Waktu:

• O(V + E)
  • Membangun adjacency list menyentuh setiap edge satu kali, dan traversal mengunjungi setiap vertex serta memeriksa setiap edge beberapa kali dengan jumlah tetap.

Kompleksitas Ruang:

• O(V + E)
  • Adjacency list menyimpan setiap edge, sedangkan array visited dan stack masing-masing menampung hingga V vertex.

Ringkasan:

• DFS menjelajah sedalam mungkin terlebih dahulu, lalu melakukan backtracking saat kehabisan tetangga yang belum dikunjungi.
• DFS berjalan dalam waktu linear dan menjadi dasar bagi banyak algoritma graf.