Metode Depth First Search

LancangKuning.com - Pernahkah kita berfikir, bagaimana sebuah komputer melakukan sebuah pencarian? Seperti mencari kata dalam kamus online atau mencari data di file explorer yang tersusun atas banyak folder. Salah satu metode pencarian yang sering digunakan dalam sebuah struktur data adalah Depth-First Search (DFS).

Pada sebuah struktur data, terdapat node. Node adalah unit paling dasar yang ada dalam sebuah struktur data. Node biasanya terdiri dari dua bagian yaitu data dan link yang dapat mengarah ke node lainnya. Node yang saling terhubung kemudian akan membentuk grafik atau biasa dikenal sebagai ‘pohon’ data .

Depth-First Search (DFS) adalah metode untuk menjelajahi pohon data atau grafik. Dalam DFS, pencarian akan masuk sedalam mungkin ke satu jalur kemudian kembali dan mencoba masuk ke jalur yang lain. Metode DFS seperti berjalan melalui labirin dengan menggunakan jagung sebagai penanda jalan kembali.

Baca Juga : Tempat Wisata di Riau

Kita akan menjelajahi satu arah terlebih dahulu, mencapai jalan buntu, dan kembali dan mencoba yang lain. Algoritma akan melakukan ini sampai seluruh grafik telah dieksplorasi. Banyak masalah dalam ilmu komputer dapat digambarkan dengan grafik. Misalnya, menganalisis jaringan, memetakan rute, menjadwalkan, dan menemukan spanning tree menjadi mudah menggunakan grafik. Untuk menganalisis masalah ini, algoritma pencarian grafik seperti DFS sangat berguna.

Pengaplikasian DFS

1. Untuk Weighted Graph, DFS traversal dari grafik menghasilkan pohon berukuran paling minimum dan semua pasangan jalur pohon pendek.
2. Mendeteksi cycle dalam grafik

Grafik akan disebut sebagai cycle jika dan hanya jika kita bisa melihat node pertama terhubung dengan node terakhir atau membentuk sebuah sirkuit.

Baca Juga : Akreditasi Jurusan Kampus Universitas Bandar Lampung

1. Topological Sorting

Topological sorting biasa digunakan untuk menjadwalkan pekerjaan dengan ketergantungan yang diberikan di antara pekerjaan. Dalam ilmu komputer, aplikasi jenis ini muncul untuk penjadwalan instruksi, pemesanan evaluasi sel formula ketika mengkomputasi ulang nilai formula dalam spreadsheet, sintesis logika, menentukan urutan tugas kompilasi yang harus dilakukan dalam makefile, serialisasi data, dan menyelesaikan ketergantungan simbol dalam tautan.

2. Menemukan Komponen yang Sangat Terhubung dalam suatu Grafik

Suatu graf berarah disebut sangat terhubung jika ada jalur dari setiap node dalam grafik ke setiap node lainnya. Jadi setiap node dalam grafik dapat terhubung atau memiliki link ke setiap node lain.

Kelebihan Depth-First Search

1. Membutuhkan Lebih Sedikit Memori

DFS hanya perlu melakukan perjalanan satu tingkat pada satu waktu untuk mencari tahu apakah ada node lagi setelahnya. Jadi DFS hanya perlu mengetahui satu jalur setiap menjalankan pencarian. Apabila telah selesai, DFS akan berganti jalur dan melupakan jalur yang telah dijelajahi sebelumnya. Berbeda dengan Breadth-First Search dimana BFS akan menjelajahi setiap permukaan dari struktur data dan mengingat setiap jalur yang akan dilewati setiap node yang sedang diperiksa.

2. Menemukan elemen paling jauh dalam struktur data.

DFS akan mencari dengan melewati satu jalur dan mencapai titik terdalam terlebih dahulu. Hal ini memungkinkan DFS untuk menemukan data terjauh dalam waktu yang singkat.

Baca Juga : Tempat Wisata di Pekanbaru

Kekurangan Depth-First Search

1. Tidak selalu memberikan solusi yang optimal

Tergantung dari letak data yang dicari dan ukuran struktur data yang digunakan, metode DFS dapat memberikan hasil yang beragam. Misalnya data berada di permukaan jalur terakhir, maka pencarian akan terlebih dahulu dilakukan pada jalur pertama sampai ke titik paling ujung kemudian melanjutkan ke jalur selanjutnya. Hal ini akan membuat proses pencarian menjadi cukup lama.

2. Memungkinkan terjebak

Metode DFS akan memeriksa setiap jalur sampai ke ujung. Hal ini memungkinkan adanya jalur yang ‘tidak berguna’ karena bisa saja node yang dicari tidak ada pada jalur tersebut dan menyebabkan tidak efektifnya waktu pencarian.

Jadi, metode Depth-First Search adalah metode yang mencari data dengan mencari melalui satu jalur sampai ke akhir jalur dan kemudian beralih ke jalur lain. Metode ini dapat memiliki keuntungan maupun kekurangan berdasar jenis dan ukuran struktur data serta lokasi suatu data dalam sebuah struktur data.(Aldi)