GraphsMenengahFase D–FE1E5

DFS MAZE

DFS Maze menelusuri labirin secara mendalam (Depth-First Search) dengan menjelajah satu jalur sejauh mungkin sebelum mundur dari jalan buntu. Setiap sel ditandai lalu rekursi masuk ke tetangga yang masih bebas; jika mencapai tujuan jalur dicatat, jika buntu algoritma backtrack ke persimpangan sebelumnya. Visualisasi menandai sel yang dikunjungi, dead end, dan jalur solusi hingga jalur terkunci dari awal ke tujuan.

Example use case

Menelusuri semua kemungkinan cabang untuk menemukan jalan keluar labirin, atau crawler yang menjelajah tautan situs secara mendalam.

Syllabus

DFS menjelajah satu jalur sedalam mungkin dulu, lalu mundur (backtrack) dari jalan buntu untuk mencoba cabang lain.

Objectives

·Memahami cara DFS masuk sedalam mungkin sebelum mundur
·Menjelaskan peran backtracking saat menemui jalan buntu
·Menerapkan DFS untuk menelusuri labirin atau cabang

How It Works

·Mulai dari satu simpul, tandai sudah dikunjungi
·Masuk ke salah satu tetangga yang belum dikunjungi secara rekursif
·Terus melaju sejauh mungkin menyusuri satu cabang
·Saat mentok jalan buntu, mundur ke persimpangan sebelumnya
·Coba cabang lain sampai semua simpul terjelajahi atau target ketemu

Prerequisites

·Rekursi
·Graf

Real-World Uses

·Menelusuri semua cabang labirin untuk menemukan jalan keluar
·Crawler menjelajahi tautan sebuah situs sampai ke halaman terdalam
·Mengecek semua kemungkinan langkah di game teka-teki

Complexity O(V + E)