Perbandingan Algoritma Penelusuran Depth First Search dan Breadth First Search pada Graf serta Aplikasinya

Perbandingan Algoritma Penelusuran Depth First Search dan Breadth First Search pada Graf serta Aplikasinya Hafid Inggiantowi - 13507094 Program Studi Teknik Informatika , Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung, Bandung , e-mail : [email protected]

Abstrak – Dalam matematika dan sains komputer, teori graf adalah studi graf, dimana graf adalah struktur matematika yang digunakan untuk memodelkan hubungan antara objek-objek. Graf dalam cakupan ini adalah sekumpulan simpul dan sekumpulan sisi yang menghubungkannya. Dalam hubungannya dengan aplikasi graf, terdapat suatu algoritma yang dapat menelusuri dan mencari pada graf. Makalah ini membahas metode penelusuran pada graf, yaitu Depth First Search dan Breadth First Search, serta menjelaskan perbandingannya. Depth First Search merupakan metode penelusuran graf dengan cara memprioritaskan kedalaman terlebih dahulu, sedangkan Breadth First Search mencari dengan memulai dari simpul akar dan menelusuri semua tetangga dari simpul tersebut. Setelah membandingkan kedua algoritma tersebut, dapat kita lihat bahwa algoritma ini juga memiliki banyak aplikasi dan banyak digunakan dalam masalahmasalah yang berhubungan dengan graf. Kata Kunci: graf, pohon, Depth First Search, Breadth First Search, algoritma penelusuran pada graf, perbandingan Depth First Search dan Breadth First Search, aplikasi Depth First Search dan Breadth First Search. 1. PENDAHULUAN Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf, dimana permasalahan jembatan Königsberg tersebut menuntut suatu pemodelan dalam suatu graf. Suatu graf direpresentasi secara grafik dengan menggambar titik untuk setiap simpul, dan menggambar garis antara dua simpul apabila mereka dihubungkan oleh suatu sisi. Graf tentunya memiliki banyak jenis. Suatu graf khusus yang disebut pohon juga merupakan salah satu contoh jenis dari graf. Dengan struktur data apapun, algoritma umum yang akan ditulis untuk pertama kali adalah suatu algorima yang menelusuri struktur datanya, atau istilah lainnya, algoritma traversal. Untuk graf, terdapat dua metode standar traversal untuk menelusuri graf itu sendiri, yaitu Depth First Search dan Breadth First Search. Dan nampaknya, dua traversal ini, umumnya Depth First Search lebih banyak, dapat dimanfaatkan dan

digunakan untuk menyelesaikan variasi masalah pada graf ketika menelusuri graf itu sendiri. 2. TEORI GRAF Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. 2.1 Sejarah Graf Masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf.

Gambar 2.1 : Jembatan Königsberg

Tujuh buah jembatan menghubungkan daratan yang dibelah oleh sungai Pregal, di kota Königsberg (lihat gambar 2.1). Masalah jembatan Königsberg yang tidak dapat dijelaskan jawabannya adalah persoalan mengenai ketidakmungkinan untuk melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula. Tidak ada yang dapat menjelaskannya kecuali dengan cara coba-coba sampai ketika pada tahun 1736, seorang matematikawan Swiss L.Euler memodelkan masalah ini pada suatu graf (lihat gambar 2.2). C

A

D

B

Gambar 2.2 : Model graf Jembatan Königsberg

Menurut Euler, orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap. Derajat disini adalah banyaknya garis yang bersisian dengan noktah (titik).

1

2.2 Definisi Graf Secara matematis, graf didefinisikan sebagai berikut : Graf G didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini : V = himpunan tidak kosong dari simpul-simpul (vertices atau node) = {v1, v2, …, vn } dan E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = { e1, e2, …, en } Sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi minimal simpulnya harus ada satu. Oleh karena itu, V tidak boleh kosong, sedangkan E boleh kosong.

2.4.2 Terhubung (Connected) Graf disebut terhubung apabila ada lintasan antara tiap pasang simpul. Komponen terhubung graf G adalah subgraf dari G terhubung maksimal.

