ANALISA DAN PERANCANGAN APLIKASI GRAPH DENGAN MENGGUNAKAN METODE DEPTH FIRST SEARCH

Abstract

Algoritma depth first search (dfs) merupakan salah satu algoritma pencarian yang menggunakan struktur data saat mencapai suatu simpul atau vertex yang terhubung dalam suatu graph. Kemampuannya yaitu bisa menyelesaikan pencarian spanning cycle pada graph dalam menemukan simpul-simpul yang belum dikunjungi memudahkan pencarian solusi minimum. Dalam tulisan ini dibahas tentang implementasi suatu program sederhana dan menganalisis penggunaan algoritma depth first search (dfs) yang bertujuan untuk memperoleh solusi minimum pada graph. Dalam menentukan spanning cycle pada suatu graph dapat direpresentasikan dalam perencanaan perjalanan yang menghubungkan beberapa sasaran atau lokasi. Jumlah spanning cycle yang mungkin terjadi tergantung dari banyaknya vertex dan juga edge yang digunakan untuk menghubungkan setiap vertex dalam menggambarkan graph. Semakin banyak jumlah vertex pada suatu graph maka akan semakin banyak pula edge yang akan menghubungkan vertex-vertex tersebut dan secara otomatis akan menambah jalur-jalur yang akan dilalui atau semakin banyak pula spanning cycle yang akan terbentuk. Metode ini memudahkan pengguna (user) melihat atau menampilkan setiap spanning cycle dari suatu graph, pengguna (user) dapat melakukan visualisasi dari setiap spanning cycle yang terbentuk dengan cara memilih dan mengklik salah satu lintasan spanning cycle yang ingin ditampilkan. Perubahan warna edge menunjukkan gambar visualisasi dari sebuah spanning cycle yang dipilih oleh pengguna.