1

ANALISIS ALGORITMA II

MINIMUM SPANNING TREE

ALGORITMA PRIM

OLEH :

SITI DESY AWALIA (115100071)

EVA CELIA RAHARJO (115100038)

JUNI ASTUTI N. (115100033)

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS TEKNOLOGI INDUSTRI

INSTITUT TEKNOLOGI INDONESIA

Institut Teknologi Indonesia

1

BAB 1

A.PendahuluanI.1 Latar Belakang

Graf merupakan suatu metode untuk mencari solusi dari permasalahan diskret yang di temui dalam kehidupan sehari-hari. Untuk mencari solusi ini, di dalam graf terdapat banyak konsep. Salah satu konsep yang sering dipakai adalah konsep pohon (tree). Konsep pohon adalah kosep yang paling penting dan popular, karena konsep pohon mampu mendukung aplikasi graf dalam berbagai bidang ilmu. Aplikasi ilmu yang menggunakan konsep pohon diantaranya: pembagunan jalan dan rel kereta api, pembuatan jaringan komputer, pencarian jalur untuk penjual keliling.

Pohon adalah suatu graf terhubung yang tidak berarah dan tidak memuat siklus. Sirklus adalah lintasan yang berawal dan berakhir pada simpul yang sama. Jika G adalah graf berbobot, maka bobot dari pohon pembangkit T dari G didefinisikan sebagai jumlah bobot pada semua sisi di T. Pohon pembangkit yang berbeda memiliki bobot yangberbeda pula. Di antara pohon pembangkit di G, pohon yang memiliki bobot paling minimum dinamakan pohon pembangkit minimum. Pohon ini merupakan pohonpembangkit yang paling penting.

Terdapat beberapa algoritma untuk membangun pohon pembangkit minimum, salah satunya adalah menggunakan Algoritma Prim. Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari pohon pembangkit minimum untuk sebuah graf terhubung berbobot. Dengan kata lain sebuah himpunan bagian dari cabang-cabang yang membentuk suatu pohon yang terdiri dari semua simpul, di mana bobot keseluruhan semua cabang dalam pohon adalah paling kecil. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon pembangkit minimum untuk satu dari komponen yang terhubung.

I.2 TujuanTujuan dari dibuatnya makalah ini adalah Untuk memahami konsep dari algoritma prim Untuk menyelesaikan tugas analisis Algoritma II yang diberikan oleh

dosen kami

Institut Teknologi Indonesia

1

BAB 2

B.Pembahasan2.1 Rumusan Masalah

Rumusan masalah dalam makalah ini adalah untuk menjelaskan dan mengimplementasikan Algoritma Prim untuk menentukan Minimum Spanning Tree (MST) dengam menggunakan algoritma prim. Contoh :

Gambar dibawah ini adalah graf terhubung berbobot awal. Graf ini bukan pohon karena ada siklus. Nama yang lebih tepat untuk diagram ini adalah graf atau jaringan. Angka-angka dekat garis penghubung adalah bobotnya. Maka carilah pohon pembangkit minimum dari graf pada gambar dibawah ini

2.2 Pembahasan MasalahLangkah langkah dalam menentukan Minimum Spanning Tree (MST) dengam

menggunakan algoritma prim

Langkah pertama: pilih salah satu simpul secara sebarang, misal simpul D, maka simpul tersebut beri warna hijau untuk menandakan bahwa simpul tersebut sudah terpilih menjadi anggota dari pohon.

Institut Teknologi Indonesia

1

Langkah ke-2: Setelah dipilih titik D, selanjutnya pilih garis yang terhubung pada simpul D dengan bobot terkecil. Garis-garis tersebut dengan bobotnya adalah {D,A} = 5, {D,B} = 7, {D,E} = 15, dan {D,F} = 6. Dari keempatnya, 5 adalah bobot yang terkecil, jadi garis yang dipilih adalah garis DA, kemudian diberi warna hijau untuk menandai bawa garis tersebut sudah terpilih.