Gambar 2.6 : Graf terhubung

2. 5 Definisi Pohon Terdapat suatu graf khusus yang disebut sebagai pohon (tree). Definisi pohon adalah sebagai berikut Pohon adalah graf tak berarah terhubung yang tidak mengandung sirkuit

Gambar 2.3 : Contoh suatu graf

2.3 Jenis- Jenis Graf Graf tentunya memiliki banyak sekali jenis. Graf dapat dikelompokkan menjadi beberapa kategori sesuai sudut pandang pengelompokannya. Apabila berdasarkan orientasi arah pada sisi, secara umum graf dibedakan atas dua jenis : 1. Graf tak berarah Graf yang sisinya tidak mempunyai orientasi arah 2. Graf berarah Graf yang setiap sisinya diberikan orientasi arah. 2.4 Definisi-Definisi Penting pada Graf 2.4.1 Subgraf (Subgraph) Subgraf atau upagraf S dari graf G adalah graf yang bersifat :  Simpul S adalah subset simpul dari G  Sisi S adalah subset sisi dari G.

Gambar 2.4 : Subgraf

Gambar 2.7 : Contoh suatu pohon, dengan 6 simpul & 5 sisi

Pohon adalah graf tak berarah G yang memiliki kondisi-kondisi sebagai berikut :  G terhubung dan tidak mengandung sirkuit (cycle)  G tidak memiliki sirkuit, dan sirkuit akan terbentuk jika ada penambahan sisi  G terhubung, dan dan tidak akan terhubung lagi bila ada sisi yang dihapus dari G  G terhubung dan tidak mengandung graf lengkap 3-sisi K3  Dua simpul apapun pada G dapat terhubung oleh lintasan unik sederhana. Jika G memiliki banyak simpul, berjumlah n, maka  G terhubung dan memiliki n -1 sisi  G tidak memiliki sirkuit dan memiliki n -1 sisi.

Subgraf merentang G (spanning subgraf) adalah subgraf yang berisi semua simpul dari G.

Graf tak berarah G disebut hutan (forest) apabila ia tidak memiliki sirkuit sederhana. Komponen terhubung dari hutan adalah pohon.

Gambar 2.5 : Subgraf merentang

Gambar 2.8 : Pohon dan Hutan

2

Pohon merentang (spanning tree) dari graf terhubung adalah subgraf merentang yang merupakan pohon. Pohon merentang tidak unik, kecuali graf adalah pohon. Pohon merentang diaplikasikan dalam desain jaringan komunikasi. Pohon merentang dari graf adalah subgraf merentang yang merupakan hutan.



 

Gambar 2.9 : Pohon merentang

3. TRAVERSAL GRAF  Satu hal menarik pada teori graf adalah traversal graf. Banyak algoritma menarik pada graf yang didasarkan dari ide iterasi yang berjalan melewati simpul-simpul pada graf sesuai urutan yang berhubungan dengan struktur graf.

Traversal DFS dari suatu graf G akan : o Mengunjungi semua simpul dan sisi dari G o Menentukan apakah G terhubung o Memperhitungkan komponen terhubung dari G o Memperhitungkan pohon merentang dari G DFS pada graf dengan n simpul dan m sisi membutuhkan waktu O(n + m ) DFS dapat lebih jauh diperluas untuk menyelesaikan masalah-masalah pada graf o Menemukan dan melaporkan lintasan antara dua simpul yang diberikan o Menemukan sirkuit pada graf Depth First Search untuk menggambar graf Euler ke pohon biner

Berikut terdapat suatu pohon pencarian.

