MATERI KULIAH 04 September 2026 1 menit baca 4

Struktur Data & Algoritma: Breadth First Search (BFS) dan Depth First Search (DFS)

Materi ini membahas teknik penjelajahan graf (traversal) untuk mengunjungi seluruh simpul (vertex) melalui dua pendekatan fundamental: Breadth First Search (BFS) dan Depth First Search (DFS). BFS bekerja secara melebar mengunjungi simpul-simpul yang sederajat terlebih dahulu menggunakan struktur antrean (Queue) berprinsip FIFO.

## Konsep Traversal pada Graf

Dalam teori graf, *traversal* merupakan proses sistematis untuk mengunjungi setiap simpul (*vertex*) tepat satu kali di dalam suatu graf. Penjelajahan graf memerlukan mekanisme pencatatan status simpul agar algoritma tidak terjebak dalam perulangan siklik (*infinite loop*). Dua metode utama yang paling banyak digunakan adalah:

- **Breadth First Search (BFS)**: Penelusuran secara melebar yang memprioritaskan kunjungan ke simpul-simpul yang sederajat atau bertetangga langsung sebelum melangkah ke tingkat berikutnya.
- **Depth First Search (DFS)**: Penelusuran secara mendalam yang menelusuri simpul ke cabang terdalam hingga mencapai simpul buntu, kemudian melakukan penelusuran balik (*backtracking*).

## Mekanisme Breadth First Search (BFS)

Algoritma BFS mengutamakan eksplorasi melebar level demi level. Implementasi BFS menggunakan struktur data **Queue** (antrean) yang beroperasi dengan prinsip First In, First Out (FIFO).

Tahapan alur kerja BFS meliputi:

1. Menyiapkan antrean dalam keadaan kosong serta mengosongkan himpunan hasil.
2. Memasukkan simpul awal ke dalam antrean dan memberi status "telah dikunjungi".
3. Selama antrean masih memiliki elemen:
   - Mengeluarkan simpul terdepan (*Front*) dari antrean dan memasukkannya ke dalam urutan hasil traversal.
   - Memeriksa semua simpul tetangga dari simpul tersebut yang belum dikunjungi.
   - Memasukkan tetangga yang belum dikunjungi ke antrean sisi belakang (*Rear*) serta menandainya sebagai "telah dikunjungi".
4. Proses berakhir ketika antrean kosong dan seluruh simpul yang terhubung telah terdata.

Pada graf percontohan dengan simpul awal **A**, BFS berturut-turut mengeksplorasi tetangga terdekat level 1 yaitu **B** dan **C**, berlanjut ke simpul level 2 yaitu **D**, **E**, **F**, dan **G**, disusul level 3 yakni **H** dan **I**, hingga berakhir di simpul terdalam **J**. Urutan akhir yang dihasilkan adalah:

$$\text{Hasil DFS} = \text{A} \rightarrow \text{C} \rightarrow \text{G} \rightarrow \text{I} \rightarrow \text{J} \rightarrow \text{H} \rightarrow \text{E} \rightarrow \text{D} \rightarrow \text{F} \rightarrow \text{B}$$

## Perbandingan BFS dan DFS

Pemilihan antara BFS dan DFS bergantung pada struktur permasalahan dan karakteristik data yang dihadapi:

## Kesimpulan

Breadth First Search (BFS) dan Depth First Search (DFS) merupakan dua strategi fundamental dalam penjelajahan graf yang saling melengkapi. BFS dengan pendekatan FIFO menjamin penelusuran simpul sederajat terlebih dahulu dan sangat efektif untuk menemukan jalur terpendek pada graf tanpa bobot. Di sisi lain, DFS dengan karakteristik LIFO bergerak cepat menuju simpul terdalam, menjadikannya solusi ideal untuk mendeteksi siklus maupun penelusuran labirin secara efisien.

#universitas siber asia #struktur data #stack #queue #graph #informatika #LIFO #vertex #traversal #graf #breadth first search #bfs #depth first search #dfs #fifo

Komentar (0)

Belum ada komentar. Jadi yang pertama berkomentar di bawah.

Struktur Data & Algoritma: Breadth First Search (BFS) dan Depth First Search (DFS)

Komentar (0)

Tulis Komentar

Artikel Terkait

Estetika Humanisme: Psikologi Humanistik

Estetika Humanisme: Leadership

Estetika Humanisme: Manajemen Konflik