Modul 5 [BFS dan DFS]

Breadth-First Search (BFS) dan Depth-First Search (DFS)

Breadth-First Search

Pada BFS, penelusuran node pada graf dilakukan lapis demi lapis. Semakin dekat suatu node dengan node awal, node tersebut akan dikunjungi terlebih dahulu.

Penjelasan Gambar:

Sebuah graf dan urutan pengunjungan node -nya secara BFS. Angka pada node menunjukkan urutan node tersebut dikunjungi. Node 1 dikunjungi pertama, node 2 dikunjungi kedua, dan seterusnya). Daerah yang dibatasi garis putus-putus menyatakan daerah yang mana setiap node memiliki jarak yang sama kepada node yang dikunjungi pertama. Edge yang dicetak tebal menyatakan edge yang dilalui oleh penelusuran secara BFS.

Dalam pemrograman C++, BFS biasa diimplementasikan dengan STL queue, dimana queue akan menyimpan daftar node yang akan dikunjungi. Tahap setiap node ditambahkan ke dalam queue adalah:

1. BFS akan mengunjungi satu node terlebih dahulu
2. node yang sedang dikunjungi akan dihapus dari queue
3. dari node tersebut akan dimasukan tetangga-tetangga node yang belum dikunjungi
4. Lakukan terus sampai tidak ditemukan node yang belum dikunjungi

Pseudocode BFS

void BFS(int s){
	queue<int> bfs;
	visited[s] = 1; //menandai node pertama sebagai telah dikunjungi
	bfs.push(s);

	while(!bfs.empty()){
		int cur = bfs.top();
		cout << cur << ' ';
		bfs.pop(); //menghapus node yang sedang dikunjungi dari dalam queue
				
		for(i = 0; i < adj[cur].size(); i++){
			if(!visited[adj[cur][i]]){
				visited[adj[cur][i]] = 1;  //menandai node yang akan dikunjungi
				bfs.push(adj[cur][i]);  //memasukan node yang akan dikunjungi ke dalam queue
			}
		}
	}
}

Depth-First Search

Pada DFS, penelusuran node pada graf dilakukan dengan cara mengunjungi node secara rekursif (mengunjungi nodes tetangga yang belum dikunjungi) dan backtracking (mundur jika tidak ada nodes tetangga yang belum dikunjungi). Untuk lebih sederhananya adalah DFS akan bergerak maju terus, sampai pada saat tidak ada tetangga yang belum dikunjungi, maka akan mundur sekali untuk mencari nodes tetangga yang belum dikunjungi. DFS akan melakukan hal tersebut sampai semua nodes telah dikunjungi.

Penjelasan Gambar:

Proses DFS ini dilakukan ke graf satu arah, dengan jalur antara nodes yang tebal akan dilalui oleh program dan yang putus-putus tidak dilalui program.

Disini DFS menggunakan rekursi fungsi dalam menjalankan programmnya, dimana setiap fungsi akan mempresentasikan setiap node yang akan mencoba mengunjungi node lain lalu jika node tersebut belum pernah dikunjungi maka fungsi node yang belum dikunjungi dijalankan.

Pseudocode

void DFS(int cur){
	cout << cur << ' ';

	for(i = 0; i < adj[cur].size(); i++){
		if(!visited[adj[cur][i]]){
			visited[adj[cur][i]] = 1;  //menandai node yang akan dikunjungi
			DFS(adj[cur][i]);  //memasukan node yang akan dikunjungi ke dalam queue
		}
	}
}

void DFS_init(int s){
	visited[s] = 1;  //menandai node pertama sebagai telah dikunjungi
	DFS(s);
}

Referensi

• PEMROGRAMAN KOMPETITIF DASAR oleh Wiliam Gozali & Alham Fikri Aji
• Introduction to Alogrithms Second Edition oleh Thomas. H. Cormen dkk.
• [drive](https://drive.google.com/file/d/1-i_7k_QRzjJnSd5L-mj8jj6WPIPM4Seh/view?usp=share_link)