GRAPH 8
KHOI R U NURFI TRI , S . K O M . , M . KO M
FAKULTAS T E K N I K
UNI VERSI TAS MUH AMM A DI Y A H P O NO RO GO
Mata Kuliah Struktur Data
CAPAIAN
PEMBELAJARAN
1. Mahasiswa mengetahui konsep dasar
Graph
2. Mahasiswa mengetahui Jenis-jenis
Grap
3. Mahasiswa Mengetahui Operasi-
operasi Graph
4. Mahasiswa Mengetahui implementasi
Graph pada C++
MATERI
1. Definisi Graph
2. Jenis-Jenis Graph
3. Implentasi dalam C++
Bagaimana
merepresentasikan
struktur hubungan
seperti ini ???
Bagaimana
merepresentasikan
struktur hubungan
seperti ini ???
Hubungan
seperti itu bisa
Bagaimana dinyatakan
merepresentasikan dalam bentuk
struktur hubungan Struktur Data
Graph
seperti ini ???
Tentunya Struktur Data ini berbeda dengan struktur data Tree
Analogi Graph dalam Kehidupan Sehari-Hari
Graph dalam kehidupan sehari-hari dapat dianalogikan sebagai suatu
jaringan satu dengan jaringan lainnya yang saling terhubung. Misal seperti
negara Indonesia yang memiliki banyak kota seperti: Jakarta, Bandung,
Srabaya, Yogyakarta. Kota-kota itulah yang tergabung dalam negara
Indonesia dan kota-kota itulah yang saling berhubungan.
Contoh-contoh aplikasi graf
Peta (jaringan jalan dan hubungan antar kota)
Jaringan komputer
Jaringan persahabatan (facebook, dll)
Peta migrasi populasi hewan
…?
Representasi Graph
Suatu graph mengandung 2 himpunan, yaitu:
Himpunan E yang merupakan pasangan tak urut dari simpul.
Anggotanya disebut ruas (edge, rusuk atau sisi).
Himpunan V yang elemennya disebut simpul (atau vertex atau point
atau node atau titik).
Graph dengan definisi tersebut di atas ditulis dengan notasi :
G=(V,E)
Representasi Graph
Jenis-Jenis Graph
Directed graph (Digraph)
Undirected / unordered Graph
Weight Graph
Jenis-Jenis Graph
Directed graph/ Digraph (Graph Berarah)
Jika sisi-sisi graph hanya berlaku satu arah. Misalnya : {x,y} yaitu arah x ke y, bukan dari y ke x; x disebut origin
dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai vektor (x, y)
Contoh Digraph G = {V, E} :
V = {A, B, C, D, E, F, G, H, I,J, K, L, M}
E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E),
(C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K),
(D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K),
(J,M), (L,K), (L,M)}.
Jenis-Jenis Graph
Undirected graph/ Undigraph (Graph Tak Berarah)
Setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak
memiliki mata panah dan secara notasional menggunakan kurung kurawal
Jenis-Jenis Graph
Weighted Graph (Graph Berbobot)
Graph dengan sisi mempunyai Bobot/ Biaya. “Biaya" ini bisa mewakili banyak aspek: biaya ekonomi suatu
aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya.
Istilah-Istilah dalam Graph
Incident
Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut
“terletak” pada e, dan e disebut incident dengan v dan w.
Degree (derajat), indegree, dan outdegree
Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
- Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul
tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
- 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.
Adjacent
Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan
kedua simpul tersebut. Simpul v dan w disebut adjacent.
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 dari simpul v
Path
Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut
dari simpul satu ke simpul berikutnya.
Matrix
Representasi
GRAPH Linked List
Adjacency Matrix Graph tak berarah
Urut Abjad
Graph
Dalam
Matrix
Degree Simpul : 3
Adjacency Matrix Graph berarah
Graph
Dalam
Matrix
Adjacency Matrix Graph berbobot
Graph 5 4
Dalam 5 3 12
Matrix 3 8 6
4 8 3
12 6 3
Adjency List graph tak berarah
Digambarkan sebagai sebuah simpul yang
memiliki 2 pointer.
Graph
Dalam
Linked List
Adjency List graph tak berarah
Contoh : untuk vertex A, memiliki 2 edge yang
terhubung yaitu e1 dan e2
Graph
Dalam
Linked List
Adjency List graph berarah & Tidak Berarah
Graph
Dalam
Linked List
Adjency List graph berarah dan Berbobot
Graph
Dalam
Linked List
Contoh Program
void graf::masukan (){
#include <iostream>
cout<<"Hitung Jarak pada Graf dengan 5
#include <string>
Titik Simpul"<<endl<<endl;
using namespace std; cout<<" Titik 1: ";cin>>kata1;
class graf{ cout<<" Titik 2: ";cin>>kata2;
public : cout<<" Titik 3: ";cin>>kata3;
void masukan(); cout<<" Titik 4: ";cin>>kata4;
void keluaran(); cout<<" Titik 5: ";cin>>kata5; cout<<endl;
private: cout<<"Garis yang dapat dibentuk: "<<endl;
char kata1; //A cout<<kata1<<kata2<<", "; //AB = a
char kata2; //B cout<<kata2<<kata3<<", "; //BC = b
char kata3; //C cout<<kata3<<kata5<<", "; //CE = c
char kata4; //D cout<<kata4<<kata3<<", "; //DC = d
char kata5; //E cout<<kata4<<kata5<<“,”; //DE = e
int a, b, c, d, e, f, g, h, i, j; cout<<kata1<<kata4<<", "; //AD = f
}; cout<<kata2<<kata1<<", "; //BA = g
cout<<kata5<<kata2<<endl<<endl; //EB = h
Contoh Program
cout<<"Busur simpul "<<kata1<<" dengan "<<kata2<<" : ";cin>>a;
cout<<"Busur simpul "<<kata2<<" dengan "<<kata3<<" : ";cin>>b;
cout<<"Busur simpul "<<kata3<<" dengan "<<kata5<<" : ";cin>>c;
cout<<"Busur simpul "<<kata4<<" dengan "<<kata3<<" : ";cin>>d;
cout<<"Busur simpul "<<kata4<<" dengan "<<kata5<<" : ";cin>>e;
cout<<"Busur simpul "<<kata1<<" dengan "<<kata4<<" : ";cin>>f;
cout<<"Busur simpul "<<kata2<<" dengan "<<kata1<<" : ";cin>>g;
cout<<"Busur simpul "<<kata5<<" dengan "<<kata2<<" : ";cin>>h;
}
void graf::keluaran() {
cout<<"Jadi panjang jarak totalnya = "<<a+b+c+d+e+f+g+h<<endl<<endl;
cout<<"Mencari jalur terpendek dari "<<kata1<<" menuju "<<kata4<<" : "<<endl;
int j, k, l;
j=e+d; //Alternatif 1
k=a+b+c; //Alternatif 2
l=f+d+c; //Alternatif 3
cout<<"Alternatif Pertama : "<<kata1<<" -> "<<kata4<<" -> "<<kata5<<" = "<<kata1<<kata4<<" +
"<<kata4<<kata5<< " Jarak : "<<j<<endl;
cout<<"Alternatif Kedua : "<<kata1<<" -> "<<kata2<<" -> "<<kata3<<" -> "<<kata5<<" =
"<<kata1<<kata2<<" + "<<kata2<<kata3<<" + "<<kata3<<kata5<< "Jarak : "<<k<<endl;
cout<<"Alternatif Ketiga : "<<kata1<<" -> "<<kata4<<" -> "<<kata3<<" -> "<<kata5<<" =
"<<kata1<<kata4<<" + "<<kata4<<kata3<<" + "<<kata3<<kata5<<" Jarak : "<<l<<endl;
Contoh Program
//Pilihan jalur/laluan
if (j<e && j<f) cout<<"JALUR YANG DIPILIH ADALAH YANG JARAKNYA " <<j;
if (k<a && k<b && k<c) cout<<"JALUR YANG DIPILIH ADALAH YANG JARAKNYA "
<<k;
if (l<c && l<d && n<f) cout<<"JALUR YANG DIPILIH ADALAH YANG JARAKNYA "
<<l;
}
int main(int argc, char *argv[])
{
graf x;
[Link](); cout<<endl;
[Link](); cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
return 0;
}
Contoh Program
Algoritma mencari jarak terpendek dari A ke E:
1. Menentukan jumlah simpul (vertex)
2. Pembentukan garis
3. Menentukan panjang busur
4. Hitung jarak-jarak dari A ke titik E
REFERENSI
Kadir, Abdul (2013). Teori dan Aplikasi
Struktur Data Menggunakan C++.
Yogyakarta:Penerbit ANDI
J, Rosa A.S. (2018). Struktur Data Terapan
Dakam Berbagai Bahasa Pemrograman
PASCAL, C, C++, dan JAVA. Bandung.
Penerbit Informatika
Sianipar, R.H. (2015). Soal & Penyelesaian
C++. Bandung. Penerbit Informatika
Munir, Rinaldi. Lidya, Lenony. (2016)
Algoritma Pemrograman. Bandung. Penerbit
Informatika
Yatini, Indra. [Link] Nasution.
(2002).Algoritma dan Struktur Data dengan
C++.Graha Ilmu