graph
11/04/21 struktur data by andi arfian 1
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
11/04/21 struktur data by andi arfian 2
Contoh sebuah graph
v2
B Simpul=[Link],vortex(V)
e1 e3 V=v1,v2,,,,,v5
v1
A
e4 C v3 Busur =arc,egde (E)
e5 E1,e2,,,,e7
e2 e7
D E
e6 v5
v4
11/04/21 struktur data by andi arfian 3
Karakter graph
Sebuah graph mungkin hanya terdiri dari satu simpul.
Sebuah graph belum tentu semua simpulnya terhubung
dengan busur
Dalam sebuah graph kemungkinan ada simpul yg tak
terhubung
Sebuah graph kemungkinan saling berhubungan
11/04/21 struktur data by andi arfian 4
Terminologi
GRAPH adalah suatu struktur data yang berbentuk network/jaringan dimana hubungan
antara elemen-elemennya adalah many-to-many.
BU :
G = (V,E)
V = NODE (VERTICE), E = ARC (EDGE)
SUBGRAPH :
Adalah GRAPH yang merupakan suatu subset/bagian dari GRAPH.
PATH
Adalah sequence dari kumpulan node-node dimana tiap node dengan
node berikutnya dihubungkan dengan EDGE
B D
A F
C E
A-F
11/04/21 struktur data by andi arfian 5
Terminologi
SIMPLE PATH
Jika node dalam path tersebut hanya muncul 1 kali.
B D
B D
A F
A F
C E
A-F
11/04/21 struktur data by andi arfian 6
Terminologi
CYCLE GRAPH
Jika node pertama dan node terakhir dalam GRAPH adalah sama.
A
C
11/04/21 struktur data by andi arfian 7
Tipe
Directed GRAPH (DiGraph)/ berarah
Undirected GRAPH/tidak berarah
Connected GRAPH
Unconnected GRAPH
Weighted GRAPH/berbobot
Unweighted GRAPH
11/04/21 struktur data by andi arfian 8
Directed Graph
Jika sepasang node yg membentuk edge dalam GRAPH
mempunyai arah/arti
A C
Directed Graph
11/04/21 struktur data by andi arfian 9
Contoh direct graph
Busur ab adalah satu
b busur.
Busur b->a dengan busur
lainnya
a c
d e
11/04/21 struktur data by andi arfian 10
Undirected Graph/tak berarah
Jika sepasang node yang membentuk edge dalam
GRAPH tidak terarah./ urutan simpul dalam busur tidak
dipentingkan
Ex.a b,b->a
A C
Undirected Graph
11/04/21 struktur data by andi arfian 11
Connected Graph/terhubung
Bila setiap pasang node punya hubungan di antara
keduanya dalam GRAPH.
B D
A F
C E
Connected Graph
11/04/21 struktur data by andi arfian 12
Full Connected Graph/Terhubung
penuh
Suatu graph terhubung penuh jika setiap
simpul saling berhubungan
b Pada full conneted berlaku : m=n(n-1) /2
c Dimana m=jumlah busur
a
N=jumlah simpul
d e Terlihat : untuk simpul n=5,
maka busur m=5(5-1)/2=10
11/04/21 struktur data by andi arfian 13
Unconnected Graph
Bila terdapat SubGraph yang terisolasi.
B D
A F
C E
Unconnected Graph
11/04/21 struktur data by andi arfian 14
Weighted Graph
Jika semua edge dalam GRAPH diberi nilai.
A 4 C
2 3
5
B D
Weighted Graph
Apabila setiap busur mempunyai nilai yang menyatakan hubungan antara dua
buah simpul ,maka busur tersebut dikatakan mempunyai bobot,dan graph disebut
graph berbobot, bobot sebuah busur dapat menyatakan panjang sebuah jalan
anatara dua titik
11/04/21 struktur data by andi arfian 15
Graph berlabel hubungan dengan jarak dan diameter
Graph berbobot adalah graph yang diberikan bobot
disetiap [Link] tersebut bisa merupakan
pengambaran suatu besaran mengenai jarak,biaya atau
apa saja(Sesuai aplikasi yang akan dibahas)
f Jarak antara dua titik didalam graphadalah jalur
5 3 terpendek yg menghubungkan kedua simpul tersebut
a 5 b Diameter Graph (Terhubung) adalah nilai maksimum
dari jarak(antara dua titik) yang ada didalam graph
4 7 4
Ex, dari titik D menuju titik F minimal dapat dilakukan
d e sebayak 2 langkah(sehingga,jarak D ke F adalah 2)
6 begitu juga dari titik e ke f, sedankan dari titik A atau
Bketitik F sama-sama dapat dilakukan dengan sekali
langkah ( jarak=1),
maka diameter graph adalah maksimal dari jarak-
jarak tersebut.
11/04/21 struktur data by andi arfian 16
Unweighted Graph
Jika semua edge dalam GRAPH tidak ada nilai.
A C
B D
Weighted Graph
11/04/21 struktur data by andi arfian 17
Sub graph
Sub graph adalah bagian dari graph ,bahkan
graph itu sendiri merupakan sub graph dari
dirinya sendiri,
Contoh (hanya untuk graph sederhana tak
berbobot dan tak berarah)
Graph G Graph G1 Graph G2
Graph G1 adalah
subgraph dari G
11/04/21 struktur data by andi arfian
G2 adalah sub dari18G
Multi graph
Sebuah multi graph hampir serupa dengan graph,tetapi
tidak dapat dikatakan graph karena didalamnya
mengandung lebih dari satu garis yang menghubungkan
dua buah titik / simpul atau menghubungkan garis yang
menghubungkan titik yang sama (Loop)
Contoh,
d
e8 e6 Sebuah multigraph karena ada garis e1dan e2
yang menghubungkan titik A dan B atau terdapat
e7 Loop e5 di titik C
a c
e2 e4
e5
e1 e3
multigraph
11/04/21 struktur data by andi arfian 19
Walk ,trail,path
WALk adalah suatu perjalanan yang melintasi barisan
titikdan barisan garis yang ada ada dalam graf yang
dimulai dari titik awal tertentu(V1) menuju titik
akhir(Vn),banyaknya ruas yang dilalui disebut sebagai
panjang WALK, Walk (Cyle) dikatakan tertutup bila titik
awal juga merupakan titik akhirnya.
Trail adalah walk yang tidak memiliki garis atau ruas
yang sama didalam barisannya.
Path adalah walk yang semua titik dalam barisanya
berbeda, path sudah pasti [Link](Leght) dari
sebuah path adalah banyaknya garis yang dilalui
11/04/21 struktur data by andi arfian 20
Walk terbuka ,path dan trail Smr Sby
•Titik Jkt,Bdg,Yog,Smr dan S by
Jkt
Walk Tebuka Yog
Bdg
Walk tertutup dan Trail
Graph lengkap /complete bila setiap titik memiliki hubungan dengan seluruh
titik yang ada didalam graph, N(N-1)/2 maka 5(5-1)2= 10
Jalur Eulerian didalam Graph yaitu jalur yang melewati seluruh titik yang ada
didalam graph tepat satu kali ,tetapi boleh melewati garis penghubungnya
lebih dari satu, jalur eulerian dimulai dari titik awal dan berakhir dititik awal
11/04/21 struktur data by andi arfian 21
Diskusi
A
B C D
E F
Apakah tree tersebut juga merupakan Graph ?
Jika merupakan Graph, termasuk dalam tipe yang mana ?
11/04/21 struktur data by andi arfian 22
Representasi
ADJACENCY MATRIX
Direpresentasikan dengan Array 2 dimensi
Tipe komponen dari Array bisa digunakan
BOOLEAN atau INTEGER (untuk
WEIGHTED GRAPH).
ADJACENCY LIST
Direpresentasikan sebagai suatu list, bisa
dinyatakan dengan LINKED -LIST.
11/04/21 struktur data by andi arfian 23
Adjacency
B D
A F
C E
Undirected Graph
NODE A B C D E F NODE EDGE LIST
A 0 1 1 0 0 0 A B C
B 1 0 1 1 1 0 B A C D E
C 1 1 0 0 1 0 C A B E
D 0 1 0 0 1 1 D B E F
E 0 1 1 1 0 1 E B C D F
F 0 0 0 1 1 0 F D E
Adjacency Matrix Adjacency List
11/04/21 struktur data by andi arfian 24
Traversal
Adalah proses untuk mengunjungi setiap node pada
GRAPH. Dua metode yang digunakan untuk
traversal pada GRAPH :
• Breadth First Traversal (BFT) : adalah proses traversal
yang lebih memprioritaskan node-node tetangga atau
node pada level yang sama. Setelah itu diteruskan ke
level terdalam selanjutnya.
• Depth First Traversal (DFT) : adalah proses traversal
yang lebih memprioritaskan langkah penelusuran ke level
terdalam terlebih dahulu.
11/04/21 struktur data by andi arfian 25
Algoritma BFT
Pilih node Awal
1. Set semua node dengan status siap dikunjungi (status=1)
2. Enqueue(node Awal), ubah status node awal menjadi
menunggu (status=2)
3. Dequeue&(node_N), ubahstatus node_N menjadi telah
diproses (status=3)
4. Enqueue semua node yang adjacent dengan node_N dan
memiliki status=1, ubah status mereka menjadi 2
5. Ulangi langkah 3 s.d. 4 hingga Queue kosong
11/04/21 struktur data by andi arfian 26
Algoritma DFT
Pilih node Awal
1. Set semua node dengan status siap dikunjungi (status=1)
2. Push(node Awal), ubah status node awal menjadi
menunggu (status=2)
3. Pop(node_N), ubahstatus node_N menjadi telah diproses
(status=3)
4. Push semua node yang adjacent dengan node_N dan
memiliki status=1, ubah status mereka menjadi 2
5. Ulangi langkah 3 s.d. 4 hingga Stack kosong
11/04/21 struktur data by andi arfian 27
Contoh Traversal
B D
NODE EDGE LIST
A F A B C
C E B A C D E
C A B E
Undirected Graph
D B E F
E B C D F
F D E
BFT ?
Adjacency List
DFT ?
11/04/21 struktur data by andi arfian 28
BFT
start node A
Status Node
Langkah Node_N QUEUE Hasil
A B C D E F
1 1 1 1 1 1 1
2 A 2 1 1 1 1 1
3 A 3 1 1 1 1 1 A
4 A B-C 3 2 2 1 1 1 A
5 B C 3 3 2 1 1 1 A-B
6 B C-D-E 3 3 2 2 2 1 A-B
7 C D-E 3 3 3 2 2 1 A-B-C
8 C D-E 3 3 3 2 2 1 A-B-C
9 D E 3 3 3 3 2 1 A-B-C-D
10 D E-F 3 3 3 3 2 2 A-B-C-D
11 E F 3 3 3 3 3 2 A-B-C-D-E
12 E F 3 3 3 3 3 2 A-B-C-D-E
13 F 3 3 3 3 3 3 A-B-C-D-E-F
11/04/21 struktur data by andi arfian 29
Selesai
11/04/21 struktur data by andi arfian 30
11/04/21 struktur data by andi arfian 31
11/04/21 struktur data by andi arfian 32
11/04/21 struktur data by andi arfian 33
11/04/21 struktur data by andi arfian 34
11/04/21 struktur data by andi arfian 35
11/04/21 struktur data by andi arfian 36