Mengenal Algoritma Traversal di dalam Graf - Skripsi Teknik Informatika

Kali ini saya akan membangikan pengetahuan kepada anda tentang algoritma travesal, mungkin bagi anda yang membutuhkan info tersebut artikel ini bisa membantu anda dalam memahami tentang algoritma travesal di dalam graf. Baik langsung saja berikut adalah penjelasannya

Traversal di dalam graf berarti mengunjungi simpul-simpul dengan cara yang sistematik, didalam algoritma tersebut dibagi menjadi dua yaitu :


1. Pencarian Melebar (Breadth First Search atau BFS),

2. Pencarian Mendalam (Depth First Search atau DFS). 

Untuk selanjutnya kita akan membahas tentang apa itu BFS dan apa itu DFS, tentunya disertai dengan contoh masing-masing. Yang pertama kita akan membahas tentang algoritma BFS.

Baca juga Jasa Bimbingan Skripsi Teknik Informatika

Algoritma Pencarian Melebar (BFS)

Alur jalan algoritma BFS

1. Kunjungi simpul v.

2. Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu. 

3. Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi                           dikunjungi, demikian seterusnya. 

• Jika graf berbentuk pohor berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum mengunjungi simpul-simpul pada aras d + 1.

Contoh 1:  (misalkan traversal dimulai dari simpul 1)

(a) (b) (c)

Gambar (a)   BFS(1): 1, 2, 3, 4, 5, 6, 7, 8.

Gambar (b)   BFS(1): 1, 2, 3, 4, 5, 6, 7, 8

Gambar (c)   BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

• Pseudo-code algoritma:

• Diperlukan: 

1.   Matriks ketetanggaan A = [aij] yang berukuran n  n, 

aij = 1,  jika simpul i dan simpul j bertetangga,

aij = 0,   jika simpul i dan simpul j tidak bertetangga.

2.   Antrian q untuk menyimpan simpul yang telah dikunjungi. 

3.  Tabel boolean yang bernama dikunjungi 

 

 dikunjungi : array[l..n] of boolean

  

dikunjungi[i] = true jika simpul i sudah dikunjungi

dikunjungi[i] = false jika simpul i belum dikunjungi

Inisialisasi tabel:  

for il to n do

  dikunjungi[i] false

endfor

Metode Pencarian Mendalam (DFS)

Alur jalan algoritma DFS

1. Kunjungi simpul v.
2. Kunjungi simpul w yang bertetangga dengan simpul v.
3. Ulangi DFS mulai dari simpul w.
4. Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya  telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjung  sebelumnya dan mempunyai simpul w yang belum dikunjungi.
5. Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari  simpul yang telah dikunjungi.

Contoh 2:  (misalkan traversal dimulai dari simpul 1)

      (a) (b) (c)

       

Gambar (a)   DFS(1): 1, 2, 4, 8, 5, 6, 3, 7 

Gambar (b)   DFS(1): 1, 2, 3, 6, 8, 4, 5, 7 

Gambar (c)   DFS(1): 1, 2, 5, 8, 9, 6, 3, 7, 4

Baca juga Jasa Bimbingan Skripsi Teknik Informatika

Aplikasi DFS dan BFS

•  Search Engine (google, yahoo, altavista)

Komponen search engine:

1. Spider: program penjelajah web (web surfer)

2. Index:  basisdata yang menyimpan kata-kata penting pada  setiap halaman web

3.  Query: pencarian berdasarkan string yang dimasukkan oleh pengguna (end- user)

Secara periodik (setiap jam atau setiap hari), spider menjejalahi internet untuk mengunjungi halaman-halaman web, mengambil kata-kata penting di dalam web, dan menyimpannya di dalam index.

Query dilakukan terhadap index, bukan terhadap website yang aktual.

Demekian penjelasan singkat tentang algoritma travesal, semoga membantu untuk kebutuhan informasi anda.

Kata Kunci : Algoritma Pencarian Mendalam (DFS), Algoritma Pencarian Melebar (BFS),  Algoritma Traversal, Skripsi Teknik Informatika, Contoh Skripsi, Skripsi.