My first Magazine pemrograman-kompetitif-dasar | Page 111

9.6 Contoh Permasalahan Graf
1. Awalnya, seluruh node dianggap belum pernah dikunjungi.
2. Pilih salah satu node yang belum pernah dikunjungi, lalu lakukan penelusuran mulai dari
node tersebut. Seluruh node yang dilalui pada penelusuran ini dianggap telah dikunjungi.
3. Apabila masih ada node yang belum pernah dikunjungi, lakukan langkah ke-2. Apabila
seluruh node telah dikunjungi, laporkan banyaknya penelusuran graf yang dilakukan sebagai
jawaban dari persoalan ini.
Urutan pengunjungan node tidaklah penting, sehingga penelusuran graf yang digunakan
dapat berupa DFS atau BFS. Algoritma 47 menggunakan DFS yang diimplementasikan secara
rekursif sebagai penelusuran grafnya.
Algoritma 47 Solusi Persebaran Informasi menggunakan DFS.
1: visited ← new boolean[MAX_N]
2: procedure DFS(curNode)
visited[curNode] ← true
for ad jNode ∈ ad j(curNode) do
if not visited[ad jNode] then
DFS(ad jNode)
end if
end for
end procedure
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
function SOLVE ()
FILL A RRAY (visited, f alse)
result ← 0
for i ← 1, N do
if not visited[i] then
DFS(i)
result ← result + 1
end if
end for
return result
end function
. Fungsi utama yang mengembalikan jawaban soal
Permasalahan semacam ini biasa disebut dengan menghitung banyaknya komponen. Sebuah
komponen pada graf tidak berbobot merupakan sekumpulan node yang dapat saling mengunjungi
satu sama lain, tanpa ada node lain pada graf yang dapat dimasukkan pada kumpulan node ini.
Dalam sebuah graf, mungkin saja terdapat beberapa komponen.
II Sekilas Info JJ
Algoritma penelusuran graf untuk mengunjungi seluruh node pada suatu komponen umum-
nya disebut dengan flood fill . Secara harfiah, flood fill berarti "pengisian banjir". Nama
ini sesuai dengan jalannya algoritma yang seperti air banjir mengalir dari suatu node ke
node lainnya yang bertetangga. Pada Algoritma 47, flood fill ditunjukkan pada baris ke-2
sampai dengan baris ke-9.
101