Pohon yang telah dihasilkan memiliki 1 ruas garis DA dengan simpul A dan D.Langkah ke-3: Garis berikutnya yang dipilih adalah yang terhubung dengan D atau A. {A,B} = 7, {D,B} = 9, {D,E} = 15 dan {D,F}= 6 6 adalah bobot yang terkecil, jadi kita pilih ruas garis DF kemudian beri warna hijau.

Langkah ke-4: Algoritma ini berlanjut seperti di atas. Garis {A,B} = 7 merupakan salah satu dari banyak garis yang terhubung dengan simpul A, D atau F yang memiliki bobot terkecil. Maka ruas garis AB yang dipilih kemudian beri warnahijau.

Di sini, ruas garis yang terhubung dengansimpul A, D atau F adalah {B,C} = 8, {B,D}= 9, {B,E} = 7, {D,E} = 15, {F,E} = 8 dan {F,G} =11.Ruas garis BD jangan dipilih, karena akanmenghasilkan siklus.Ruas garis BE yang dipilih, karena memilikibobot terkecil (7), kemudian beri warna hijau.

Ruas garis yang terhubung dengan simpul, B, E atau F adalah {B,C} = 8, {E,C} =5, {D,E} = 15,{E,F} = 8, {E,G} = 9, dan {F,G} = 11Ruas garis DE dan EF jangan dipilih karenaakan menghasilkan siklus, maka ruas garis yang dapat dipilih adalah BC, EC, EG, dan FG.Karena EC memiliki bobot terkecil yaitu 5maka garis EC lah yang dipilih.

Institut Teknologi Indonesia

1

Simpul G adalah satu-satunya yang tersisa.Maka dengan mudah cari ruas garis yangterhubung dengan simpul G dan tidakmembentuk siklus dan memiliki bobot terkecil.Ruas garis {E,G} = 9, dan {F,G} = 11, makakita pilih ruas garis EG.

Sekarang semua simpul telah terhubung, danpohon pembangkit minimum ditunjukkandengan warna hijau, sehingga bobotnya = 6 + 5 + 7 + 7 + 5 + 9 = 39.

Dengan struktur data binary heap sederhana, algoritma Prim dapat ditunjukkan berjalan dalam waktu O(Elog V), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan Fibonacci heap, hal ini dapat ditekan menjadi O(E + Vlog V), yang jauh lebih cepat bila grafnya cukup padat sehingga E adalah Ω(Vlog V).

Konsep dasar yang digunakan dalam algoritma Prim adalah dalam setiap langkah, pilih sisi dari graf G yang berbobot minimum, yang terhubung dengan pohon merentang T yang telah terbentuk, dan tidak membentuk sirkuit.

Langkah-langkah algoritma Prim :1. Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T.2. Pilih sisi (u,v) yang mempunyai bobot minimum dan bersisian dengan T, tetapi

(u,v) tidak membentuk sirkuit di T. Tambahkan (u,v) ke dalam T.3. Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu setelah

mengalami pengulangan sebanyak n-2 kali (n adalah jumlah simpul graf G).

Institut Teknologi Indonesia

1

Penulisan algoritma Prim dalam bentuk notasi algoritmik (pseudocode)

Institut Teknologi Indonesia

1

BAB 3

C.Penutup

3.1 Kesimpulan

Algoritma Prim merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan yang berhubungan dengan graf dengan membangun graf menjadi pohon merentang minimum. Algoritma Prim termasuk algoritma Greedy karena pada satu langkah algoritm Prim akan mencari hasil yang paling optimal sehingga dikatakan algoritma Prim selalu memenuhi locl optimal tetapi belum tentu menghasilkan global optimal. Algoritma Prim pasti menghasilkan pohon merentang minimum meskipun tidak selalu unik. Sisi graf yang dimasukkan untuk menjadi kandidat sisi pohon merentang minimum adalah sisi yang bersisian dengan simpul sebelumnya.

3.2 Penutup

Demikianlah makalah yang telah Kami buat. Semoga makalah ini dapat berguna untuk Kami sebagai pembuat maupun untuk semua orang yang membacanya.

3.3 Daftar Pustaka

Cormen et al, 2001, Introduction to Algorithms : second edition, MIT

Institut Teknologi Indonesia