Depth-First Search di Python: Menelusuri Graf dan Pohon

Bayangkan Anda menjelajahi sebuah sistem gua yang luas. Anda memilih satu terowongan dan mengikutinya sejauh mungkin, makin dalam, hingga menemui jalan buntu. Lalu, Anda mundur ke persimpangan terakhir dan mencoba terowongan baru. Metode eksplorasi menyelam-dalam seperti ini, hanya mundur saat perlu, mirip dengan depth-first search (DFS), sebuah algoritma fundamental untuk menavigasi struktur data seperti graf dan pohon.

Jika Anda tertarik pada struktur data, algoritma, dan pemecahan masalah, DataCamp siap membantu: Pelajari lebih lanjut tentang berbagai struktur data dan algoritma terbaik untuk mengeksplorasinya di kursus Data Structures and Algorithms in Python serta tutorial kami Data Structures: A Comprehensive Guide With Python Examples.

Apa itu Depth-First Search?

Depth-first search (DFS) adalah algoritma untuk menelusuri atau mencari struktur data, seperti graf atau pohon. Gagasan dasarnya adalah menjelajah sedalam mungkin pada satu cabang graf atau pohon sebelum mundur untuk mengeksplorasi cabang alternatif. Pendekatan ini berlawanan dengan breadth-first search, yang menjelajahi semua node pada tingkat kedalaman saat ini sebelum beralih ke tingkat berikutnya. Anda dapat membaca tentang breadth-first search DI SINI.

Anggap depth-first search sebagai cara menjelajahi labirin: Anda memilih satu jalur dan mengikutinya sampai menemui jalan buntu. Setelah mencapai ujung jalur tersebut, Anda mundur ke titik keputusan terakhir dan mencoba rute lain. Eksplorasi mendalam ini membuat DFS sangat cocok saat tujuan Anda adalah menjelajahi struktur secara menyeluruh, terutama yang memiliki banyak kemungkinan jalur.

DFS sangat berguna untuk masalah di mana Anda perlu mengeksplorasi setiap kemungkinan solusi.

Beberapa contohnya antara lain:

• Menavigasi pohon keputusan dalam AI, di mana setiap cabang mewakili rangkaian pilihan, dan tujuannya adalah mengevaluasi semua kemungkinan hasil.
• Masalah pencarian jalur, seperti menavigasi papan permainan atau menemukan rute pada peta, yang memerlukan penelusuran menyeluruh.

DFS memastikan setiap node dikunjungi sekali dan algoritma mencakup seluruh graf atau pohon.

Fitur Utama Depth-First Search di Python

Depth-first search memiliki pendekatan sistematis untuk mengeksplorasi node dan hanya melakukan backtracking bila perlu. Mari kita lihat beberapa karakteristik utamanya.

Sifat rekursif

Pada intinya, DFS bekerja secara rekursif, artinya ia menyelesaikan masalah dengan berulang kali memanggil dirinya sendiri saat menelusuri lebih dalam ke struktur. Ketika DFS menyelam ke satu cabang, ia mengeksplorasinya sedalam mungkin sebelum kembali ke atas untuk menjelajahi cabang lain. Proses menyelam ke jalur dan mundur saat tidak ada opsi lanjutan ini ideal ditangani melalui rekursi. Lihat Understanding Recursive Functions in Python untuk pembahasan mendalam tentang apa itu fungsi rekursif dan kapan fungsinya bermanfaat.

Backtracking

Backtracking sangat penting dalam DFS. Saat algoritma mencapai node yang tidak memiliki tetangga yang belum dikunjungi, ia menelusuri kembali langkahnya ke node sebelumnya dan memeriksa apakah masih ada tetangga lain yang belum dikunjungi di sana. Jika ada, ia akan mengeksplorasinya; jika tidak, ia terus melakukan backtracking. Siklus menyelam lebih dalam dan menelusuri kembali ini berlanjut hingga semua kemungkinan jalur tercakup atau hingga kondisi berhenti terpenuhi.

Menangani siklus

