Algoritma Graph Depth First Search


Depth First Search

Depth First Search

Secara matematis (Hafid Inggantowi, 2008, hlm. 2), graf didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini :

V = himpunan tidak kosong dari simpul-simpul (vertices atau node) = {v1,v2, …, vn } dan

E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = { e1, e2, …, en}

Sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi minimal simpulnya harus ada satu. Oleh karena itu, V tidak boleh kosong, sedangkan E boleh kosong.

graf

Contoh Graf

Menurut siswanto (2010, hlm. 77). Depth first search (DFS) adalah pencarian kemungkinan metode terbaik yang dapat diikuti dimana heuristic tidak digunakan.

DFS sebuah algoritma umum traversal atau pencarian pada pohon, struktur pohon, atau graf. pencarian yang berjalan dengan meluaskan anak akar pertama dari pohon pencarian yang dipilih dan berjalan dalam dan lebih dalam lagi sampai simpul tujuan ditemukan, atau sampai menemukan simpul yang tidak punya anak. Kemudian, pencarian backtracking, akan kembali ke simpul yang belum selesai ditelusuri. Dalam implementasi nonrekursif , semua simpul yang diluaskan ditambahkan ke LIFO (Last-In, First-Out) stack untuk penelusuran. (Hafid Inggantowi, 2008, hlm. 3).

Berikut terdapat suatu pohon pencarian :

Pohon pencarian (search tree)

Pohon pencarian (search tree)

Pada graf yang kita miliki di atas (Gambar 2.2), hubungan antara lintasan tidak dua arah. Semua lintasan hanya berjalan dari atas ke bawah. Dengan kata lain, A memiliki lintasan ke B dan C, tapi B dan C tidak memiliki lintasan ke A. Jadi, secara umum bisa kita anggap seperti jalan satu arah (one way street). (Hafid Inggantowi, 2008, hlm. 3).

Referensi :

  1. Inggiantowi , H. (2008).”Perbandingan Algoritma Penelusuran Depth First Search dan Breadth First Search pada Graf serta Aplikasinya [Online]. diakses dari : http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2008-2009/Makalah2008/Makalah0809-054.pdf (21 Mei 2015).
  2. Siswanto. (2010). Kecerdasan Tiruan. Yogyakarta : Graha Ilmu