Depth First Search (DFS): Pengertian, Teori, Pseudocode, dan Contoh Implementasi

Depth First Search (DFS) adalah salah satu algoritma dasar untuk menjelajah atau mencari jalur pada struktur data graf maupun pohon. Algoritma ini bekerja dengan prinsip menelusuri sedalam mungkin satu cabang sebelum kembali (backtrack) untuk menelusuri cabang lain. DFS menggunakan rekursi atau stack sebagai media penyimpanan simpul yang akan diproses selanjutnya.

Algoritma DFS pertama kali diperkenalkan pada era awal pengembangan teori graf oleh matematikawan seperti Konrad Zuse dan kemudian dipopulerkan dalam literatur algoritma komputer. DFS banyak digunakan dalam berbagai aplikasi komputasi, mulai dari pencarian jalur, pemecahan teka-teki, hingga analisis jaringan sosial dan pemrosesan bahasa alami.

Table of Contents

Dasar Teori dan Karakteristik Depth First Search

Prinsip utama DFS adalah masuk sedalam mungkin ke dalam struktur graf sebelum kembali ke simpul sebelumnya. Langkah umum DFS meliputi:

Kunjungi simpul awal dan tandai sebagai telah dikunjungi.
Pilih salah satu simpul tetangga yang belum dikunjungi.
Ulangi proses (rekursif) pada simpul tetangga tersebut.
Jika simpul tidak memiliki tetangga yang belum dikunjungi, backtrack ke simpul sebelumnya.
Proses selesai ketika semua simpul yang dapat dijangkau telah dikunjungi.

Dalam notasi Big O, kompleksitas waktu DFS pada graf dengan V simpul dan E sisi adalah O(V + E). Kompleksitas memori bergantung pada kedalaman maksimum jalur DFS. Jika menggunakan rekursi, kedalaman rekursi dapat mencapai O(V) pada graf linier. Dengan implementasi stack eksplisit, penggunaan memori juga mencapai O(V) untuk menyimpan simpul dalam antrian.

Implementasi dan Aplikasi DFS dalam Pemrograman

Berikut adalah pseudocode DFS menggunakan pendekatan rekursif:

DFS(simpul):
Tandai simpul sebagai diklik atau visited.
Untuk setiap tetangga simpul yang belum dikunjungi, panggil DFS(tetangga).
Selesai.

Varian menggunakan stack eksplisit:

Push simpul awal ke dalam stack dan tandai visited.
Sementara stack tidak kosong:
Pop simpul dari stack.
Proses simpul tersebut.
Untuk setiap tetangga yang belum dikunjungi, tandai visited dan push ke stack.
Selesai.

Contoh Implementasi di Python

Contoh sederhana DFS pada graf tak berarah direpresentasikan dengan dictionary:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# Contoh penggunaan
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited_nodes = dfs(graph, 'A')
print("Simpul terkunjungi:", visited_nodes)

def dfs(graph, start, visited=None):

if visited is None:

visited = set()

visited.add(start)

print(start)

for neighbor in graph[start]:

if neighbor not in visited:

dfs(graph, neighbor, visited)

return visited

# Contoh penggunaan

graph = {

'A': ['B', 'C'],

'B': ['A', 'D', 'E'],

'C': ['A', 'F'],

'D': ['B'],

'E': ['B', 'F'],

'F': ['C', 'E']

}

visited_nodes = dfs(graph, 'A')

print("Simpul terkunjungi:", visited_nodes)

Aplikasi Nyata DFS

DFS banyak diaplikasikan di berbagai bidang, antara lain:

Pencarian Jalur pada game atau simulasi: Menemukan rute dari titik A ke B.
Pemecahan Teka-Teki seperti Sudoku atau labirin.
Analisis Struktur Data: Menentukan komponen terhubung pada graf.
Topological Sorting pada graf berarah asiklik (DAG).
Web Crawling: Menjelajahi halaman web secara mendalam.

Kelebihan dan Kekurangan Depth First Search

Kelebihan DFS

Implementasi Sederhana: Rekursi atau stack eksplisit memudahkan kode.
Penggunaan Memori Efisien pada graf besar dengan banyak cabang sempit.
Deteksi Siklus: Mudah mengetahui apakah graf mengandung siklus.
Pencarian Mendalam: Berguna untuk menemukan solusi yang menuntut eksplorasi mendalam.

Kekurangan DFS

Risiko Stack Overflow saat rekursi terlalu dalam pada graf besar.
Tidak Optimal untuk menemukan jalur terpendek jika bobot sisi sama.
Backtracking Berlebihan dapat menghabiskan waktu pada graf dengan banyak cabang bercabang.
Beban Memori meningkat pada graf yang sangat lebar (banyak simpul pada satu level).

Dengan pemahaman mendalam tentang Depth First Search, Anda dapat memilih atau memodifikasi algoritma ini sesuai kebutuhan aplikasi, baik untuk keperluan akademis maupun industri.