Graf dapat mengandung siklus, yaitu jalur yang kembali ke dirinya sendiri. Tanpa kehati-hatian, DFS bisa mengunjungi ulang node dalam siklus ini tanpa henti. Dengan menandai setiap node sebagai telah dikunjungi saat pertama kali ditemui, DFS dapat menghindari menelusuri ulang langkah-langkahnya secara tidak perlu. Dengan cara ini, bahkan pada graf yang bersiklus, DFS tetap efisien dan menghindari loop tak berujung.

Eksplorasi menyeluruh

Salah satu ciri khas DFS adalah kemampuannya untuk mengeksplorasi struktur secara penuh. Algoritma berlanjut hingga setiap node telah dikunjungi. Hal ini sangat berguna ketika Anda perlu memastikan tidak ada potensi solusi yang terlewat, seperti saat memecahkan teka-teki, mengeksplorasi pohon keputusan, atau menavigasi labirin.

Mengimplementasikan Depth-First Search di Python

Ada dua cara utama untuk mengimplementasikan depth-first search di Python: secara rekursif dan iteratif. Masing-masing memiliki kelebihan dan kompromi, dan pilihan sering bergantung pada ukuran graf dan masalah yang Anda selesaikan.

Untuk mengilustrasikan kedua metode, mari buat pohon keputusan sederhana dan gunakan DFS untuk menelusurinya. Kita akan menggunakan Python untuk contoh ini. Anda selalu bisa melihat Python Programming skill track untuk menyegarkan kemampuan Python Anda.

Mari ambil contoh pohon keputusan biner. Berikut struktur pohon sederhana di mana tiap node memiliki dua cabang anak:

Mari kita definisikan pohon keputusan ini secara eksplisit di Python sebagai sebuah dictionary.

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}Didukung oleh

DFS Rekursif

DFS sering diimplementasikan secara rekursif. Pada setiap node, DFS memanggil dirinya pada node anak hingga tidak ada lagi yang perlu dikunjungi, lalu melakukan backtracking. Berikut fungsi DFS rekursif untuk menelusuri pohon tersebut.

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')Didukung oleh

Pada versi rekursif ini, kita mulai dari node akar A dan menjelajah ke setiap cabang sebelum mundur untuk mengeksplorasi alternatifnya. Jika kita menjalankan kode ini, ia akan mencetak jalur yang ditempuh saat menelusuri pohon ini:

A
B
D
H
I
E
J
K
C
F
L
M
G
N
ODidukung oleh

DFS Iteratif

Untuk pohon keputusan yang sangat besar, batas kedalaman rekursi Python bisa menimbulkan masalah. Dalam kasus tersebut, kita dapat mengimplementasikan DFS secara iteratif, menggunakan stack untuk mengelola node yang perlu dikunjungi. Berikut cara kita dapat mengimplementasikan DFS iteratif untuk pohon keputusan yang sama:

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')Didukung oleh

Pendekatan iteratif ini menghindari batas kedalaman rekursi dengan menangani stack secara manual, yang berguna untuk pohon besar atau struktur yang dalam. Menjalankan kode ini menghasilkan keluaran yang sama seperti di atas.

Kapan Menggunakan DFS Rekursif vs. Iteratif

Kedua pendekatan—rekursif dan iteratif—untuk depth-first search merupakan alat yang berharga, namun pilihan di antara keduanya bergantung pada struktur graf dan kebutuhan spesifik Anda. Mari kita lihat lebih dekat kekuatan dan keterbatasan masing-masing.

DFS Rekursif

Saya umumnya menyukai DFS rekursif karena kesederhanaan dan keanggunannya. Pendekatan ini intuitif dan bersih.

Kelebihan:

• Kesederhanaan: Kodenya ringkas dan mencerminkan permasalahan dengan baik.
• Keterbacaan: Lebih mudah dipahami, terutama untuk masalah kecil hingga menengah.

Kekurangan:

• Batas Kedalaman Rekursi: Untuk graf besar, Anda mungkin mencapai batas kedalaman rekursi Python.

Rekursi ideal untuk masalah di mana pohon atau graf relatif kecil dan nyaman berada dalam batas kedalaman rekursi Python.

DFS Iteratif

