Pengertian Algoritma Depth First Search (DFS)
Algoritma Depth First Search (DFS) adalah algoritma pencarian mendalam yang digunakan untuk melintasi atau melakukan pencarian pada struktur data graf atau pohon dengan menggunakan teknik backtracking. DFS dimulai dari node awal dan dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya.
Algoritma ini pertama kali dipelajari pada abad ke-19 oleh matematikawan Prancis Charles Pierre Trmaux sebagai strategi untuk memecahkan labirin. DFS merupakan salah satu algoritma yang paling umum digunakan untuk mencari semua simpul dari suatu graf atau tree.
Proses pencarian pada algoritma DFS dilakukan pada semua anaknya terlebih dahulu, sebelum dilakukan pencarian ke node-node yang selevel. Algoritma ini melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.
Cara Kerja Algoritma Depth First Search
Cara kerja algoritma Depth First Search dimulai dengan memasukkan node akar ke dalam sebuah tumpukan. Proses berikutnya adalah mengambil simpul pertama pada level paling atas. Jika simpul tersebut merupakan solusi pencarian, proses selesai, dan hasil dikembalikan.
Jika simpul bukan solusi, seluruh simpul yang bertetangga dengan simpul tersebut dimasukkan ke dalam tumpukan. Proses ini diulang hingga seluruh simpul telah dicek dan tumpukan kosong. Pencarian selesai, dan hasil dikembalikan dengan mencatat bahwa solusi tidak ditemukan.
Langkah-langkah Algoritma DFS
- Masukkan node akar ke dalam tumpukan.
- Ambil simpul pertama pada level paling atas.
- Jika simpul merupakan solusi, selesaikan pencarian dan kembalikan hasil.
- Jika simpul bukan solusi, masukkan semua simpul yang bertetangga dengan simpul tersebut ke dalam tumpukan.
- Ulangi langkah 2 hingga 4 sampai seluruh simpul telah dicek dan tumpukan kosong.
Contoh Program Algoritma DFS
def dfs(graph, start, goal):
stack = [start]
visited = set()while stack:
current_node = stack.pop()
if current_node == goal:
return True # Solusi ditemukan
if current_node not in visited:
visited.add(current_node)
stack.extend(graph[current_node] – visited)return False # Solusi tidak ditemukan
Penerapan Algoritma DFS dalam Kehidupan Sehari-hari
Algoritma Depth-First Search (DFS) memiliki beragam penerapan dalam kehidupan sehari-hari. Salah satunya adalah dalam permainan, di mana algoritma ini dapat digunakan untuk menemukan solusi atau jalur terbaik.
Selain itu, DFS juga dapat diterapkan dalam perencanaan rute, navigasi, atau optimisasi transportasi dalam kehidupan sehari-hari. Dengan menggunakan algoritma DFS, persoalan-persoalan yang ada di kehidupan sehari-hari dapat diselesaikan dengan lebih efisien .
Dalam konteks lain, DFS juga sering digunakan dalam menyelesaikan persoalan lintasan dan sirkuit Euler. Sirkuit Euler merupakan sirkuit yang melewati setiap sisi dalam graf tepat satu kali dan kembali, dan hal ini sering ditemui pada lintasan dan sirkuit Euler