Contoh Soal dan Jawaban BFS dan DFS: Menjelajahi Graf dengan Algoritma Pencarian

Pernahkah Anda terbayang bagaimana aplikasi navigasi menemukan rute tercepat dari lokasi Anda ke tujuan? Atau bagaimana mesin pencari menemukan halaman web yang relevan dengan kata kunci yang Anda masukkan? Di balik keajaiban teknologi tersebut, terdapat algoritma yang bekerja keras untuk mencari solusi optimal dalam data yang kompleks, salah satunya adalah Breadth-First Search (BFS) dan Depth-First Search (DFS). Contoh Soal dan Jawaban BFS dan DFS: Menjelajahi Graf dengan Algoritma Pencarian akan membantu Anda memahami konsep dasar kedua algoritma ini, cara kerjanya, dan bagaimana penerapannya dalam dunia nyata.

BFS dan DFS merupakan algoritma pencarian graf yang digunakan untuk menjelajahi semua simpul dalam sebuah graf. BFS menjelajahi graf secara berlapis, mulai dari simpul awal dan mengeksplorasi semua simpul yang berdekatan dengannya sebelum beralih ke lapisan berikutnya. Sementara DFS menjelajahi graf secara mendalam, menelusuri satu cabang sampai mencapai ujungnya sebelum kembali ke simpul sebelumnya dan menjelajahi cabang lain.

Pengertian BFS dan DFS

Dalam dunia ilmu komputer, khususnya dalam struktur data dan algoritma, kita seringkali berhadapan dengan graf. Graf adalah representasi visual dari hubungan antar objek, di mana objek disebut simpul (node) dan hubungan antar simpul disebut sisi (edge). Untuk menjelajahi graf ini, kita membutuhkan algoritma pencarian, dan dua algoritma yang paling populer adalah Breadth-First Search (BFS) dan Depth-First Search (DFS).

Breadth-First Search (BFS)

BFS merupakan algoritma pencarian graf yang bekerja dengan prinsip menjelajahi semua simpul pada level yang sama terlebih dahulu sebelum melanjutkan ke level berikutnya. Algoritma ini seperti melakukan penjelajahan secara “mendatar” atau “melebar”.

Depth-First Search (DFS)

DFS merupakan algoritma pencarian graf yang bekerja dengan prinsip menjelajahi satu jalur hingga mencapai simpul akhir, baru kemudian kembali ke simpul sebelumnya dan menjelajahi jalur lain. Algoritma ini seperti melakukan penjelajahan secara “menurun” atau “mendalam”.

Ilustrasi BFS dan DFS pada Graf Sederhana

Bayangkan sebuah graf sederhana dengan 5 simpul, yaitu A, B, C, D, dan E, yang dihubungkan dengan sisi sebagai berikut:

• A terhubung ke B dan C
• B terhubung ke D
• C terhubung ke E

Misalnya, kita ingin mencari simpul E dari simpul A. Berikut ilustrasi bagaimana BFS dan DFS bekerja:

BFS

BFS akan memulai pencarian dari simpul A. Pertama, BFS akan mengunjungi semua simpul yang terhubung langsung ke A, yaitu B dan C. Kemudian, BFS akan mengunjungi semua simpul yang terhubung langsung ke B dan C, yaitu D dan E. Algoritma ini akan berhenti ketika simpul E ditemukan.

DFS

DFS akan memulai pencarian dari simpul A. Pertama, DFS akan mengunjungi satu jalur dari A, misalnya A-B-D. Setelah mencapai simpul D, DFS akan kembali ke B dan melanjutkan ke jalur lain dari B, yaitu B-C-E. Algoritma ini akan berhenti ketika simpul E ditemukan.

Contoh Soal BFS

BFS (Breadth-First Search) merupakan algoritma pencarian graf yang bekerja dengan menelusuri semua simpul pada level yang sama sebelum melanjutkan ke level berikutnya. Algoritma ini sangat berguna untuk menemukan jalur terpendek dari simpul awal ke simpul tujuan dalam graf. Untuk memahami BFS, mari kita bahas contoh soal berikut.