Meski sedikit lebih kompleks untuk ditulis, DFS iteratif lebih fleksibel dan dapat menangani masalah yang lebih besar tanpa khawatir tentang batas rekursi. Alih-alih mengandalkan call stack Python, DFS iteratif secara eksplisit mengelola node yang akan dieksplorasi melalui sebuah stack.

Kelebihan:

• Tidak Terbatas Rekursi: Mengelola stack secara manual menghindari batas kedalaman rekursi Python.

Kekurangan:

• Lebih Banyak Kode: DFS iteratif memerlukan lebih banyak penyiapan dan bisa kurang intuitif.
• Keterbacaan: Kodenya sering sedikit lebih bertele-tele, sehingga lebih sulit diikuti.

Pendekatan iteratif paling baik untuk masalah besar atau kompleks ketika kedalaman rekursi menjadi perhatian. Ini juga berguna saat Anda memerlukan kontrol lebih atas penelusuran.

Kompleksitas Waktu dan Ruang

DFS adalah algoritma yang efisien, tetapi kinerjanya dipengaruhi oleh ukuran dan struktur graf yang dijelajahi. Lama waktu berjalan dan banyaknya memori yang digunakan bergantung pada jumlah node yang dikunjungi serta koneksi di antaranya.

Kita menggunakan notasi Big-O untuk membahas kompleksitas. Untuk penyegaran tentang notasi Big O, lihat Big O Notation and Time Complexity Guide: Intuition and Math.

Kompleksitas waktu

Kompleksitas waktu DFS didefinisikan sebagai O(V + E), di mana V adalah jumlah node dan E adalah jumlah koneksi (disebut "edge"). DFS mengunjungi setiap node dan setiap koneksi satu kali. Jadi, total waktu yang dibutuhkan DFS bergantung pada berapa banyak node dan koneksi yang ada.

Kompleksitas ruang

Ruang yang digunakan dalam DFS bergantung pada berapa banyak node yang sedang dilacak algoritma pada suatu saat. Baik DFS rekursif maupun iteratif menggunakan stack untuk melacak node yang sedang dieksplorasi. Pada skenario terburuk, memori yang digunakan dapat menampung semua node dalam graf, menghasilkan kompleksitas ruang O(V).

Jelajahi cara lain untuk mengukur kompleksitas algoritma dalam tutorial Analyzing Complexity of Code through Python.

Aplikasi Dunia Nyata dari Depth-First Search

DFS berguna di banyak bidang, termasuk ilmu komputer, AI, dan pengembangan game. Lihat tabel di bawah untuk beberapa aplikasi umum DFS.

Depth-First Search vs. Algoritma Pencarian Lain

Mari bandingkan DFS dengan algoritma terkenal lainnya seperti breadth-first search, Dijkstra, dan A*.

Depth-first search versus breadth-first search

Breadth-first search (BFS) menjelajahi graf per tingkat, mengunjungi semua node pada kedalaman saat ini sebelum beralih ke tingkat berikutnya. BFS sangat berguna ketika tujuannya adalah menemukan jalur terpendek pada graf tak berbobot. Namun, BFS dapat menggunakan banyak memori, terutama pada graf yang lebar, karena harus melacak semua node pada setiap tingkat. BFS sangat cocok untuk analisis jejaring sosial atau masalah perutean sederhana.

Sebaliknya, depth-first search berguna ketika tujuannya adalah mengeksplorasi semua kemungkinan jalur atau solusi, seperti pemecahan teka-teki atau menemukan siklus dalam graf. Tidak seperti BFS, DFS tidak menjamin jalur terpendek. Namun, DFS lebih hemat memori karena hanya melacak jalur saat ini.

Anda dapat mempelajari lebih lanjut tentang breadth-first search Breadth-First Search: A Beginner’s Guide with Python Examples.

DFS versus algoritma Dijkstra

