PROGRAM GRAF BERARAH,TAK BERARAH DAN BERBOBOT

—  PROGRAM GRAF BERARAH,TAK BERARAH DAN BERBOBOT

—  GRAPH

• Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :

G = (V, E)

Dimana :

                G = Graph

                V = Simpul atau Vertex, atau Node, atau Titik

                E = Busur atau Edge, atau arc

—  Graf merupakan suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai simpul (vertex/node) dan jalan yang menghubungkan setiap kotanya sebagai sisi (edge) yang bobotnya (weight) adalah panjang dari jalan tersebut.

—   3. Indegree sebuah simpul pada graph berarah
adalah jumlah busur yang kepalanya incident dengan
simpul tersebut, atau jumlah busur yang 􀁬masuk􀁺􀀁atau
menuju simpul tersebut.

  4. Outdegree sebuah simpul pada graph berarah
adalah jumlah busur yang ekornya incident dengan
simpul tersebut, atau jumlah busur yang 􀁬keluar􀁺􀀁atau
berasal dari simpul tersebut.

•       Sebuah graph mungkin hanya terdiri                                      
dari satu simpul.

• Sebuah graph belum tentu semua
simpulnya terhubung dengan busur.

• Sebuah graph mungkin mempunyai
simpul yang tak terhubung dengan
simpul yang lain.

• Sebuah graph mungkin semua
simpulnya saling berhubungan

—  Berdasarkan orientasi arah pada sisi dan bobotnya, maka secara umum graf dapat dibedakan
atas tiga jenis yaitu:

1. GRAPH BERARAH (directed graph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Secara
umum sisi berarah disebut dengan busur (arc). Pada graf berarah (u,v) dan (v,u)
menyatakan dua buah busur yang berbeda, dalam arti kata bahwa (u,v) ¹ (v,u).

— 

Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lintas
kota dan lain sebagainya. Sehingga pada graf berarah gelang atau looping
diperbolehkan tetapi sisi ganda tidak diperbolehkan.

—  Contoh programnya:

—  Uses wincrt;
type titikList= ^Titik;
garisList= ^Garis;{simpuluntuk senarai Titik}
Titik= record
namaTitik: char;
NextTitik: TitikList;
KeGaris: GarisList;
end;
{simpul untuk senarai garis }Garis= record panjang: word;
KeTitik: TitikList;
NextGaris: GarisList;
end;
varT : text;
T1,T2: Byte; P : word;
GraphAwal: TitikList
End.

—  2. GRAPH tak BERARAH (undirected graph atau non-directed graph) :

2. Graf tidak berarah

—  Yaitu Graf yang setiap sisinya tidak mempunyai arah anak panah tetapi memiliki bobot pada

—  setiap sisinya. Urutan pasangan simpul yang terhubung oleh sisi tidak diperhatikan.

—  Sehingga (u,v) = (v,u) adalah sisi yang sama.

— 
3. GRAPH Berbobot (Weighted Graph).

—  graf berbobot merupakan suatu graf tanpa busur parallel dimana setiap busurnya berhubungan dengan suatu bilangan riil tak negatif yang menyatakan bobot busur (w(a)) tersebuT.
Di dalam model graf, ada informasi yang ditambahkan pada busur graf. Misalnya pada graf yang menggambarkan antara kota-kota, dapat ditambahkan sebuah bilangan pada setiap busur untuk menujukkan jalur antara kedua kota yang dibutuhkan oleh busur tersebut.
 

—  Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki
bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui
sebuah jalan, dll.
 

Ø  Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.

Contoh program

—  HASILNYA

SEKIAN PRESENTASI KAMI

TERIMAKASIH

Read More

soal tentang insertion sort

1. Buatlah satu contoh tentang insertion sort
2. Apa perbedaan exchange sort dan bubble sort
3. buatlah lima contoh tentang metode pengurutan data
4. Apa yang dimaksud dengan pengurutan (sorting)
5. Buatlah contoh program selection sort

Jawaban :

1.      contoh tentang insertion sort
 
 
 
 

12.      perbedaan exchange sort

•            Sangat mirip dengan Bubble Sort

•         Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort

•         Pebedaan : dalam hal bagaimana membandingkan antar elemen-elemennya.

•         Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu.  Jadi ada elemen yang selalu menjadi elemen pusat (pivot).

•         Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Sedangkan bubble sort

•         Metode sorting termudah

•         Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda.

•         Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.

2.      lima contoh tentang metode pengurutan data

•            Pengurutan berdasarkan perbandingan (comparison-based sorting)

•         Bubble sort, exchange sort

•         Pengurutan berdasarkan prioritas (priority queue sorting method)

•         Selection sort, heap sort (menggunakan tree)

•         Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

•         Insertion sort, tree sort

•         Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

•         Quick sort, merge sort

•         Pengurutan berkurang menurun (diminishing increment sort method)

•         Shell sort (pengembangan insertion)

34.      pengurutan (sorting)

•            Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.

•         Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)

•         Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

Contoh:

•         Data Acak       : 5 6 8 1 3 25 10

•         Ascending       : 1 3 5 6 8 10 25

•         Descending     : 25 10 8 6 5 3 1

45.      contoh program selection sort 

 

Read More