Contoh Soal BFS

Perhatikan graf berikut yang memiliki 10 simpul dan 15 sisi. Titik awal adalah simpul A dan titik tujuan adalah simpul J.

Berikut tabel yang menunjukkan langkah-langkah BFS pada contoh soal tersebut.

Simpulu	Tetangga	Kunjungan	Jarak
A	B, C, D	Ya	0
B	A, E, F	Ya	1
C	A, G, H	Ya	1
D	A, I	Ya	1
E	B, J	Ya	2
F	B	Ya	2
G	C	Ya	2
H	C	Ya	2
I	D	Ya	2
J	E	Ya	3

Berdasarkan tabel di atas, kita dapat melihat bahwa simpul J ditemukan pada level 3, yang berarti jarak terpendek dari simpul A ke simpul J adalah 3.

Contoh Soal DFS

DFS (Depth-First Search) adalah algoritma pencarian graf yang menjelajahi semua simpul dalam graf dengan mendalami satu cabang secara penuh sebelum beralih ke cabang lainnya. Algoritma ini bekerja dengan menandai simpul yang telah dikunjungi dan menjelajahi tetangga dari simpul yang belum dikunjungi.

Contoh soal berikut ini akan mendemonstrasikan langkah-langkah DFS pada graf dengan 8 simpul dan 12 sisi.

Contoh Soal

Misalkan kita memiliki graf dengan 8 simpul (A, B, C, D, E, F, G, H) dan 12 sisi seperti pada gambar berikut:

Gambar Graf

Titik awal adalah simpul A dan tujuan adalah simpul H. Kita akan menggunakan algoritma DFS untuk menemukan jalur dari simpul A ke simpul H.

Langkah-langkah DFS

Simpulu	Tetangga	Kunjungan	Jarak
A	B, C, D	Ya	0
B	A, E, F	Ya	1
E	B, G	Ya	2
G	E, H	Ya	3
H	G	Ya	4
F	B, C	Ya	2
C	A, F	Ya	1
D	A	Ya	1

Langkah-langkah DFS pada contoh soal di atas adalah sebagai berikut:

1. Mulai dari simpul A sebagai titik awal. Simpul A ditandai sebagai telah dikunjungi dan jaraknya 0.
2. Jelajahi tetangga dari simpul A yaitu B, C, dan D. Simpul B ditandai sebagai telah dikunjungi dan jaraknya 1.
3. Jelajahi tetangga dari simpul B yaitu A, E, dan F. Simpul E ditandai sebagai telah dikunjungi dan jaraknya 2.
4. Jelajahi tetangga dari simpul E yaitu B dan G. Simpul G ditandai sebagai telah dikunjungi dan jaraknya 3.
5. Jelajahi tetangga dari simpul G yaitu E dan H. Simpul H ditandai sebagai telah dikunjungi dan jaraknya 4. Karena simpul H adalah simpul tujuan, maka pencarian selesai.
6. Kembali ke simpul G, karena semua tetangganya telah dikunjungi. Kembali ke simpul E, karena semua tetangganya telah dikunjungi. Kembali ke simpul B, karena semua tetangganya telah dikunjungi.
7. Jelajahi tetangga dari simpul B yaitu F. Simpul F ditandai sebagai telah dikunjungi dan jaraknya 2.
8. Jelajahi tetangga dari simpul F yaitu B dan C. Simpul C ditandai sebagai telah dikunjungi dan jaraknya 1.
9. Jelajahi tetangga dari simpul C yaitu A dan F. Semua tetangganya telah dikunjungi. Kembali ke simpul B.
10. Semua tetangga dari simpul B telah dikunjungi. Kembali ke simpul A.
11. Jelajahi tetangga dari simpul A yaitu D. Simpul D ditandai sebagai telah dikunjungi dan jaraknya 1.
12. Semua tetangga dari simpul A telah dikunjungi. Pencarian selesai.

Berdasarkan langkah-langkah DFS di atas, maka jalur dari simpul A ke simpul H adalah A – B – E – G – H dengan jarak 4.

Perbedaan BFS dan DFS

BFS (Breadth-First Search) dan DFS (Depth-First Search) adalah dua algoritma pencarian grafo yang umum digunakan dalam ilmu komputer. Kedua algoritma ini memiliki pendekatan yang berbeda dalam menjelajahi simpul-simpul dalam sebuah grafo. Perbedaan utama antara BFS dan DFS terletak pada urutan kunjungan simpul dan strategi pencarian yang digunakan.

Perbedaan BFS dan DFS

Tabel berikut merangkum perbedaan utama antara BFS dan DFS dalam hal prinsip pencarian, urutan kunjungan simpul, kegunaan, kompleksitas waktu, dan kompleksitas ruang.

BFS	DFS
Menjelajahi semua simpul pada level yang sama sebelum melanjutkan ke level berikutnya.	Menjelajahi satu cabang secara mendalam sebelum beralih ke cabang lainnya.
Mencari simpul terdekat dari simpul awal.	Mencari simpul yang berada jauh dari simpul awal.
Menemukan jalur terpendek dalam grafo.	Menemukan semua simpul yang terhubung dalam grafo.
O(V + E), di mana V adalah jumlah simpul dan E adalah jumlah edge.	O(V + E), di mana V adalah jumlah simpul dan E adalah jumlah edge.
O(V), di mana V adalah jumlah simpul.	O(V), di mana V adalah jumlah simpul.

Penerapan BFS dan DFS: Contoh Soal Dan Jawaban Bfs Dan Dfs

BFS (Breadth-First Search) dan DFS (Depth-First Search) adalah dua algoritma pencarian grafis yang sangat berguna dalam berbagai aplikasi praktis. BFS dan DFS membantu dalam menavigasi dan mengeksplorasi struktur data yang kompleks, seperti jaringan, pohon, dan grafik. Kedua algoritma ini memiliki pendekatan yang berbeda, yang memungkinkan mereka untuk unggul dalam skenario tertentu.

Pencarian Jalur Terpendek

BFS sangat efektif dalam menemukan jalur terpendek antara dua titik dalam suatu grafik. Misalnya, dalam aplikasi peta, BFS dapat digunakan untuk menemukan rute terpendek antara dua lokasi. Algoritma ini bekerja dengan menjelajahi semua simpul pada level yang sama sebelum melanjutkan ke level berikutnya. Ini memastikan bahwa jalur terpendek ditemukan pertama kali.

• Skenario: Aplikasi peta seperti Google Maps atau Waze.
• Penerapan: BFS digunakan untuk menemukan rute terpendek antara titik awal dan tujuan, dengan mempertimbangkan jalan, lalu lintas, dan hambatan lainnya.
• Bagaimana: BFS memulai pencarian dari titik awal dan menjelajahi semua simpul yang berdekatan dengannya. Kemudian, ia bergerak ke simpul yang berdekatan dengan simpul yang sudah dijelajahi, dan seterusnya. Proses ini berlanjut sampai tujuan ditemukan. Jalur yang diambil dari titik awal ke tujuan adalah jalur terpendek.

Pencarian Semua Jalur

DFS sangat berguna dalam menemukan semua jalur yang mungkin antara dua titik dalam suatu grafik. Misalnya, dalam permainan catur, DFS dapat digunakan untuk menemukan semua kemungkinan gerakan yang dapat dibuat oleh sebuah bidak.

• Skenario: Permainan catur atau teka-teki seperti Sudoku.
• Penerapan: DFS digunakan untuk menjelajahi semua kemungkinan gerakan atau solusi yang mungkin dalam permainan atau teka-teki.
• Bagaimana: DFS dimulai dari titik awal dan menjelajahi satu jalur sampai akhir, lalu kembali ke titik percabangan dan menjelajahi jalur lain. Proses ini berlanjut sampai semua jalur telah dijelajahi. DFS memungkinkan untuk menemukan semua solusi yang mungkin, bahkan jika beberapa solusi tidak optimal.

