DFS (Depth First Traversal) dalam Struktur Data: Apa itu, Pemesanan & Aplikasi

Arti DFS dalam Struktur Data

DFS dalam Struktur Data, juga dikenal sebagai traversal kedalaman-pertama, adalah algoritma rekursif yang terutama digunakan untuk mencari semua simpul dari struktur data grafik atau pohon. Traversal adalah kunjungan setiap node dari grafik. Algoritme dimulai dari simpul akar (yang mungkin merupakan simpul arbitrer sebagai simpul akar dalam grafik) dan berjalan sejauh mungkin di sepanjang setiap cabang sebelum melakukan lacak balik.

Idenya adalah untuk memulai dari root atau node arbitrer dan menjaga node tetap ditandai. Setelah ini, Anda perlu pindah ke node yang berdekatan yang tidak bertanda dan melanjutkan loop ini sampai tidak ada node sebelah yang tidak bertanda. Kemudian lacak kembali dan periksa node lain yang tidak ditandai dan lintasi mereka. Langkah terakhir adalah mencetak node di dalam path.

algoritma

Merumuskan fungsi rekursif yang akan mengambil indeks node dan array yang dikunjungi.

1. Pertahankan simpul saat ini ditandai sebagai dikunjungi dan kemudian cetak.
2. Lintasi semua catatan yang disatukan dan yang tidak bertanda dan panggil fungsi rekursif dengan indeks simpul yang berdekatan.

Jelajahi Kursus Rekayasa Perangkat Lunak Populer kami

Properti

Analisis waktu dan ruang dalam DFS dalam Struktur Data bervariasi sesuai dengan area penerapannya. Secara teoritis, DFS terutama digunakan untuk melintasi grafik penuh dan membutuhkan waktu O(|V|+|E|) di mana |V| menggambarkan jumlah simpul dan |E| menggambarkan jumlah sisi. Grafik ini linier.

Dalam aplikasi ini, ruang O(|V|) juga digunakan sebagai upaya terakhir untuk menyimpan tumpukan simpul yang tersimpan di jalur pencarian dan himpunan simpul yang sudah dikunjungi. Oleh karena itu, pengaturan batas waktu dan ruang mirip dengan pencarian keluasan-pertama. Di sini, kedua algoritme yang digunakan tidak terlalu bergantung pada kompleksitasnya dan lebih pada berbagai karakteristik orde verteks yang dihasilkan oleh kedua algoritme tersebut.

Ketika membahas aplikasi DFS dalam Struktur Data yang terkait dengan domain tertentu, seperti menemukan solusi dalam perayapan web atau AI, grafik yang memerlukan traversing mungkin terlalu substansial untuk dikunjungi secara keseluruhan. Dalam kasus seperti itu, pencarian hanya dilakukan pada kedalaman terbatas; karena sumber daya yang terbatas, seperti ruang disk atau memori. Struktur data biasanya tidak digunakan untuk melacak kumpulan semua simpul yang dikunjungi sebelumnya. Pencarian yang dilakukan pada kedalaman terbatas masih membuat waktu menjadi linier ketika berhubungan dengan unit tepi dan simpul yang diperluas.

Namun, ingat bahwa nomor ini tidak memiliki ukuran yang sama dengan seluruh grafik karena beberapa simpul dapat dicari beberapa kali dan yang lainnya tidak dicari.

Dalam kasus seperti itu, DFS juga beralih ke metode heuristik untuk memilih cabang yang lebih menjanjikan. Akhirnya, ketika batas kedalaman yang sesuai tidak dapat ditentukan, apriori, DFS pendalaman berulang diterapkan melalui urutan batas yang tumbuh.

Pelajari Kursus Pengembangan Perangkat Lunak online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.

Algoritma Pencarian Kedalaman Pertama

Setiap simpul dari grafik dalam implementasi DFS standar dibagi menjadi salah satu dari dua kategori:

1. Tidak Dikunjungi
2. Dikunjungi

Algoritma ini digunakan untuk menentukan setiap simpul dan menandainya sebagai dikunjungi dan pada saat yang sama menghindari siklus.

Beginilah cara kerja algoritma DFS:

1. Letakkan setiap titik tertentu dari grafik pada tumpukan.
2. Item di atas tumpukan harus ditambahkan ke daftar yang dikunjungi.
3. Buat daftar simpul yang berdampingan dari simpul itu dan tambahkan yang tidak ada dalam daftar yang dikunjungi di bagian atas tumpukan.
4. Terus ulangi langkah sebelumnya sampai tumpukan kosong.

Pemesanan DFS

Pengurutan verteks: Ada empat cara untuk mengurutkan verteks dari graf atau pohon secara linear di DFS:

