Analisis Perbandingan Penelusuran secara Depth First Search pada Graf dengan Algoritma Rekursif dan Non-Rekursif

Abstrak Analisis Perbandingan Penelusuran secara Depth First Search pada Graf dengan Algoritma Rekursif dan Non-Rekursif

DFS (Depth First Search) merupakan metode penelusuran graf dengan cara memprioritaskan kedalaman terlebih dahulu. Penyelesaian ini dapat dilakukan dengan algoritma rekursif dan non-rekursif. Jika menggunakan algoritma non rekursif, maka masalah penelusuran DFS dapat diselesaikan dengan memakai bantuan tumpukan (Stack). Sedangkan jika menggunakan algoritma rekursif, maka dapat diselesaikan dengan cara memanggil algoritma itu sendiri. Makalah ini berisi analisa perbandingan penyelesaian masalah metode penelusuran DFS pada graf dengan algoritma rekursif dan algoritma non-rekursif. Perbandingannya dititikberatkan pada kompleksitas kedua algoritma tersebut. Kata kunci: DFS, algoritma, graf, rekursif , non-rekursif, stack

Pendahuluan Analisis Perbandingan Penelusuran secara Depth First Search pada Graf dengan Algoritma Rekursif dan Non-Rekursif

Graf adalah himpunan simpul yang dihubungkan dengan busur-busur. Setiap busur diasosiasikan dengan tepat dua simpul. Dalam kehidupan seharihari banyak sekali persoalan yang diimplementasikan dengan graf. Bidang-bidang yang menggunakan penerapan graf antara lain Switching network, Coding theory, Electrical analysis, Operation research, Aljabar, Computer science, dan Kimia. Graf merupakan model matematika yang sangat kompleks dan rumit, tapi bisa juga menjadi solusi yang sangat bagus terhadap suatu kasus tertentu. Maka dari itu representasi suatu graf bergantung dari sifat data dan operasi yang dilakukan terhadap data dari sebuah kasus tertentu. Representasi graf dalam bahasa pemrograman dapat dilakukan dengan memakai array atau memakai linked list. Kedua representasi tersebut mempunyai keunggulan masing-masing. Jika kita memakai representasi array, kita dapat melakukan manipulasi dan penyimpanan lebih mudah daripada memakai linked list karena dengan array, kita tidak perlu memikirkan kerumitan pointer. Jika kita memakai representasi linked list, kita lebih fleksibel dalam jumlah data yang kita pakai daripada memakai representasi array karena dengan array, jumlah datanya terbatas. Ada banyak operasi yang bisa dilakukan pada graf antara lain : operasi pembentukan graf ( misalnya : penyisipan simpul dan busur ) , operasi untuk mengirimkan besaran graf ( misalnya : penghitungan derajat graf, penghitungan jumlah simpul dan busur dari suatu graf), operasi penelusuran graf ( misalnya : penelusuran secara DFS dan BFS )., penentuan jalur terpendek, pembuatan minimum spanning tree ( pohon merentang minimum ), dan sebagainya. Dalam makalah ini kami akan membahas salah satu operasi pada graph yaitu penelusuran graf secara DFS dan pada makalah ini, kami memakai representasi graf dengan array.

Analisis Perbandingan Penelusuran secara Depth First Search pada Graf dengan Algoritma Rekursif dan Non-Rekursif

| Download File Lengkapnya... |

Like Skripsi Ini :