Ada dua traversal graf yang fundamental, yang diketahui sebagai Breadth First Search dan Depth First Search. Breadth First Search (BFS) dan Depth First Search (DFS) adalah dua traversal berbeda yang berjalan mengunjungi simpul dan sisi pada graf. BFS bermula dari suatu akar dan akan mengunjungi simpul tujuan dengan urutan bergantung pada jarak mereka dari akar. Tentu akibatnya, simpul terdekat akan dikunjungi terlebih dahulu. Sedangkan, DFS lebih memilih untuk mengunjungi langsung, simpul yang belum ditemukan, sehingga pohon pencarian (search tree) hasil traversal akan lebih dalam, dibandingkan dengan BFS, yang akan lebih seimbang. DFS mengandung tiga lintasan Hamiltonian, satu di setiap komponen – dan sebaliknya, pohon BFS, lebih jauh, memiliki simpul 3 derajat yang merefleksikan keseimbangan. 3.1 Depth First Search Depth first search (DFS) adalah algoritma umum traversal atau pencarian pada pohon, struktur pohon, atau graf. DFS adalah pencarian yang berjalan dengan meluaskan anak akar pertama dari pohon pencarian yang dipilih dan berjalan dalam dan lebih dalam lagi sampai simpul tujuan ditemukan, atau sampai menemukan simpul yang tidak punya anak. Kemudian, pencarian backtracking, akan kembali ke simpul yang belum selesai ditelusuri. Dalam implementasi nonrekursif , semua simpul yang diluaskan ditambahkan ke LIFO stack untuk penelusuran. Beberapa hal mengenai traversal DFS :

Gambar 3.1 : Pohon pencarian (search tree)

Pada graf yang kita miliki di atas (Gambar 3.1), hubungan antara lintasan tidak dua arah. Semua lintasan hanya berjalan dari atas ke bawah. Dengan kata lain, A memiliki lintasan ke B dan C, tapi B dan C tidak memiliki lintasan ke A. Jadi, secara umum bisa kita anggap seperti jalan satu arah (one way street). Setiap lingkaran yang berhuruf pada graf di atas adalah simpul. Setiap simpul dapat dihubungkan dengan simpul yang lain dengan sisi atau suatu lintasan, dan simpul yang langsung berhubungan dengan simpul disebut tetangga. B dan C adalah tetangga dari A. Kemudian, E dan D adalah tetangga dari B, dan B bukan tetangga dari D atau E karena B tidak bisa dicapai menggunakan D atau E. Berikut ini akan dijelaskan demonstrasi yang dapat membantu kita memahami cara kerja Depth First Search. Misalkan kita ingin mencari lintasan antara simpul A dan F pada graf yang telah kita punyai di atas (gambar 3.1). Depth First Search telah kita ketahui, bekerja dengan memilih suatu simpul, kemudian akan memeriksa tetangga-tetangganya, meluaskan dengan simpul pertama yang ditemui pada tetangga-tetangganya, kemudian memeriksa apakah simpul hasil perluasan adalah tujuannya atau bukan, dan jika bukan, akan

3

melanjutkan menelusuri simpul yang lebih banyak lagi. Langkah Awal: Dimulai dari simpul akar, atau simpul tujuan yang kita pilih, yaitu A Gambar 3.2: Langkah Awal

Kita akan menggunakan dua list info untuk menyimpan langkah yang kita lakukan, yaitu Open dan Close. Open akan menyimpan langkah yang perlu kita lakukan, dan Close akan menyimpan langkah yang telah kita lakukan. Saat ini, kita hanya punya titik awal yang kita pilih, yaitu simpul A. Kita belum melakukan apapun ke simpul tersebut, sehingga sekarang kita tambahkan ke Open. Open : A Close : < kosong >

Close: A, B Langkah 3 : Kita akan melihat bahwa sebuah pola mulai terbentuk. Karena D ada di awal dari Open, maka kita meluaskannya. D bukan tujuan kita, dan tidak berisi satu pun tetangga. Selanjutnya, kita dapat menghapus D dari Open dan menambahkanya ke Close. Open: E, C Close: A, B, D Langkah 4: Sekarang kita meluaskan simpul E dari Open. E bukan tujuan kita, sehingga kita telusuri tetanggatetangganya dan menemukan bahwa ia memiliki tetangga F dan G. Karena F adalah tujuan kita, kita masih belum berhenti di sini tentunya. Di samping F berada pada lintasan kita, kita hanya akan berhenti begitu kita akan meluaskan simpul tujuan kita, dalam kasus ini yaitu F :

Langkah 1 Sekarang, kita memeriksa tetangga- tetangga dari simpul A. Dengan kata lain, mengambil simpul awal dari Open kita dan kemudian menelusuri tetanggatetangganya. Gambar 3.5 : Langkah 4 Gambar 3.3 :Langkah 1

Tetangga-tetangga dari simpul A adalah simpul B dan C. Karena sekarang kita telah selesai dengan simpul A, kita dapat menghapusnya dari Open dan menambahkannya ke Close. Kita belum selesai dengan langkah ini tentunya. Tambahkan dua simpul B dan C tadi ke Open.

Kita akan menghapus simpul E dari Open dan menambahkan simpul F dan G ke dalamnya. Kemudian, simpul E ditambahkan ke Close: Open: F, G, C Close: A, B, D, E Langkah 5 Sekarang kita meluaskan simpul F. Karena F adalah tujuan kita, maka kita berhenti :

Sekarang, Open dan Close berisi data sebagai berikut : Open : B, C Close: A Langkah 2 Open kini berisi dua simpul. Untuk depth first search dan breadth first search, selalu kita telusuri simpul pertama dari Open. Simpul pertama pada open sekarang adalah simpul B. B bukan tujuan kita, sehingga kita telusuri tetangga-tetangganya.

Gambar 3.4 : Langkah 2

Karena kini B telah diluaskan, kita dapat menghapusnya dari Open dan menambahkannya ke Close. Kini, simpul baru kita adalah D dan E, dan kita tambahkan simpul ini ke awal dari Open (menggantikan B yang telah dihapus). Open: D, E, C


Kita menghapus F dari Open dan menambahkannya ke Close. Karena kita telah sampai di tujuan, maka tidak perlu lagi meluaskan F dan mencari tetangganya. Open dan Close akhir kita akan berisi data sebagai berikut : Open: G, C Close: A, B, D, E, F Lintasan akhir yang akan diambil oleh metode Depth First Search kita adalah nilai terakhir dari Close, yaitu : A, B, D, E, F. 3.2 Breadth First Search Dalam teori graf, breadth first search (BFS) juga merupakan teknik umum dalam traversal graf. Algoritma pencarian grafnya dimulai dari simpul akar

4

yang kemudian menelusuri semua simpul tetangganya. Kemudian, untuk setiap simpul yang terdekat itu, ditelusuri simpul tetangga yang belum diperiksa, dan demikian seterusnya, sampai ditemukan simpul tujuan. BFS adalah metode pencarian yang bertujuan memperluas dan memeriksa semua simpul pada graf. BFS merupakan kombinasi dari tiap urutan langkah yang secara sistematik mencari tiap solusi. Dengan kata lain, BFS secara penuh mencoba mencari pada keseluruhan graf dengan urutan langkah yang tidak memikirkan tujuan sampai akhirnya menemukan tujuan itu sendiri. BFS tidak menggunakan heuristik. Dari sudut algoritma, semua simpul anak yang didapat dengan memperluas simpul ditambahkan ke FIFO queue. Pada implementasi khasnya, simpul yang belum diperiksa tetangganya diletakkan pada suatu container ( misal queue atau list terhubung) yang disebut Open dan sekali lagi diperiksa dan diletakkan pada container Close. Beberapa hal mengenai traversal BFS :  Traversal BFS dari suatu graf G akan : o Mengunjungi semua simpul dan sisi dari G o Menentukan apakah G terhubung o Memperhitungkan komponen terhubung dari G o Memperhitungkan pohon merentang dari G.  DFS pada graf dengan n simpul dan m sisi membutuhkan waktu O(n + m )  DFS dapat lebih jauh diperluas untuk menyelesaikan masalah-masalah pada graf o Menemukan dan melaporkan lintasan dengan angka minimum dari sisi antara dua simpul yang diberikan o Menemukan sirkuit sederhana pada graf, jika ada. Metode Breadth first search hampir serupa dengan Depth first search. Pada Depth first search, simpul yang paling baru ditelusuri ditambahkan ke awal dari Open. Pada Breadth first search, simpul terbaru yang ditelusuri ditambahkan ke akhir dari Open. Berikut adalah demonstrasi yang dapat membantu kita memahami cara kerja Breadth First Search. Misalkan kita ingin mencari lintasan antara simpul A dan E pada pohon pencarian yang telah kita gunakan untuk demonstrasi depth first search di atas (gambar 3.1). Langkah Awal: Dimulai dari simpul akar, atau simpul tujuan yang kita pilih, yaitu A Gambar 3.7 : Langkah Awal