1. Daftar vertex yang diatur bagaimana mereka dikunjungi pertama kali oleh algoritma DFS dikenal sebagai pre-ordering. Ini adalah cara singkat untuk menggambarkan kemajuan pencarian.
2. Daftar vertex dalam urutan yang terakhir dikunjungi oleh algoritma dikenal sebagai post-ordering.
3. Daftar vertex dalam urutan yang berlawanan dengan kunjungan pertama mereka adalah pre-ordering terbalik. Oleh karena itu, jangan sampai salah untuk post-order.
4. Daftar verteks dalam urutan yang berlawanan dengan kunjungan terakhir mereka adalah post-ordering terbalik. Jangan sampai salah untuk pre-order.

Selain itu, ada pengurutan dan pengurutan terbalik untuk pohon biner.

Depth First Search atau DFS untuk Grafik

DFS untuk graf hampir sama dengan DFS untuk pohon. Satu-satunya perbedaan adalah bahwa grafik mungkin memiliki siklus, tidak seperti pohon. Sebuah node mungkin dikunjungi beberapa kali dan untuk menghindari pemrosesan node, array yang dikunjungi Boolean digunakan.

Keluaran Pencarian Pertama Kedalaman

Pencarian depth-first lebih mudah digambarkan dalam bentuk spanning tree dari vertex yang sudah dicapai dalam pencarian. Berdasarkan pohon merentang ini, tepi graf asli dibagi menjadi tiga kelas: tepi depan di mana simpul pohon mengarah ke salah satu turunannya, tepi belakang di mana simpul mengarah ke salah satu nenek moyangnya, dan tepi silang. , yang tidak melakukan salah satu fungsi sebelumnya.

Aplikasi Depth First Traversal (DFS)

Pencarian mendalam-pertama digunakan dalam algoritma berikut sebagai blok bangunan:

• Mencari komponen yang terhubung.
• Menemukan 2-(vertex atau edge)-komponen yang terhubung.
• Menemukan jembatan grafik.
• Menemukan komponen yang terhubung 3-(vertex atau edge).
• Pengurutan topologi.
• Menemukan komponen yang terhubung kuat.
• Mencari tahu apakah suatu spesies mirip dengan satu atau lain spesies dalam pohon filogenetik.
• Pengujian planaritas.
• Memproduksi kata-kata untuk menentukan himpunan batas dari setiap kelompok.
• Memecahkan teka-teki yang hanya memiliki satu solusi, seperti labirin.
• Generasi labirin .
• Mencari bi-konektivitas dalam grafik.

Pseudocode dan Implementasi DFS dengan Python

Fungsi init() dijalankan pada setiap node dalam pseudocode di bawah ini untuk memastikan bahwa semua vertex dikunjungi. Ini sangat penting karena grafik mungkin memiliki berbagai area yang tidak terhubung.

Berikut pseudocodenya:

DFS(G, u)

u.visited = benar

untuk setiap v G.Adj[u]

jika v.visited == false

DFS(G,v)

init() {

Untuk setiap u G

u.dikunjungi = salah

Untuk setiap u G

DFS(G, u)

}

Berikut adalah implementasi DFS dengan Python:

grafik = {

'5' : ['3′,'7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

'7' : []

}

dikunjungi = set()

def dfs(dikunjungi, grafik, simpul):

jika node tidak dikunjungi:

cetak (simpul)

dikunjungi. tambahkan(simpul)

untuk tetangga dalam grafik[simpul]:

dfs(dikunjungi, grafik, tetangga)

print("Ini DFSnya:")

dfs(dikunjungi, grafik, '5')

Keluaran:

Ini adalah DFS: 5

Jelajahi Kursus Rekayasa Perangkat Lunak Populer kami

Kompleksitas Depth First Search

John Reif mengeksplorasi kompleksitas komputasi Depth First Search. Tepatnya, dalam grafik, fakta yang diberikan adalah G, biarkan O menjadi urutan standar yang ditentukan oleh algoritma DFS berulang. G mewakili grafik, dan O mewakili output pengurutan dari algoritma DFS redundan. Keluaran ini dikenal sebagai pengurutan DFS leksikografis.

Kesimpulan

Tujuan utama dari algoritma DFS adalah mengunjungi setiap simpul tunggal yang menghindari siklus dalam grafik target. Jika Anda ingin terlibat dengan implementasi lanjutan dari operasi pencarian atau operasi pemesanan, Anda harus mempertimbangkan untuk mengikuti kursus premium dan holistik dalam Depth First Search dan Struktur Data.

upGrad memiliki beberapa kursus DFS tingkat atas seperti Master of Science dalam Ilmu Komputer dan Spesialisasi dalam Big Data .

Jika Anda berjuang untuk mengambil langkah berikutnya dan mencari beberapa saran ahli, upGrad Mentorship berusaha memberi Anda sesi tatap muka dengan konselor karir terbaik dan pakar di industri ini.