GRAPH [Struktur Data]



Assalamualaikum Wr.Wb.
Hai teman-teman semua, kali ini aku akan membahas materi selanjutnya pada struktur data yaitu GRAPH. Seperti biasa ni ya sebelumnya apa kalian tau apa itu grap? Nahh jika belum kita simak baik baik yukk.

GRAPH adalah kumpulan dari simpul dan busur yang secara matematika dinyatakan sebagai :


Contoh graph :
           
Undirected graph(graph tak berarah)
-       Sebuah graph mungkin terdiri dari 1 simpul.
-       Belum tentu semua simpulnya terhubbung dengan busur.
-       Mungkin mempunyai simpul yang tak terhubung dengan simpul lain.
-       Mungkin semua simpul saling berhubungan.


Graph Berarah dan Graph tak Berarah

Ø  Graph berarah (Directed graph)
Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan BA adalah e8.
Ø  Graph tidak berarah (Undirected graph)

Urutan simpul dalam sebuah busur tidak dipentingkan, misal busur e1 dapat disebut AB/BA.

          
Dapat kita lihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul.

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




Ø  Graph berarah dan berbobot
            Ex :


SOAL LATIHAN!

1.    Sebuah graph tidak berarah mempunyai 5 buah vertex, yaitu P, Q, R, S, T. Vertex-vertex tersebut dihubungkan oleh 6 buah edge yang menghubungkan antara P-Q, P-S, Q-T, Q-R, R-S, dan R-T. Gambarkan!

Jawab :


1.    Gambarkan jika graph diatas adalah graph berarah dan berbobot,dengan nilai bobot sbb :
PQ = 8
SR = 9
SQ = 5
QP = 6
RT = 8
TS = 4
RS = 9
QS = 2

Jawab :

·         Istilah pada Graph

1.    Incident
            jika e merupakan busur dengan simpul-simpulnya adalah v dan w ditulis e = (v , w) maka v dan w disebut “terletak” pada e. Dan e disebut incident dengan v dan W.
2.    Degree (derajat), indegree dan outdegree.
Degree untuk graph tidak berarah sedangkan indegree dan outdegree untuk graph berarah.

Degree          : sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
Indegree       : sebuah simpul pada graph berarah adalah jumlah busur yang “masuk” atau menuju simpul tersebut.

Outdegree    : sebuah simpul pada graph berarah adalah jumlah busur yang “keluar” atau berasal dari simpul tersebut.

3.   Adjacent
o   Pada graph tidak berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Dapat dilihat pada gambar dibawah ini.

o   Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v. Dapat dilihat gambar dibawah ini.


4.    Successor dan Predecessor
Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor simpul v.

5.  Path
Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.
Contohnya dapat dilihat pada gambar dibawah ini.


·         Representasi Graph dalam bentuk Matrix
Ada dua yaitu berarah dan tak berarah,sebagai berikut contohnya:




·         Graph berarah dan berbobot



Sekian terimakasih penjelasan dari saya,semoga dapat dipahami dan bermanfaat.
Wassalamualaikum Wr.Wb.








Komentar

Posting Komentar

Postingan populer dari blog ini

TREE [Struktur Data]

Gambar
Assalamualaikum Wr.Wb Halo teman teman semuaa, pasti masih semangat kan yaa?? Hemm jadi aku mau ngebahas struktur data materi tree. Yuk kita pelajari apasih tree itu? Tree adalah kumpulan node yang saling terhubung satu sama lain. Dalam suatu kesatuan yang membentuk layaknya struktur sebuah pohon. Nah sedangkan struktur pohon itu adalah suatu cara mempresentasikan suatu struktur hiarki(one to many) Tree dibagi menjadi 2 yaitu 1.       Tree statik        : isi node – nodenya tetap karena bentuk pohonnya sudah ditentukan 2.       Tree dinamik    : isi nodenya berubah ubah karena terjadi proses penambahan (insert) dan penghapusan (delete) Ø Node root            Node root dalam tree adalah suatu node yang memiliki hiarki tertinggi dan dapat juga memiliki node node anak. Semua node dapat ditelusuri dari node root tersebut. Node node lain di bawah node root saling terhubung satu sama lain dan disebut subtree. Ø Implementasi Tree Contoh penggunaan struktu
Baca selengkapnya

Searching [Struktur Data]

Gambar
Assalamualaikum Wr.Wb. Hai teman teman.. lanjut yuk belajarnya Kali ini aku akan bahas tentang searching. Apasih searching dalam struktur data ini? Nahh bagi yang belum tahu yukk simak baik baik . Searching adalah merupakan proses pencarian dalam pengolahan data. untuk menemukan nilai (data) pada sekumpulan data yang bertipe sama. Searching dibagi menjadi 2 yaitu sequential search dan binary search. Kita bahas satu persatu yaa 1.       Sequential search adalah proses pencarian yang dilakukan secara berurut.   Sequential search merupakan teknik yang paling sederhana dan langsung dapat digunakan pada struktur data baik Array maupun liked list. Sequential search ini biasanya dilakukan pada data yang tidak terurut seperti contoh berikut . Ø Algoritma sequential search 1.       Input X (data yang dicari) 2.       Bandingka X dengan data ke 1-n 3.       Jika ada data yang sama dengan X maka cetak pesan “Ada” 4.       Jika tidak ada data yang sama den
Baca selengkapnya