Sama dengan sebelumnya, kita akan menggunakan dua list info untuk menyimpan langkah yang kita lakukan, yaitu Open dan Close. Sekarang, tambahkan A ke Open. Open : A Close : < kosong > Langkah 1 Sekarang, kita memeriksa tetangga- tetangga dari simpul A. Sampai sini, dengan sama, kita mengikuti langkah depth first.


Kita menghapus A dari Open dan menambahkannya ke Close. Tetangga A, simpul B dan C, ditambahkan ke Open. Kemudian, B dan C ditambahkan ke akhir dari Open. Open dan Close akan berisi data sebagai berikut. Open : B, C Close : A Langkah 2 Pada langkah inilah, mulai jauh terlihat berbeda dari metode depth first search yang telah kita lakukan. Kini, kita melihat pada simpul B karena muncul pertama kali pada Open. Karena B bukan tujuan kita, kita menelusuri tetangganya.


B kini dipindah ke Close, tapi tetangga dari B, simpul D dan E ditambahkan ke akhir dari Open. Open : C, D , E Close : A, B Langkah 3 Sekarang kita meluaskan simpul C :


Karena C tidak memiliki tetangga, yang kita lakukan adalah menghapus C dari Open dan maju lagi : Open : D, E Close : A, B, C Langkah 4 Serupa dengan langkah 3, kita meluaskan simpul D. Karena bukan tujuan kita, dan juga tidak memiliki tetangga, kita hapus D dari Open, lalu menambahkannya ke Close, dan lanjut lagi :

5

Open : E Close : A, B, C, D

b. Cek dan lihat apakah simpul yang dihapus adalah tujuan kita i. if -- Jika simpul yang dihapus adalah tujuan kita, keluar dari loop, tambahkan simpul ke Close, dan kembali ke nilai dari Close kita. ii. else -- Jika simpul yang dihapus bukan tujuan kita, lanjutkan loop (ke Langkah C)

Langkah 5 Karena Open kita hanya memiliki satu simpul, kita tak punya pilihan selalin melihat pada simpul E. Karena E adalah tujuan kita, maka kita dapat berhenti di sini :


c. Ekstrak tetangga dari simpul yang dihapus di atas d. Tambahkan tetangga ke akhir dari Open, dan tambahkan simpul yang dihapus ke Close.

Open dan Close akhir kita akan berisi data sebagai berikut : Open: < kosong > Close: A, B, C, D, E

3.3.3 Sintaks Flash Depth First Search (AS) Berikut adalah konversi pseudocode Depth First Search yang telah dijelaskan ke Action Script menggunakan metode dari ADT Graf :

Berjalan dari A ke E akan melalui lintasan B, C, dan D bila menggunakan breadth first search.

