Algoritma BFS dan DFS

Depth First Search

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman.proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan ke node-node yang selevel.Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.

Contoh DFS Pohon Biner

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L


Contoh DFS Representasi Array

Contoh Implementasi Bahasa C

Breadth First Search

BFS (Breadth First Search)merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun bedanya BFS melakukan pencarian secara melebar atau per level pohon. Simpul ditelusuri dari root kemudian menelusuri semua simpul pada setiap level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ), maka penelusuran dilakukan terus dari simpul paling kiri ke simpul anak – anak tetangganya yang selevel.

Kegunaan BFS

• Memeriksa apakah Graph terhubung
• Menghitung spanning Forest Graph
• Menghitung tiap vertex dalam graph,jalur dengan jumlah edge minimum antara vertex awal dan current vertex atau ketiadaan path
• menghitung cycle dalam graph atau ketiadaan cycle

Contoh BFS pada Matrix 9x9

Contoh BFS pohon Biner Huruf

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L

Contoh Pencarian Secara Grafikal

Contoh Implementasi dalam bahasa C