Pencarian Siklus dalam Grafik

DFS dapat digunakan untuk mendeteksi siklus dalam suatu grafik. Misalnya, dalam analisis jaringan sosial, DFS dapat digunakan untuk mendeteksi kelompok orang yang saling terhubung dengan erat. Jika DFS menemukan simpul yang sudah dikunjungi sebelumnya, maka ada siklus dalam grafik.

Mencari jalan terpendek dari titik A ke B dalam peta? Contoh soal dan jawaban BFS dan DFS bisa membantu! Konsepnya mirip dengan menentukan berapa banyak buah yang kamu punya, contohnya, “berapa banyak apel?” Nah, contoh soal much and many ini bisa membantu kamu memahami penggunaan ‘much’ dan ‘many’ dalam bahasa Inggris.

Kembali ke contoh soal BFS dan DFS, algoritma ini penting banget untuk memahami cara kerja program komputer dalam menemukan solusi optimal, lho!

• Skenario: Analisis jaringan sosial, deteksi kesalahan dalam kode program.
• Penerapan: DFS digunakan untuk menemukan siklus atau loop dalam jaringan sosial atau kode program. Siklus dalam jaringan sosial dapat menunjukkan kelompok orang yang saling terhubung dengan erat, sedangkan siklus dalam kode program dapat menunjukkan kesalahan atau perilaku yang tidak diinginkan.
• Bagaimana: DFS dimulai dari simpul awal dan menjelajahi semua simpul yang berdekatan dengannya. Jika DFS menemukan simpul yang sudah dikunjungi sebelumnya, maka ada siklus dalam grafik. Siklus diidentifikasi berdasarkan simpul yang dikunjungi sebelumnya dalam jalur pencarian saat ini.

Implementasi BFS

Algoritma Breadth-First Search (BFS) merupakan algoritma pencarian graf yang mengeksplorasi semua simpul pada level yang sama sebelum beralih ke level berikutnya. Algoritma ini menggunakan struktur data antrean untuk menyimpan simpul yang akan dikunjungi. Implementasi BFS dapat dilakukan dengan berbagai bahasa pemrograman, seperti Python. Berikut contoh implementasi BFS dalam bahasa Python:

Implementasi BFS dalam Python

Contoh kode BFS dalam Python menggunakan struktur data antrean (queue) untuk menyimpan simpul yang akan dikunjungi. Kode ini akan menampilkan urutan kunjungan simpul berdasarkan algoritma BFS.

# Fungsi untuk melakukan BFS
def bfs(graph, start):
  visited = set()  # Set untuk menyimpan simpul yang sudah dikunjungi
  queue = [start]  # Antrean untuk menyimpan simpul yang akan dikunjungi
  visited.add(start)  # Tandai simpul awal sebagai dikunjungi

  while queue:
    node = queue.pop(0)  # Ambil simpul dari depan antrean
    print(node, end=" ")  # Cetak simpul yang dikunjungi

    # Tambahkan tetangga yang belum dikunjungi ke antrean
    for neighbor in graph[node]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

# Contoh graf
graph = 
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']


# Panggil fungsi BFS dengan simpul awal 'A'
bfs(graph, 'A')

Berikut penjelasan dari kode tersebut:

• def bfs(graph, start):: Mendefinisikan fungsi bfs yang menerima graf dan simpul awal sebagai parameter.
• visited = set(): Membuat set visited untuk menyimpan simpul yang sudah dikunjungi.
• queue = [start]: Membuat antrean queue dan menambahkan simpul awal ke dalam antrean.
• visited.add(start): Menandai simpul awal sebagai dikunjungi.
• while queue:: Looping selama antrean tidak kosong.
• node = queue.pop(0): Mengambil simpul dari depan antrean dan menyimpannya dalam variabel node.
• print(node, end=" "): Mencetak simpul yang dikunjungi.
• for neighbor in graph[node]:: Looping untuk setiap tetangga dari simpul node.
• if neighbor not in visited:: Jika tetangga belum dikunjungi.
• visited.add(neighbor): Menandai tetangga sebagai dikunjungi.
• queue.append(neighbor): Menambahkan tetangga ke dalam antrean.
• graph = ... : Mendefinisikan graf dengan representasi adjacency list.
• bfs(graph, 'A'): Memanggil fungsi bfs dengan graf dan simpul awal ‘A’.

