Algoritma DFS (Depth First Search) 6


Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.
Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.



Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik yang ada
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Titik awalTitik TujuanBiaya
Titik ATitik B10
Titik ATitik E11
Titik BTitik A12
Titik BTitik C20
Titik BTitik D6
Titik BTitik E9
Titik CTitik B15
Titik CTitik D14
Titik DTitik B7
Titik DTitik C5
Titik ETitik C8
Titik ETitik D13

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
heldkarpawal



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

Const jumlahTitik As Integer = 5

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan inisialisasi daftar titik sebanyak jumlah titik, dan masukkan masing-masing titik ke dalam daftar

Dim daftarTitik() As Integer = New Integer(jumlahTitik - 1) {0, 1, 2, 3, 4}

2. Lakukan inisialisasi daftar jalur sesuai dengan data yang tersedia
Terdapat matriks berukuran [jumlah titik x jumlah titik] untuk menyimpan jalur dari masing-masing titik
Jika tidak ada jalur diantara 2 titik, maka nilai jalurnya adalah 0

Dim daftarBiaya(,) As Double = New Double(jumlahTitik - 1, jumlahTitik - 1) { _
	{0, 10, 0, 0, 11}, _
	{12, 0, 20, 6, 9}, _
	{0, 15, 0, 14, 0}, _
	{0, 7, 5, 0, 0}, _
	{0, 0, 8, 13, 0} _
}

3. Tentukan titik awal pencarian jalur

Console.WriteLine("Tentukan titik awal pencarian jalur antara 1 sampai dengan " & jumlahTitik & ": ")
Dim idxTitikAwal As Integer = Integer.Parse(Console.ReadLine) - 1

4. Lakukan perhitungan pencarian jalur melalui semua titik yang ada
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 4a – 4e)

Dim jalur As ArrayList = DFS(daftarTitik, daftarBiaya, idxTitikAwal)

Memasuki perhitungan pada fungsi DFS

4a. Masukkan titik awal sebagai titik pertama yang akan dicari jalurnya

Dim daftarInduk As New ArrayList()
daftarInduk.Add(idxTitikAwal)

4b. Kemudian masukkan titik-titik lain secara terurut dari titik terakhir ke titik pertama

For i As Integer = daftartitik.Length - 1 To 0 Step -1
	If i <> idxTitikAwal Then daftarInduk.Add(i)
Next

4c. Inisialisasi variabel depth / kedalaman untuk mengetahui kedalaman pada saat pencarian jalur

Dim depth(daftartitik.Count - 1) As Integer
Dim depthNormal(daftartitik.Count - 1) As Integer
For i As Integer = 0 To depthNormal.Length - 1
	depth(i) = daftartitik.Count - i
	depthNormal(i) = daftartitik.Count - 1 - i
Next

4d. Masukkan titik pertama ke dalam jalur yang akan dihitung
Dan hilangkan titik tersebut dari daftar titik yang sudah dihitung

Dim jalur As New ArrayList()
jalur.Add(daftarInduk(0))
daftarInduk.RemoveAt(0)
depth(jalur.Count - 1) -= 1

4e. Lakukan perhitungan selama masih ada titik yang belum dihitung (poin 4e1 – 4e4)

4e1. Masukkan titik berikutnya ke dalam jalur yang sedang dihitung
Dan hilangkan titik tersebut dari daftar titik yang sudah dihitung

jalur.Add(titikBerikutnya)
daftarInduk.RemoveAt(0)

4e2. Hitung kedalaman pada titik yang sedang dihitung
Apabila nilai kedalaman adalah 0, maka beri nilai awal kedalaman
Selain itu kurangkan nilai kedalamannya dengan 1

If depth(jalur.Count - 1) <= 0 Then
	depth(jalur.Count - 1) = depthNormal(jalur.Count - 1)
Else
	depth(jalur.Count - 1) -= 1
End If

4e3. Jika terdapat jalur antara titik sebelumnya dan titik berikutnya,
Lakukan pengecekan apakah semua titik sudah dihitung semua
Jika kondisi tersebut benar, maka hentikan perhitungan

