Rabu, 18 Desember 2019
Jumat, 13 Desember 2019
Kamis, 12 Desember 2019
Senin, 14 Oktober 2019
Minggu, 09 Juni 2019
GRAF DAN POHON DALAM PEMROGRAMAN C++
[
Tugas Kuliah ] Algoritma dan Pemrograman 2 | Graf dan Pohon
Tugas
TI POLITALA Alpro 2C
Nama :
Prima Angelia Rehulina Barus
Kelas :
2C
Jurusan :
Teknik Informatika
NIM :
1801301109
Matkul :
Alpro 2 Tugas 4
Semester :
II
GRAF
DAN POHON
Pada pembahasan
kali ini, saya akan menjelaskan tentang materi graf dan pohon khususnya materi graf
dan pohon dengan algoritma djikstra dan kruskal. Materi ini berdasarkan hasil
diskusi kelompok dengan kasus rumah makan terdekat di Pelaihari dengan
algoritma djikstra dan kruskal.
A.
Pengertian Graf
Sebuah
graf G didefinisikan sebagai pasangan himpunan (V,E) , dengan V adalah himpunan
tak kosong yang terdiri dari simpul-simpul (vertices) atau titik pada G.
Sedangkan E adalah himpunan rusuk (edge) atau sisi pada G yang menghubungkan
sepasang simpul atau titik. Himpunan simpul atau titik pada G dinotasikan
sebagai V, dan himpunan rusuk atau sisi pada G dinotasikan sebagai E. Jadi
G=(V, E)
Berdasarkan ada tidaknya gelang atau sisi ganda pada
suatu graph, maka graph digolongkan menjadi dua jenis:
1.
Graph sederhana (simple graph).
Graf yang tidak mempunyai
gelang atau loop maupun sisi ganda.
2.
Graph tak-sederhana (unsimple-graph).
Graf yang
mempunyai gelang atau loop maupun sisi ganda.
Berdasarkan
jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan
menjadi dua jenis:
1. Graph
berhingga (limited graph)
2. Graph
tak-berhingga (unlimited graph)
Berdasarkan orientasi arah
pada sisi, maka secara umum graph
dibedakan atas 2 jenis:
1. Graph
tak-berarah (undirected graph)
Graph yang sisinya tidak
mempunyai orientasi arah atau panah disebut graph tak-berarah.
2. Graph
berarah (directed graph atau digraph)
Graph yang setiap sisinya
diberikan orientasi arah atau panah disebut sebagai graph berarah.
Algoritma Graf
Algoritma Graf yang
dibahas dalam laporan ini ada 2 yaitu :
a)
Algoritma Dijkstra (Pencarian Jalur Terpendek)
Algoritma
ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari
satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis
menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasiatau total terhadap semua kemungkinan bobot terkecil dari
setiap titik yang dilalui.
Pertama-tama
tentukan titik mana yang akan menjadi node awal, lalu beri
bobot jarak pada node pertama ke node terdekat
satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke
titik lain dan ke titik selanjutnya tahap demi tahap. Inilah urutan logika dari
algoritma Dijkstra:
1. Beri
nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal
dan nilai tak hingga terhadap node lain (belum terisi).
2. Set
semua node “Belum terjamah” dan set node awal
sebagai “Node keberangkatan”.
3.Dari node keberangkatan,
pertimbangkan node tetangga yang belum terjamah dan hitung
jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A
ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2,
maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak
sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data
jarak dengan jarak yang baru.
4. Saat kita
selesai mempertimbangkan setiap jarak terhadap node tetangga,
tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah
tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan
yang paling minimal bobotnya.
5. Set “Node belum
terjamah” dengan jarak terkecil (dari node keberangkatan)
sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan
kembali ke step 3.
2. Algoritma
Kruskal
Algoritma
Kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum
tree untuk sebuah graf berbobot yang terhubung. Jika grafik tidak terhubung,
maka menemukan hutan rentang minimum (pohon rentan minimum untuk setiap
komponen terhubung). Dasar pembentukan algoritma Kruskal berasal dari analogi
glowing forest. Glowing forest maksudnya adalah untuk membentuk pohon merentang
minimum T dari graf G adalah dengan cara mengambil satu persatu sisi dari graf
G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring
dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon
yang semakain sedikit. Algoritma Kruskal akan terus menambah sisi-sisi kedalam
hutan yang sesuai hingga akhirnya tidak akan ada lagi forest, melainkan hanyalah
sebuah pohon yang merentang minimum.
Secara umum
Algoritma Kruskal ditulis:
1.
T
masih kosong
2.
Pilih
sisi (i, j) dengan bobot minimum
3.
Pilih
sisi (i, j) dengan bobot minimum yang berikutnya yang tidak membentuk cycle di
T, tambahkan (i,j) ke T
4.
Ulangi
langkah 3 sebanyak (n-2) kali
5.
Total
langkah (n-1) kali
Karakteristik dari Algoritma Kruskal :
a.Sifat dari Algoritma Kruskal
1. Bekerja tidak hanya dengan grafik
diarahkan.
2. Bekerja dengan bobot dan tidak grafik
tertimbang. Tapi yang lebih menarik, apabila tepi yang berbobot.
3. Kruskal adalah jenis algoritma yang
menghasilkan solusi optimal MST.
Langkah-Langkah Algoritma Kruskal
Langkah-langkah algoritma Kruskal adalah
sebagai berikut:
1. Atur tepi berat: pling berat pertama
dan terberat terakhir.
2. Pilih yang ringan tidak diperiksa tapi
dari diagram.
3. Tambahkan tepi memilih ini ke pohon,
hanya jika hal itu tidak membuat siklus.
4. Menghentikan proses kapanpun n-1 tapi
lebih ditambahkan kepohon.
B.
Pengertian Pohon
Pohon (tree) adalah merupakan
graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. pohon
adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :
~ Graph tersebut
tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).
~ Graph tersebut
terhubung .
Hutan ( forest )
merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan
graf tidak terhubung yang tidak mengandung sirkuit.
Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf
dengan n buah simpul dan tepat n – 1 buah sisi.
2. Jika G tidak mempunyai sirkuit
maka G merupakan pohon.
3. Suatu pohon dengan n buah simpul mempunyai
n – 1 buah sisi.
4. Setiap pasang simpul di dalam
suatu pohon terhubung dengan lintasan tunggal.
5. Misalkan G adalah graf sederhana
dengan jumlah simpul n,jika G tidak mengandung sirkuit maka penambahan satu
sisi pada graf hanya akan membuat satu sirkuit.
C.
Permasalahan
Permasalahan yang
terdapat pada laporan ini adalah sebagai berikut:
1.
Membuat sebuah pembahasan tentang graf dan
pohon serta algoritma djikstra dan kruskal.
2.
Membuat sebuah program mencari jalur
terpendek antar rumah makan terdekat di Pelaihari menggunakan algoritma
djikstra dan kruskal.
D. Penjelasan
Kasus
Kasus
yang diambil dalam laporan ini adalah kasus rumah makan terdekat di pelaihari.
Disini diambil beberapa rumah makan ada sekitar 10 rumah makan. Dari 10 rumah
makan tersebut diukur jaraknya di google map untuk memuat grafnya. Setelah itu
dibuat jarak satu persatu rumah makan untuk membuat matriks berbobotnya.
a) Map
b) Graf
Djikstra dan Kruskal
c) Matriks
Djikstra
d) Matriks
Kruskal
e) Codingan
Algoritma Djikstra
Hasil
Running Djikstra
f) Codingan
Algoritma Kruskal
Hasil
Running Kruskal
Sekian penjelasan
dari saya tentang materi graf dan pohon khususnya materi graf dan pohon dengan
algoritma djikstra dan kruskal. Semoga bermanfaat.
Daftar pustaka
Rifanti, Marina Utti. 2017. “PEMILIHAN RUTE TERBAIK
MENGGUNAKAN ALGORITMA DIJKSTRA UNTUK MENGURANGI KEMACETAN LALU LINTAS DI
PURWOKERTO (BEST ROUTE SELECTION USE DIJKSTRA ALGORITHM TO REDUCE TRAFFIC
CONGESTION IN PURWOKERTO)”. Diakses pada tanggal 25 Mei 2019 pukul 09.30 WITA
dari https://www.researchgate.net/publication/325059321_Pemilihan_Rute_Terbaik_Menggunakan_Algoritma_Dijkstra_Untuk_Mengurangi_Kemacetan_Lalu_Lintas_di_Purwokerto/download
Amrullah. 2018. “APLIKASI GRAF POHON PADA ALGORITMA
HUFFMAN”. Diakses pada tanggal 25 Mei 2019 pukul 10.45 WITA dari
https://www.researchgate.net/publication/322423546
Sabtu, 08 Juni 2019
SORTING DALAM PEMROGRAMAN C++
[
Tugas Kuliah ] Algoritma dan Pemrograman 2 | Sorting – Bubble Sort
Tugas
TI POLITALA Alpro 2C
Nama :
Prima Angelia Rehulina Barus
Kelas :
2C
Jurusan :
Teknik Informatika
NIM :
1801301109
Matkul :
Alpro 2 Tugas 3
Semester :
II
SORTING
Pada pembahasan
kali ini, saya akan menjelaskan tentang materi sorting khususnya materi sorting
dengan algoritma bubble sort dan quick sort.
Pengertian Sorting
(pengurutan)
Sorting yaitu suatu aktivitas untuk
mengurutkan suatu data yang belum terurut misalnya mengurutkan data-data dari
nilai yang terkecil ke terbesar ataupun sebaliknya.
Ada 6 jenis metode
sorting, yaitu;
1. Bubble
sort
2. Insertion
sort
3. Merge
sort
4. Quick
sort
5. Selection
sort
6. Shell
sort
Tetapi pada kali ini
saya akan membahas tentang salah satu materi yaitu sorting dengan algoritma
bubble sort dan quick sort.
a. Metode
Pengurutan dengan Bubble Sort
Metode pengurutan
bubble sort merupakan algoritma pengurutan yang paling tua dan sederhana dan
mudah untuk diimplementasikan. Metode gelembung (bubble sort) disebut juga dengan
metode pertukaran (exchange sort) yaitu metode yang mengurutkan data dengan
cara membandingkan masing-masing elemen, kemudian melakukan penukaran bila
perlu. Metode ini mudah untuk dipahami dan diprogram, tetapi bila dibandingkan
dengan metode lain yang lebih kompleks, metode ini merupakan metode yang paling
tidak efisien untuk mengurutkan data.
b.
Metode Pengurutan dengan Quick Sort
Metode pengurutan quick sort merupakan algoritma
pengurutan data yang sangat cepat dengan tipe penyelesaian divide and conquer.
sehingga cocok untuk mengurutkan data dalam jumlah yang besar.
c.
Algoritma dari Bubble Sort
Adapun Proses
Algoritma Bubble Sort adalah sebagai
berikut:
1. Pengurutan
dimulai dengan membandingkan elemen pertama untuk mendapatkan angka terbesar.
Lalu angka tersebut ditempatkan pada elemen terakhir.
2. Pada
akhir proses pertama ini, bilangan yang terbesar menempati tempat yang sesuai.
3. Pada
akhir proses kedua ini, bilangan terbesar kedua menempatkan tempat yang sesuai.
4.
Bila proses ini dilanjutkan, tidak ada
pertukaran tempat lagi bagi bilangan – bilangan tersebut, sebab bilangan
tersebut telah selesai disusun.
Algoritma pengurutan
dengan bubble sort dapat dituliskan sebagai berikut :
for(i=0; i<=n-2; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (data[j]<data[j-1])
{
buble=data[j];
data[j]=data[j-1];
data[j-1]=buble;
}
}
}
d. Algoritma
dari Quick Sort
Adapun proses
Algoritma Quick Sort adalah Sebagai berikut:
1. Pilih satu
elemen secara acak sebagai pivot
2. Pindahkan
semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih
besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah
satunya.
3. Lakukan sort
secara rekursif terhadap sub-array sebelah kiri dan kanan pivot
Algoritma
pengurutan dengan quick sort dapat dituliskan sebagai berikut :
int
partisi (int data[], int awal, int akhir)
{
int
x,i,j,simpan;
i=awal;
j=akhir;
while(1)
{
while(data[i]<data[awal])
i=i+1;
while(data[j]>data[awal])
j=j-1;
if (i<j)
{
//tukarkan data
simpan=data[i];
data[i]=data[j];
data[j]=simpan;
}
else
return
j;
}
}
void
quick_sort(int data[], int awal, int akhir)
{
int
q;
if(awal<akhir)
{
q=partisi(data,awal,akhir);
quick_sort(data,awal,q);
quick_sort(data,
q+1,akhir);
}
}
e. Contoh
Program
Berikut ini adalah
contoh program bubble sort :
#include
<iostream>
using
namespace std;
int main()
{
int i,j,n, bubble,pil, data[10];
cout<<"========================================="<<endl;
cout<<"| Program Sorting
Data
|"<<endl;
cout<<"| Pilih Metode Sorting
Bubble : |"<<endl;
cout<<"| 1. Ascending |"<<endl;
cout<<"| 2. Descending |"<<endl;
cout<<"========================================="<<endl;
cout<<"Masukkan Banyak Nomor
Undian: ";cin>>n;
for(i=0; i<n; i++)
{
cout<<"Data ke -
"<<i+1<<" : ";cin>>data[i];
}
cout<<"Masukkan Metode Yang
Dipilih : ";cin>>pil;
if (pil==1)
{
for(i=0; i<=n-2; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (data[j]<data[j-1])
{
bubble=data[j];
data[j]=data[j-1];
data[j-1]=bubble;
}
}
}
cout<<"Data yang
telah disorting secara ascending "<<endl;
for(i=0; i<n; i++)
{
cout<<"Data ke-
"<<i+1<<" : "<<data[i]<<endl;
}
}
else if (pil==2)
{
for(i=0; i<=n-2; i++)
{
for (j=n-1; j>=i+1; j--)
{
if (data[j]>data[j-1])
{
bubble=data[j];
data[j]=data[j-1];
data[j-1]=bubble;
}
}
}
cout<<"Data yang telah disorting
secara descending "<<endl;
for(i=0; i<n; i++)
{
cout<<"Data ke-
"<<i+1<<" : "<<data[i]<<endl;
}
}
}
Sekian penjelasan
dari saya tentang materi sorting yaitu sorting dengan algoritma bubble sort dan
quick sort. Semoga bermanfaat.
Daftar pustaka
http://ruzi.staff.gunadarma.ac.id/Downloads/files/32027/PENGURUTAN+BILANGAN+DENGAN+METODE+BUBBLE+SORT.doc
Langganan:
Postingan (Atom)