Kode ini akan menampilkan urutan kunjungan simpul berdasarkan algoritma BFS, yaitu: A B C D E F.

Implementasi DFS

Algoritma Depth-First Search (DFS) adalah algoritma pencarian graf yang bekerja dengan menjelajahi satu cabang dari graf secara menyeluruh sebelum beralih ke cabang lainnya. Implementasi DFS biasanya dilakukan dengan menggunakan rekursi atau stack.

Contoh Implementasi DFS dalam Python

Berikut adalah contoh implementasi algoritma DFS dalam bahasa pemrograman Python, menggunakan struktur data adjacency list untuk merepresentasikan graf:

def dfs(graph, start):
    visited = set() # Inisialisasi set untuk menyimpan node yang sudah dikunjungi
    stack = [start] # Inisialisasi stack dengan node awal
    
    while stack: # Selama stack tidak kosong
        node = stack.pop() # Ambil node teratas dari stack
        if node not in visited: # Jika node belum dikunjungi
            visited.add(node) # Tambahkan node ke set visited
            print(node) # Cetak node yang dikunjungi
            
            # Tambahkan tetangga node ke stack
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

# Contoh graf yang direpresentasikan dalam bentuk adjacency list
graph = 
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []


# Panggil fungsi DFS dengan node awal 'A'
dfs(graph, 'A')

Kode di atas menunjukkan implementasi DFS yang menggunakan stack. Berikut penjelasan kode tersebut:

• def dfs(graph, start):: Mendefinisikan fungsi dfs yang menerima graf dan node awal sebagai input.
• visited = set(): Inisialisasi set untuk menyimpan node yang sudah dikunjungi.
• stack = [start]: Inisialisasi stack dengan node awal.
• while stack:: Looping selama stack tidak kosong.
• node = stack.pop(): Mengambil node teratas dari stack.
• if node not in visited:: Memeriksa apakah node sudah dikunjungi. Jika belum, maka:
• visited.add(node): Menambahkan node ke set visited.
• print(node): Mencetak node yang dikunjungi.
• for neighbor in graph[node]:: Melooping melalui tetangga dari node.
• if neighbor not in visited:: Memeriksa apakah tetangga sudah dikunjungi. Jika belum, maka:
• stack.append(neighbor): Menambahkan tetangga ke stack.

Contoh Soal BFS dengan Constraint

Breadth-First Search (BFS) merupakan algoritma pencarian graf yang mengeksplorasi semua simpul pada tingkat yang sama sebelum berpindah ke tingkat berikutnya. Dalam penerapannya, BFS dapat dikombinasikan dengan batasan atau constraint untuk mengoptimalkan pencarian dan mendapatkan solusi yang diinginkan. Contohnya, kita dapat membatasi jumlah kunjungan simpul maksimal untuk mengontrol kompleksitas pencarian.

Contoh Soal BFS dengan Constraint

Berikut contoh soal BFS dengan constraint:

Diberikan graf dengan 12 simpul (A, B, C, D, E, F, G, H, I, J, K, L) dan 18 sisi, dengan titik awal A dan tujuan L. Batasan jumlah kunjungan simpul maksimal adalah 5. Tentukan jalur terpendek dari A ke L dengan constraint tersebut.

Simpulu	Tetangga	Kunjungan	Jarak
A	B, C, D	1	0
B	E, F	2	1
C	G, H	3	1
D	I, J	4	1
E	K	5	2