searchMethod = function () { var origin:Node = nodeOrigin; var destination:Node = nodeDestination; // Creating our Open and Closed Lists var closedList:Array = new Array(); var openList:Array = new Array(); // Adding our starting point to Open List openList.push(origin);

3.3 Algoritma Depth First Search dan Breadth First Search 3.3.1 Pseudocode Depth First Search Algoritma Depth First Search secara pseudocode untuk apa yang telah kita lakukan pada demonstrasi depth first search di atas dapat dijelaskan sebagai berikut.

// Loop while openList contains some data. while (openList.length != 0) { // Loop while openList contains some data. var n:Node = Node(openList.shift()); // Check if node is Destination if (n == destination) { closedList.push(destination); trace("Closed!"); break; }

i. Mendeklarasikan dua list kosong : Open dan Close ii. Menambahkan simpul awal ke Open iii. While do a. Hapus simpul awal dari Open b. Cek dan lihat apakah simpul yang dihapus adalah tujuan kita i. if -- Jika simpul yang dihapus adalah tujuan kita, keluar dari loop, tambahkan simpul ke Close, dan kembali ke nilai dari Close kita. ii. else -- Jika simpul yang dihapus bukan tujuan kita, lanjutkan loop (ke Langkah C) c. Ekstrak tetangga dari simpul yang dihapus di atas d. Tambahkan tetangga ke awal dari Open, dan tambahkan simpul yang dihapus ke Close. Lanjutkan looping. 3.3.2 Pseudocode Breadth First Search Berdasarkan pada demonstrasi Breadth First Search yang telah kita lakukan, pseudocode untuk Breadth First Search serupa dengan pseudocode Depth First Search di atas, dan dapat dijelaskan sebagai berikut. i. Mendeklarasikan dua list kosong : Open dan Close ii. Menambahkan simpul awal ke Open iii. While do a. Hapus simpul awal dari Open

// Store n's neighbors in array var neighbors:Array = n.getNeighbors(); var nLength:Number = neighbors.length; // Add each neighbor to the beginning of our openList for (i=0; i< nLength; i++) { openList.unshift(neighbors[nLength - i - 1]); } // Add current node to closedList closedList.push(n); } };

3.3.4 Sintaks Flash Breadth First Search (AS) Dan berikut, adalah versi Action Script(AS) dari Breadth First Search: searchMethod = function () { var origin:Node = nodeOrigin; var destination:Node = nodeDestination; // Creating our Open and Closed Lists var closedList:Array = new Array(); var openList:Array = new Array(); // Adding our starting point to Open List openList.push(origin); // Loop while openList contains some data. while (openList.length != 0) { // Loop while openList contains some data. var n:Node = Node(openList.shift());

6

// Check if node is Destination if (n == destination) { closedList.push(destination); trace("Closed!"); break; } // Store n's neighbors in array var neighbors:Array = n.getNeighbors(); var nLength:Number = neighbors.length; // Add each neighbor to the end of our openList for (i=0; i
3.4 Aplikasi Algoritma Depth First Search dan Breadth First Search Secara lebih lanjut, masing-masing dari algoritma penelusuran graf yang telah kita bahas memiliki aplikasi yang lebih kompleks dan memiliki kegunaan dalam permasalahan kehidupan sehari-hari. Berikut ini akan dibahas beberapa aplikasinya. 3.4.1. Layout Gambar Web Suatu Web adalah resource tersebar (sangat besar) yang memanfaatkan graf berarah yang simpulnya adalah dokumen dan sisi adalah hubungan antara mereka (link). Web dapat berisi gambar, yang berguna, direpresentasi dengan Weblet sebagai hirarki pohon, yang memiliki banyak sirkuit. Hiperbolik geometri menawarkan pendekatan sistematik, elegan, dan dapat digunakan untuk memvisualisasikan graf berarah berisi sirkuit. Graf berarah dapat ditancapkan pada ruang hiperbolik

3.4.2 Gambar Satelit Algoritma lintasan terpendek graf sangat penting pada pemrosesan dari gambar satelit. Bayangkan satelit mengambil foto dari jalanan kota, algoritma graf dapat mengidentifikasi jalan tersebut. GPS dapat mengambil gambar tersebut dan menemukan lintasan terpendek dari satu tempat ke tempat lain, alat tersebut harus bisa menjalankan algoritma pencarian graf pada gambar, yang akan mencari lintasan terpendek. Alat ini dapat menjalankan algoritma breadth first search. Algoritma ini dapat mulai dari titik sumber dan secara sistematik mencari sisi ke setiap simpul yang bisa diraih. Algoritma ini mengiterasi proses yang sama di setiap simpul yang bisa diraih ke simpul yang bisa diraih berikutnya. Untuk menyimpan simpul, digunakan FIFO Queue. FIFO menyimpan simpul yang dapat diraih pada queue.

Gambar 3.13 : Breadth First pada gambar Satelit 3.4.3 Maze Algoritma Depth First Search merupakan strategi klasik untuk menelusuri suatu maze  Tandai tiap persimpangan, pojokan, dan jalan buntu (simpul) yang dikunjungi  Tandai tiap koridor (sisi) yang ditelusuri.  Simpan lintasan kembali ke pintu masuk (simpul awal)

Subpohon yang dibutuhkan dapat dipilih menggunakan traversal. Pilihan traversal menentukan komprehensibilitas gambar. Breadth first search yang dimulai dari simpul akar akan menghasilkan gambar yang lebih bersih, lebih seimbang dibanding depth first search. Dapat dilihat pada gambar berikut, layout gambar Weblet dari indeks kota Jerman yang terhubung kuat dengan masing-masing traversal.

Gambar 3.14 : Maze sederhana

Dan tentunya masih banyak lagi aplikasi lain dapat dijelaskan yang memanfaatkan kedua algoritma ini. 4. PERBANDINGAN DEPTH FIRST SEARCH DAN BREADTH FIRST SEARCH

Gambar 3.12 : (a) Breadth first

(b)Depth first search

Telah dijelaskan pada demonstrasi di atas, cara kerja masing-masing algoritma, baik DFS maupun BFS. Perbedaan cara kerja pada DFS dan BFS adalah, DFS berprioritas pada kedalaman, memulai dari simpul akar dan berjalan semakin dalam sampai simpul tujuan ditemukan, sedangkan BFS, dimulai dari akar, akan lebih memilih untuk memeriksa semua tetangga dari

7

simpul tersebut, kemudian dicek satu-satu mulai dari simpul terdekatnya, seterusnya, sampai menemukan tujuan. Berikut ini pada gambar 4.1 dapat dilihat perbedaan urutan langkah masing-masing algoritma.

Gambar 4.1 Urutan jalan algoritma,Kiri : DFS, Kanan : BFS

Kedua algoritma ini berjalan dengan waktu yang proporsional dengan sisi-sisi pada graf. Kompleksitas waktu DFS dan BFS proporsional dengan jumlah simpul ditambah jumlah sisi pada graf yang ditelusuri (O(|V| + |E|)). Kompleksitas ruang DFS lebih rendah dari BFS. Kompleksitas ruang tersebut memberikan DFS metode heuristik yang lebih baik dalam memilih cabang yang mungkin nampak pada jalannya. Kompleksitas ruang DFS adalah O(h) dimana h adalah panjang dari lintasan sederhana terpanjang pada graf, sedangkan kompleksitas ruang BFS adalah O( | V | + | E | ). Terdapat pencarian postorder pada Depth first search, yang memeriksa banyak simpul dan mendapatkan banyak informasi. Breadth first search tidak memiliki hal ini, karena ia tidak mempunyai rekursifitas. Hal ini menyebabkan aplikasi dari DFS lebih banyak dibandingkan BFS. Depth first dan breadth first search keduanya memiliki keuntungan, yang lebih baik bergantung pada masalahnya. Untuk pohon pencarian , depth first search membutuhkan memori lebih sedikit. Namun, depth first search dapat terjebak dalam penelusuran yang lama. Depth first bagus ketika ada banyak kemungkinan solusi, dan kita hanya menginginkan satu saja (tidak peduli yang mana itu). Breadth first search mungkin membutuhkan lebih banyak memori, tapi tidak akan pernah terjebak, akan selalu menemukan lintasan terpendek yang pertama. Kemangkusan algoritma pencarian keduanya akan bergantung pada masalah yang ingin dipecahkan, dan ruang pencariannya. BFS biasa direpresentasi dengan Queue, sedangkan DFS dengan Stack. Algoritma DFS tidak optimal, sedangkan BFS optimal untuk graf tak berbobot. Kedua algorima ini membentuk pohon merentang yang sangat berguna pada algoritma graf yang lain. DFS dan BFS dalam aplikasinya dapat mencari hutan merentang, komponen terhubung, lintasan, dan sirkuit. Sedangkan untuk masing-masingnya, BFS dapat mencari lintasan terpendek, dan DFS dapat mencari komponen terhubung biconnected. Biconnected berarti graf tak dapat dipisah, maksudnya jika ada simpul

yang akan dihapus, graf akan tetap terhubung. 5. KESIMPULAN Kesimpulan yang dapat diambil dari pembahasan makalah ini adalah : 1. Pada teori graf, terdapat algoritma standar yang praktis dan umum untuk penelusuran (traversal) pada graf, yaitu Depth First Search dan Breadth First Search, implementasinya cukup sederhana, namun walaupun sederhana, banyak digunakan dalam menyelesaikan masalah-masalah pada graf 2. Depth First Search dan Breadth First Search memiliki langkah algoritma yang berbeda, namun dalam implementasinya, kedua algoritma ini saling berhubungan, dan memiliki kemiripan 3. Depth First Search dan Breadth First Search digunakan dalam berbagai banyak aplikasi, dan salah satunya merupakan permasalahan dalam kehidupan sehari-hari. Contohnya, penggunaan Depth First Search dalam menemukan solusi dari Maze 4. Depth First Search dan Breadth First Search memiliki kelebihan dan kekurangan masingmasing, tergantung pada masalah graf yang ingin dipecahkan kedua algoritma tersebut. DAFTAR REFERENSI [1] Breadth First Search/Depth First Search Animations. http://www.cs.sunysb.edu/~skiena/ combinatorica/ animations/search.html. Tanggal Akses : 31 Desember 2008 [2] Breadth-first search. http://en.wikipedia.org/wiki/ Breadth-first_search. Tanggal Akses : 31 Desember 2008 [3] Cycles. http://www.geom.uiuc.edu/docs/research/ webviz/webviz/node4.html . Tanggal Akses : 1 Januari 2008 [4] Depth-First Search. http://en.wikipedia.org/wiki/ Depth-first_search. Tanggal Akses : 31 Desember 2008 [5] Depth first vs Breadth first Search. http://www.macs.hw.ac.uk/~alison/ai3notes/paragrap h2_6_2_1_0_1.html . Tanggal Akses : 31 Desember 2008 [6] Depth First and Breadth First Search by kirupa. http://www.kirupa.com/developer/actionscript/depth_ breadth_search.htm .Tanggal Akses : 31 Desember 2008 [7] Goodrich, Tamassia. Breadth-First Search.

8

http://ww0.java4.datastructures.net/handouts/BFS.pdf . Tanggal Akses : 31 Desember 2008 [8] Goodrich, Tamassia. Depth-First Search. http://ww0.java4.datastructures.net/handouts/DFS.pdf . Tanggal Akses : 31 Desember 2008 [9] Graph traversal. Depth and Breadth First Search. http://www.mec.ac.in/resources/notes/notes/ds/gratra. htm. Tanggal Akses : 31 Desember 2008 [10] ICS 161: Design and Analysis of Algorithms. Breadth first search and depth first search. http://www.ics.uci.edu/~eppstein/161/960215.html. Tanggal Akses : 1 Januari 2008 [11] Munir, Rinaldi. 2008. Diktat Kuliah IF2091 Struktur Diskrit. Program Studi Teknik Informatika Institut Teknologi Bandung [12] Tree (graph theory). http://en.wikipedia.org/wiki /Tree_(graph_theory). Tanggal Akses : 31 Desember 2008 [13] Wharris, James. Implementing Graph Algorithms for Satellite Images. www.jameswharris.com/ . Tanggal Akses : 1 Januari 2008

9

Perbandingan Algoritma Penelusuran Depth First Search dan Breadth First Search pada Graf serta Aplikasinya

Recommend Documents