Algoritma Dijkstra dirancang untuk menemukan jalur terpendek pada graf berbobot, di mana setiap tautan antar node memiliki biaya terkait. Dijkstra bekerja dengan selalu mengeksplorasi jalur berbiaya terendah terlebih dahulu, sehingga memastikan jalur optimal dari node awal ke node lainnya ditemukan. Namun, dalam penjelajahan graf sederhana tertentu, Dijkstra bisa lebih lambat daripada DFS. Dijkstra sangat tepat untuk tugas di mana bobot edge berpengaruh, seperti jaringan jalan atau masalah perutean yang lebih kompleks.

Depth-first search tidak mempertimbangkan bobot edge, sehingga tidak akan menjamin jalur optimal. Namun, DFS lebih cepat daripada Dijkstra pada graf tak berbobot atau ketika bobot edge tidak relevan.

Anda dapat mempelajari lebih lanjut tentang Algoritma Dijkstra di Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial.

DFS versus A*

A* (dibaca “A-star”) adalah algoritma yang menyempurnakan Dijkstra dengan memasukkan heuristik untuk membimbing pencarian. Ini membuatnya lebih cepat dan efisien dalam banyak kasus. A* menyeimbangkan antara mengeksplorasi jalur berbiaya terendah (seperti Dijkstra) dan langsung menuju target, menggunakan heuristik seperti jarak garis lurus ke tujuan. Hal ini membuat A* sangat efisien untuk tugas seperti navigasi GPS atau pencarian jalur pada gim video.

Depth-first search tidak menggunakan heuristik apa pun, sehingga tidak memiliki “arah” seperti A* untuk mencapai tujuan secara efisien. DFS lebih cocok untuk masalah yang memerlukan penelusuran menyeluruh atas seluruh graf atau pohon keputusan, sedangkan A* lebih baik ketika jalur terpendek perlu ditemukan secara efisien dengan bantuan heuristik.

Kendala Umum dan Cara Menghindarinya

Saat menggunakan depth-first search, beberapa masalah umum dapat muncul, terutama pada graf besar.

Gagal melacak node yang sudah dikunjungi

Salah satu masalah timbul ketika lupa melacak node mana yang sudah dikunjungi. Ini dapat menyebabkan loop tak berujung, terutama pada graf yang mengandung siklus. Saat DFS mengunjungi ulang node tanpa memeriksa apakah sudah dieksplorasi, ia bisa terjebak dalam loop tak berujung. Untuk menghindarinya, pastikan untuk menjaga daftar node yang telah dikunjungi. Sebelum mengunjungi node baru, periksa apakah ia sudah ada dalam himpunan visited. Jika iya, Anda dapat melewatinya dengan aman dan terhindar dari jebakan.

Stack overflow pada DFS rekursif

Di Python, kedalaman rekursi secara bawaan dibatasi sekitar 1.000 level, yang berarti pemanggilan rekursif yang sangat dalam pada graf besar dapat menyebabkan RecursionError. Untuk mencegah hal ini, kita dapat menggunakan implementasi DFS iteratif untuk graf besar. Dengan mempertahankan stack sebagai list, kita menghindari batas kedalaman rekursi dan dapat menangani graf yang jauh lebih besar dengan aman.

Keliru mengira solusi sebagai jalur terpendek

Penting juga untuk diingat bahwa DFS tidak menjamin jalur terpendek antara dua node. Karena DFS mengikuti satu jalur secara mendalam sebelum mundur untuk mengeksplorasi jalur lain, ia mungkin menemukan sebuah solusi, tetapi belum tentu yang paling langsung.

Kesimpulan

Depth-first search adalah algoritma yang ampuh untuk mengeksplorasi dan menelusuri graf serta pohon. Dengan kemampuannya menyelam dalam ke jalur dan mengeksplorasi semua kemungkinan, algoritma ini sangat cocok untuk berbagai masalah seperti pemecahan labirin, pemecahan teka-teki, dan eksplorasi pohon keputusan.

Jika Anda tertarik pada algoritma pencarian, lihat artikel saya yang lain dalam seri ini: Binary Search in Python: A Complete Guide for Efficient Searching dan Breadth-First Search: A Beginner’s Guide with Python Examples. Anda mungkin juga tertarik pada AVL Tree: Complete Guide With Python Implementation, dan Introduction to Network Analysis in Python.