Berdasarkan tabel di atas, pencarian BFS terhenti pada simpul E karena jumlah kunjungan simpul maksimal sudah tercapai (5). Simpulu E memiliki tetangga K, tetapi tidak dikunjungi karena batasan jumlah kunjungan simpul. Jalur terpendek dari A ke L dengan constraint tersebut tidak ditemukan, karena simpul L tidak dapat dijangkau dalam batasan kunjungan simpul maksimal.

Contoh Soal DFS dengan Constraint

Depth-First Search (DFS) merupakan algoritma pencarian graf yang mengeksplorasi setiap cabang dari suatu simpul sebelum berpindah ke cabang lain. DFS memiliki kemampuan untuk mencari solusi dalam graf dengan batasan kedalaman pencarian, yang memungkinkan untuk membatasi jumlah simpul yang dikunjungi. Berikut ini adalah contoh soal DFS dengan constraint.

Contoh Soal DFS dengan Constraint

Perhatikan graf berikut yang memiliki 10 simpul dan 15 sisi:

Gambar 1: Graf dengan 10 simpul dan 15 sisi

Tentukan jalur terpendek dari simpul A ke simpul J dengan batasan kedalaman pencarian maksimal 3.

Langkah-langkah DFS dengan Constraint

Berikut ini adalah langkah-langkah DFS dengan constraint untuk menemukan jalur terpendek dari simpul A ke simpul J dengan batasan kedalaman pencarian maksimal 3:

Simpulu	Tetangga	Kunjungan	Jarak
A	B, C, D	Ya	0
B	A, E, F	Ya	1
E	B, G, H	Ya	2
G	E, I, J	Ya	3
J	G	Ya	4

Dari tabel di atas, kita dapat melihat bahwa jalur terpendek dari simpul A ke simpul J adalah A – B – E – G – J dengan jarak 4. Karena batasan kedalaman pencarian maksimal 3, kita tidak dapat melanjutkan pencarian lebih lanjut. Meskipun simpul I juga merupakan tetangga dari simpul G, kita tidak dapat mengunjunginya karena kedalaman pencarian sudah mencapai batas maksimal 3.

Keuntungan dan Kerugian BFS dan DFS

BFS (Breadth-First Search) dan DFS (Depth-First Search) adalah dua algoritma pencarian grafis yang umum digunakan. Masing-masing memiliki keuntungan dan kerugiannya sendiri, tergantung pada jenis masalah yang ingin diselesaikan. Mari kita bahas lebih detail tentang keduanya.

Perbandingan Keuntungan dan Kerugian BFS dan DFS, Contoh soal dan jawaban bfs dan dfs

Berikut tabel yang meringkas keuntungan dan kerugian BFS dan DFS dalam berbagai skenario:

BFS	DFS
Keuntungan: Menemukan jalur terpendek dari simpul awal ke simpul tujuan (jika ada) Cocok untuk pencarian ruang negara yang luas dan bercabang Menemukan semua simpul yang terhubung ke simpul awal	Keuntungan: Membutuhkan memori lebih sedikit dibandingkan BFS Cocok untuk menemukan solusi yang dalam, seperti dalam teka-teki atau permainan Mudah diimplementasikan
Kerugian: Membutuhkan banyak memori, terutama untuk grafik yang besar Tidak efisien untuk mencari solusi yang dalam Tidak cocok untuk grafik yang memiliki banyak cabang	Kerugian: Tidak menjamin jalur terpendek Bisa terjebak dalam siklus tak terbatas Tidak cocok untuk pencarian ruang negara yang luas dan bercabang

Ringkasan Terakhir

BFS dan DFS merupakan alat yang kuat untuk memecahkan berbagai masalah terkait graf. Dengan memahami konsep dasar dan contoh soal BFS dan DFS, Anda dapat mengaplikasikannya dalam berbagai bidang seperti pengembangan game, jaringan komputer, dan bahkan analisis data. Dengan terus mempelajari dan mempraktikkan algoritma ini, Anda akan semakin memahami cara kerja dunia komputasi dan membangun solusi yang lebih efisien dan efektif.