If daftarBiaya(titikSebelumnya, titikBerikutnya) <> 0 Then
	If jalur.Count = daftartitik.Count Then
		Console.WriteLine("Jalur sudah ditemukan")
		Console.Write("Jalur yang terbentuk = ")
		For i As Integer = 0 To jalur.Count - 1
			Dim titik As Integer = jalur(i)
			Console.Write(IIf(i = 0, "", "-") & Chr(titik + 65))
		Next
		Console.WriteLine("")
	End If
. . .

4e4. Jika tidak terdapat jalur antara titik sebelumnya dan titik berikutnya,
maka lakukan perhitungan berikut (poin 4e4a – 4e4f)

Else
. . .

4e4a. Tampilkan pesan kesalahan karena tidak terdapat jalur antara titik sebelumnya dan titik berikutnya

Console.WriteLine("Jalur tidak valid karena Titik " & Chr(titikSebelumnya + 65) & " dan Titik " & Chr(titikBerikutnya + 65) & " tidak memiliki jarak")

4e4b. Kurangi kedalaman pada posisi titik terhitung untuk masing-masing sisa titik yang tidak terhitung

For i As Integer = 0 To daftarInduk.Count - 1
	depth(jalur.Count - 1) -= 1
Next

4e4c. Dan untuk sisa titik tersebut, beri nilai kedalaman dengan angka 0

For i As Integer = jalur.Count To depth.Count - 1
	depth(i) = 0
Next

4e4d. Untuk semua titik dengan nilai kedalaman 0,
Hilangkan titik-titik tersebut dari jalur yang sedang dihitung
dan masukkan kembali titik-titik tersebut kedalam daftar titik yang sudah dihitung

While depth(jalur.Count - 1) <= 0
	Dim titikTerakhir As Integer = jalur(jalur.Count - 1)

	daftarInduk.Add(titikTerakhir)
	jalur.Remove(titikTerakhir)
	Console.WriteLine("Melepas Titik " & Chr(titikTerakhir + 65))

	depth(jalur.Count - 1) -= 1
End While

4e4e. Tentukan titik berikutnya dengan urutan terdekat setelah titik yang terakhir dihitung
Yaitu titik dengan selisih indeks negatif terendah

Dim minSelisihNegatif As Integer = Integer.MinValue
For i As Integer = 0 To daftarInduk.Count - 2
	If daftarInduk(i) - titikTujuan < 0 AndAlso minSelisihNegatif < daftarInduk(i) - titikTujuan Then
		minSelisihNegatif = daftarInduk(i) - titikTujuan
		titikTerdekat = daftarInduk(i)
		idxtitikTerdekat = i
	End If
Next

4e4f. Setelah menemukan titik terdekat,
Urutkan semua titik yang belum dihitung selain titik terdekat dari titik terakhir ke titik pertama
Kemudian masukkan titik terdekat ini pada urutan pertama sebelum urutan tersebut

daftarInduk.RemoveAt(idxtitikTerdekat)
daftarInduk.Sort()
daftarInduk.Reverse()
daftarInduk.Insert(0, titikTerdekat)

5. Setelah menemukan jalur, maka hitung biaya untuk jalur tersebut

Dim biaya As Double = 0
For i As Integer = 0 To jalur.Count - 2
	Dim titikAwal As Integer = jalur(i)
	Dim titikTujuan As Integer = jalur(i + 1)

	biaya += daftarBiaya(titikAwal, titikTujuan)
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

cmd79

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
dfs akhir

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan Balasan ke Renal Setiadi Batalkan balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

6 pemikiran di “Algoritma DFS (Depth First Search)

  • Ahmad Suryanto

    Saya tertarik dengan algoritma DFS dan BFS, yang ingin saya tanyakan apakah kedua algoritma tersebut bisa digunakan untuk pencarian jalur terpendek (shortest path) / (dalam hal ini jarak) ? Dan jika bisa masalah apa yang mungkin akan dijumpai dalam penggunaanya ? Terimakasih min

    • pip Penulis

      Tentu saja algoritma DFS dan BFS dapat digunakan dalam pencarian jalur terpendek. Masalah yang mungkin akan dijumpai adalah jika jalur tersebut memiliki banyak titik, maka tingkat perhitungan akan semakin lama karena hampir semua kemungkinan jalur akan dicoba satu persatu.