Struktur Data- Graph

Graph

Graph adalah kumpulan dari simpul dan busur

Secara sistematis dinyatakan sebagai:

            G = (V,E)

Keterangan :

            G = Graph
            V = Simpul/Vektor/Node/Titik
            E = Busur/Edge/arc

 

Dari contoh graph di atas dapat diketahui bahwa

V (Simpul)  terdiri dari A, B, C, D dan E
E (Busur) terdiri dari e1, e2, e3, e4, dan e5

Graph ada 3 macam, yaitu:

1.      Graph Tidak Berarah

2.      Graph Berarah

3.      Graph Berbobot

Lalu apa sih bedanya? Yaudah kita akan bahas satu persatu ya mulai dari graph tidak berarah, graph berarah dan graph berbobot

1.      Graph Tidak Berarah (Undirected Graph atau Non-Directed Graph )

-          Urutan simpul dalam sebuah busur tidak di pentingkan.
Misalnya penyebutan busur e1 dapat disebut AB atau BA

 

2.      Graph Berarah (Directed Graph)

-          Urutan simpul mempunyai arti.

-          Memiliki tanda panah. Dengan tujuan supaya kita tau Dari simpul mana dan tujuan kemana
Misalnya Penyebutan BA berbeda dengan AB. Karena BA terletak pada busur e1, dan AB terletak pada busur e8.

3.      Graph Berbobot (Weighted Graph)

-          Setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur dinyatakan mempunyai bobot

-          Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 titik.

-          Nilai sebuah busur tidak peerlu digambarkan lebih panjang sesuai bobotnya. Misalnya bobot 5 digambarkan lebih panjang dari bobot 3.

Ø  Graph berbobot Tidak berarah

                                      Dari contoh di atas dapat kita ketahui:

AB=BA berbobot 8
CE=EC berbobot 7

Ø  Graph berbobot Berarah

Dari contoh diata dapat kita ketahui:

     BA berbobot 8

     AB berbobot 10

Istilah istilah pada Graph

1.      Incident

Maka dari gambar di atas dapat di ketahui V dan W terletak pada e, dan e disbut incident dengan V dan W.

2.      Degree

                      Degree adalah jumlah busur yang incident dengan simpul tersebut.

                      Degree ada 2 macam, yaitu:

1.       Indegree

Indegree adalah jumlah busur yang “masuk” atau menuju ke simpul
  dari contoh diatas dapat kita ketahui bahwa V = Indegreenya 2

2.       Outdegree

Outdegree adalah jumlah busur yang “Keluar” atau berasal dari simpul temsebut
  dari contoh diatas dapat kita ketahui bahwa T = Outdegreenya 2

3.       Adjacent

Ø  Ajacent Tidak beberah

 

                Pada graph tidak berarah , 2 buah simpul disebut adjacent apabila ada busur yang menghubungkan kedua simpul tersebut.
dari contoh diatas dapat diketahui SImpul V dan W disebut adjacent.

Ø  Ajacent Berarah

                 

Pada scontoh diatas sumpul V adjacent dengan simpul W

4.       Successor dan Predecessor

5.       Path

Adalah serangkaian simpul simpul yang berbeda, yang adjacent secara berturut turut dari simpul satu kesimpul berikutnya

REPRESENSI GRAPH dalam BENTUK MATRIX

1.       Graph Tidak Berarah

             

2.       Graph Terarah

       Penulisan dalam Matrik :

3.       Grap Berarah dan berbobot

     Penulisan dalam matrik: