DEPTH-FIRST SEARCH (DFS)

Depth-First Search (DFS)

Dokumen ini membahas algoritma Depth-First Search (DFS), yaitu metode traversal graf yang mendalami cabang graf hingga akhir sebelum kembali (backtrack) dan melanjutkan ke cabang lain.

---

Definisi Depth-First Search

Depth-First Search (DFS) adalah teknik penelusuran graf yang mengeksplorasi jalur secara mendalam hingga tidak ada lagi simpul yang dapat dikunjungi, kemudian kembali (backtrack) dan mencoba jalur lainnya.

Kegunaan DFS:

• Menemukan jalur dalam graf
• Mendeteksi siklus
• Menemukan komponen terhubung
• Melakukan penyusunan topologis (topological sort)

---

Mekanisme Kerja: Rekursi atau Stack

DFS dapat diimplementasikan melalui:

• Rekursi, menggunakan call stack sistem
• Stack eksplisit, dalam bentuk pendekatan iteratif

Langkah-langkah DFS:

1. Mulai dari simpul awal
2. Tandai simpul sebagai dikunjungi
3. Telusuri simpul tetangga yang belum dikunjungi
4. Kembali jika tidak ada simpul yang tersisa untuk dikunjungi

---

Contoh Ilustrasi DFS

Graf sederhana:

     A
    / \
   B   C
  /     \
 D       E

Urutan traversal dari simpul A:

• A → B → D → C → E

---

Implementasi dalam C++

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) 
}}

int main() ;   // A = 0
    adj[1] = 0;   // B = 1
    adj[2] = 0;   // C = 2
    adj[3] = 1;      // D = 3
    adj[4] = 2;      // E = 4

    vector<bool> visited(n, false);
    dfs(0, adj, visited);

    return 0;
}}

---

Aplikasi Depth-First Search

1. Penyelesaian Puzzle dan Maze: DFS membantu menyusuri jalur hingga akhir dalam permainan atau teka-teki.
2. Deteksi Siklus: Memeriksa apakah terdapat siklus dalam suatu graf.
3. Penyusunan Topologis: Menentukan urutan tugas berdasarkan ketergantungan.
4. Analisis Jaringan: Mengidentifikasi komponen yang saling terhubung dalam jaringan komputer.

---

Kelebihan dan Kekurangan

Kelebihan:

• Menggunakan memori yang lebih sedikit dengan pendekatan rekursif
• Efektif untuk penelusuran graf yang dalam
• Implementasi sederhana

Kekurangan:

• Tidak selalu menghasilkan jalur terpendek
• Dapat menjelajahi jalur yang tidak optimal terlebih dahulu

---

Kesimpulan

Depth-First Search adalah algoritma yang mendalami graf hingga ke ujung cabang sebelum menelusuri jalur lain. DFS berguna dalam berbagai aplikasi seperti deteksi siklus, penyusunan topologis, dan eksplorasi jaringan. Pendekatan ini sangat efisien untuk struktur data dengan kedalaman besar.

Semoga pembahasan ini membantu dalam memahami dan mengimplementasikan algoritma DFS secara menyeluruh.