Data Structure Chapter 8
GRAPH
Dahlia Widhyaestoeti, S.Kom
Agenda Hari Ini
Representasi Graph Penelusuran Graph
2
Representasi Graph 1. Representasi Graph dalam bentuk Matrix a. Adjacency Matrix Graph Tak Berarah (Undirected Graph)
B
C
A D
E
A B
C
D
E
0 1
2
3
4
A
0
0 1
0
1
0
B
1
1 0
1
0
1
C
2
0 1
0
1
1
D
3
1 0
1
0
1
E
4
0 1
1
1
0
Data yang terdapat baik dalam row maupun column, dapat menyatakan degree sebuah simpul. 3
Representasi Graph 1. Representasi Graph dalam bentuk Matrix b. Adjacency Matrix Graph Berarah (Directed Graph) ke
B
C
A D
E
dari
A B
C
D
E
0 1
2
3
4
A
0
0 1
0
1
0
B
1
1 0
1
0
1
C
2
0 1
0
1
1
D
3
0 0
1
0
1
E
4
0 0
0
0
0
Data yang terdapat dalam suatu row, dapat menyatakan outdegree simpul yang bersangkutan 4
Representasi Graph 1. Representasi Graph dalam bentuk Matrix c. Inverse Adjacency Matrix Graph Berarah (Directed Graph) dari
B
C
A D
E
Menuju ke
A B
C
D
E
0 1
2
3
4
A
0
0 1
0
0
0
B
1
1 0
1
0
0
C
2
0 1
0
1
0
D
3
1 0
1
0
0
E
4
0 1
1
1
0
Perbedaan pokok dengan adjacency matrix adalah : 1. Data yang ada dalam suatu row, menyatakan indegree 2. Data yang ada dalam column, menyatakan outdegree 5
Representasi Graph
1. Representasi Graph dalam bentuk Matrix d. Adjacency Matrix Graph Berbobot Tak Berarah (Weighted Undirected Graph) 3
B
5
6
8
4
D
3
B
C
D
E
0
1
2
3
4
A 0
0
5
999
4
999
B 1
5
0
3
999
12
C 2
999
3
0
8
6
D 3
4
999
8
0
3
E 4
999
12
6
3
0
C
12
A
A
E
Dua buah simpul yang tidak berhubungan langsung atau tidak dihubungkan langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga.
6
Representasi Graph
1. Representasi Graph dalam bentuk Matrix e. Incidence Matrix Graph Tak Berarah V2 V1
e3
B
e1
C
e4
A
e5
e2
D V4
e7 e6
E V5
V3
e1
e2
e3
e4
e5
e6
e7
0
1
2
3
4
5
6
A 0 1
1
0
0
0
0
0
B 1 1
0
1
1
0
0
0
C 2 0
0
1
0
1
0
1
D 3 0
1
0
0
1
1
0
E 4 0
0
0
1
0
1
1
Matrix n * m n = jumlah simpul ; m = jumlah busur
7
Representasi Graph
1. Representasi Graph dalam bentuk Matrix e. Incidence Matrix Graph Tak Berarah e1
e2
e3
e4
e5
e6
e7
0
1
2
3
4
5
6
A 0 1
1
0
0
0
0
0
B 1 1
0
1
1
0
0
0
C 2 0
0
1
0
1
0
1
D 3 0
1
0
0
1
1
0
E 4 0
0
0
1
0
1
1
Busur yang ada hubungan dengan simpul B adalah busur: e1, e3 dan e4. Angka 1 menunjukan bahwa dari simpul B keluar 3 buah busur e1, e3 dan e4.
Simpul yang dihubungkan oleh e2 adalah simpul A dan D 8
Representasi Graph
1. Representasi Graph dalam bentuk Matrix f. Vector Matrix Graph Tak Berarah V2 V1
e3
B
e1
C
e4
A
e5
e2
D V4
V3
e7 e6
E V5
e
e
e
e
0
1
2
3
A 0 1
2
0
0
B 1 1
3
4
0
C 2 3
5
7
0
D 3 2
5
6
0
E 4 4
6
7
0
Simpul C Berhubungan dengan busur : e3, e4, dan e7
Ukuran Matrix : n * (n-1) n = jumlah simpul ; (n-1) = jumlah maksimum busur yang mungkin incedence dengan sebuah simpul 9
Representasi Graph
2. Representasi Graph dalam bentuk Linked-List a. Adjacency List Graph Tak Berarah FIRST
e3
B
e1
C
e4
A
e5
e2
D
e6 e7
E
Simpul dituliskan sesuai dengan urutan abjad.
A B C D E
B
D 0
A
C
E 0
B
D
E 0
A
C
E 0
B
C
D 0
10
Representasi Graph
2. Representasi Graph dalam bentuk Linked-List b. Adjacency List Graph Berbobot Tak Berarah FIRST
3
B
5
C
12
A
8
2
D
2 7
E
Sama dengan adjacency List Graph Berarah dimana arh busurnya selalu berpasangan.
A B C D E
B 5
D 2 0
A 5
C 3
E 12 0
B 3
D 8
E 2 0
A 2
C 8
E 7 0
B 12
C 2
D 7 0
11
Representasi Graph
2. Representasi Graph dalam bentuk Linked-List c. Adjacency List Graph Berbobot Dan Berarah FIRST
3
B
6 5
A
C
14 9
12
2
D
7
E
A B C D E
B 5
D 2 0
A 6
C 3 0
E 9 0 C 12
E 7 0
B 14 0
12
Representasi Graph
2. Representasi Graph dalam bentuk Linked-List d. Inverse Adjacency List Graph Berbobot Dan Berarah FIRST
3
B
6 5
A
C
14 9
12
2
D
7
E
A B C D E
B 6 0 A 5
E 14 0
B 2
D 12 0
A 2 0 C 9
D 7 0
13
Penelusuran Graph (Graph Traversal) Penelusuran Graph maksudnya mengunjungi (visit) atau membaca Graph menurut arah tertentu, simpul per simpul, mulai dari simpul tertentu sampai semua simpul dikunjungi tanpa ada simpul yang dikunjungi atau dibaca lebih dari satu kali. Ada 2 macam penelusuran : 1. Depth First Search (DFS), penelusuran dengan mendahulukan arah kedalaman 2. Breadth First Serch (BFS), penelusuran dengan mendahlukan arah melebar
14
Penelusuran Graph (Graph Traversal) 1. Depth First Search
Depth First Search (DFS), penelusuran graph yang arah penelusurannya mendahulukan ke arah kedalaman graph tersebut.
A B D
C E
F
H Graph G
G
A
B
C
D
E
F
G
H
0
1
2
3
4
5
6
7
A 0 0
1
1
0
0
0
0
0
B 1 1
0
0
1
1
0
0
0
C 2 1
0
0
0
0
1
1
0
D 3 0
1
0
0
0
0
0
1
E 4 0
1
0
0
0
0
0
1
F 5 0
0
1
0
1
0
0
1
G 6 0
0
1
0
0
0
0
1
H 7 0
0
0
1
1
1
1
0
Adjacency Matrix Graph G 15
Penelusuran Graph (Graph Traversal) 1. Depth First Search
Depth First Search (DFS), penelusuran graph yang arah penelusurannya mendahulukan ke arah kedalaman graph tersebut.
A
A
B D
C E
F
B G
D
C E
F
G
H
H
Graph G
Hasil penelusuran secara DFS Graph G 16
Penelusuran Graph (Graph Traversal) 1. Depth First Search
Dalam proses penelusuran, akan terlihat nanti pada suatu titik, 'terpaksa' dilakukan langkah kembali ke simpul sebelumnya. Dalam pemrograman, untuk dapat kembali ke posisi sebelumnya, biasanya diperlukan stack. Pada penelusuran, kita menggunakan stack S, dengan jumlah elemen tidak kurang dari jumlah simpul graph yang ditelusuri. Awal penelusuran: 1. Misal penelusuran dimulai dari simpul A. Ambil A. Simpan (Push) A ke Stack S. 2. A berhubungan dengan B dan C. Ambil B dan simpan B ke stack. Simpul B dinyatakan lebih dulu dari simpul C.
B
A
Top
A S
A
B A S
17
Penelusuran Graph (Graph Traversal) 2. Breadth First Search
Breadth First Search (BFS), penelusuran graph yang arah penelusurannya mendahulukan ke arah 'lebar' graph tersebut.
A B D
C E
F
H Graph G
G
A
B
C
D
E
F
G
H
0
1
2
3
4
5
6
7
A 0 0
1
1
0
0
0
0
0
B 1 1
0
0
1
1
0
0
0
C 2 1
0
0
0
0
1
1
0
D 3 0
1
0
0
0
0
0
1
E 4 0
1
0
0
0
0
0
1
F 5 0
0
1
0
1
0
0
1
G 6 0
0
1
0
0
0
0
1
H 7 0
0
0
1
1
1
1
0
Adjacency Matrix Graph G 18
Penelusuran Graph (Graph Traversal) 2. Breadth First Search
Breadth First Search (BFS), penelusuran graph yang arah penelusurannya mendahulukan ke arah 'lebar' graph tersebut.
A
A
B D
C E
F
H Graph G
B G
D
C E
F
G
H Hasil penelusuran secara BFS Graph G 19
Penelusuran Graph (Graph Traversal) 2. Breadth First Search
Proses penelusuran: Diperlukan sebuah array untuk antrian (Queue) yang diberi nama Q yang jumlah elemenya tidak kurang dari jumlah simpul. Awal penelusuran:
R
1. Misal penelusuran dimulai dari simpul A. Simpan A ke antrian Q. Pointer F dan R menunjuk ke A. 2. A berhubungan dengan B dan C. Ambil dan kunjungi semuanya. Simpan B dan C ke dalam antrian. R menunjuk yang terakhir yaitu C.
0 1 2 3 4 5 6 7
A
Q A F R 0 1 2 3 4 5 6 7
A
Q A B C F
B
C
20
