Rangkuman: Depth-First Search (DFS)

Graph Traversal

1. Pengertian

Depth-First Search (DFS) adalah algoritma untuk melintasi atau mencari pohon atau struktur data graf. Algoritma ini memulai dari node (simpul) akar (atau node awal yang dipilih) dan mengeksplorasi sejauh mungkin di sepanjang setiap cabang sebelum melakukan backtracking. Dengan kata lain, DFS akan bergerak "dalam" sejauh mungkin di satu jalur sebelum kembali dan mencoba jalur lain.

DFS dapat digunakan untuk menemukan konektivitas, siklus, dan komponen terhubung dalam graf.

2. Konsep Dasar & Mekanisme

DFS menggunakan struktur data tumpukan (stack) atau rekursi (yang secara implisit menggunakan stack panggilan sistem) untuk menyimpan node-node yang akan dikunjungi. Ini memastikan bahwa node dikunjungi secara mendalam.

Langkah-langkah Algoritma (menggunakan rekursi):

  1. Mulai dari node awal (sumber), tandai node tersebut sebagai "dikunjungi".
  2. Proses node yang dikunjungi tersebut (misalnya, cetak namanya).
  3. Untuk setiap tetangga dari node saat ini:
    • Jika tetangga tersebut belum dikunjungi:
      • Panggil rekursif fungsi DFS untuk tetangga tersebut.

Penting untuk menggunakan set `visited` (atau array boolean) untuk melacak node mana yang sudah dikunjungi agar tidak masuk ke dalam siklus tak terbatas dalam graf.

3. Contoh Ilustrasi

Graf berikut:


    A --- B
    | \   |
    |  \  |
    C --- D
    |     |
    E --- F

Jika dimulai dari Node A (dengan asumsi kunjungan tetangga A: B, C, D):

  1. DFS(A). Tandai A dikunjungi. Proses A.
  2. Untuk tetangga A:
    • Coba B: DFS(B). Tandai B dikunjungi. Proses B.
    • Untuk tetangga B:
      • Coba D: DFS(D). Tandai D dikunjungi. Proses D.
      • Untuk tetangga D:
        • Coba C: DFS(C). Tandai C dikunjungi. Proses C.
        • Untuk tetangga C:
          • Coba E: DFS(E). Tandai E dikunjungi. Proses E.
          • Untuk tetangga E: (C, F - dikunjungi)
          • Kembali ke C.
        • Coba F: DFS(F). Tandai F dikunjungi. Proses F.
        • Untuk tetangga F: (D, E - dikunjungi)
        • Kembali ke D.
      • Kembali ke B.
    • Kembali ke A.
  3. (Semua sudah dikunjungi, selesai)

Urutan kunjungan (satu kemungkinan): A -> B -> D -> C -> E -> F

4. Pseudocode Algoritma


FUNCTION DFS(graph, start_node):
    visited = new Set() // Atau array boolean

    // Panggil fungsi bantu rekursif
    DFS_Recursive(graph, start_node, visited)

FUNCTION DFS_Recursive(graph, current_node, visited):
    visited.ADD(current_node)
    PRINT current_node // Atau lakukan operasi lain pada node

    FOR EACH neighbor OF current_node:
        IF neighbor IS NOT IN visited:
            DFS_Recursive(graph, neighbor, visited)

5. Kompleksitas Waktu & Ruang

  • Kompleksitas Waktu:
    • $O(V + E)$, di mana $V$ adalah jumlah simpul (vertices) dan $E$ adalah jumlah sisi (edges). Ini karena setiap simpul dan setiap sisi akan dikunjungi maksimal satu kali.
    • Mirip dengan BFS, jika graf direpresentasikan dengan matriks adjacency, kompleksitas bisa menjadi $O(V^2)$.
  • Kompleksitas Ruang: $O(V)$ untuk menyimpan set `visited` dan untuk stack rekursi (dalam kasus terburuk, stack bisa menyimpan semua simpul).

6. Aplikasi

  • **Pencarian Jalur:** Menemukan jalur antara dua simpul dalam graf (tidak selalu terpendek).
  • **Mendeteksi Siklus:** Mendeteksi adanya siklus dalam graf.
  • **Topological Sorting:** Mengurutkan node dalam graf berarah asiklik (DAG).
  • **Penyelesaian Puzzle & Permainan:** Seperti penyelesaian labirin.
  • **Web Crawlers:** Dapat digunakan untuk mengindeks halaman web dengan menjelajahi tautan secara mendalam.
  • **Finding Connected Components:** Menemukan semua komponen terhubung dalam graf.
Kembali ke Materi Materi Selanjutnya