Download - Struktur Data Graf
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 1/26
STRUKTUR DATA (9)
Oleh Antonius Rachmat C, S.Kom,M.Cs
Dan Dra. Widi Hapsari, M.T
Struktur Data Graf
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 2/26
GRAPH
• Graph adalah kumpulan dari simpuldan busur yang secara matematis
dinyatakan sebagai :G = (V, E)
DimanaG = GraphV = Simpul atau Vertex, atau Node, atau TitikE = Busur atau Edge, atau arc
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 3/26
Contoh graph :
B
A C
D E
Undirectedgraph
vertex
edge
e1 e3e4
e7e5e2
e6
v1
v2
v4 v5
v3
V terdiri dari v1, v2, …, v5
E terdiri dari e1, e2, … , e7
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 4/26
• Sebuah graph mungkinhanya terdiri dari satusimpul
• Sebuah graph belum tentusemua simpulnyaterhubung dengan busur
• Sebuah graph mungkinmempunyai simpul yangtak terhubung dengan
simpul yang lain• Sebuah graph mungkin
semua simpulnya salingberhubungan
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 5/26
Graph Berarah dan Graph Tak
Berarah :B
A C
D E
B
A C
D E
Directedgraph
Undirectedgraph
e1 e3
e4
e7e5e2
e6
v1
v2
v4 v5
v3v1
v2
v3
v5v4
e1
e2
e3
e4
e5
e6
e7
e8 e9
e10
Dapat dilihat dari bentuk busur yang artinya urutanpenyebutan pasangan 2 simpul.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 6/26
• Graph tak berarah (undirected graphatau non-directed graph) :
• Urutan simpul dalam sebuah busur tidakdipentingkan. Mis busur e1 dapat disebutbusur AB atau BA
• Graph berarah (directed graph) :• Urutan simpul mempunyai arti. Mis busur
AB adalah e1 sedangkan busur BA adalah
e8.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 7/26
• Graph Berbobot (Weighted Graph)• Jika setiap busur mempunyai nilai yang
menyatakan hubungan antara 2 buahsimpul, maka busur tersebut dinyatakanmemiliki bobot.
• Bobot sebuah busur dapat menyatakan
panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yangmelalui sebuah jalan, dll.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 8/26
Graph Berbobot :
B
A C
D E
B
A C
D E
Directedgraph
Undirectedgraph
5 3
12
684
3
v1
v2
v4 v5
v3v1
v2
v3
v5v4
5
e2
312
8
3
6
4 7
10
Panjang busur (atau bobot) mungkin tidak digambarkan secarapanjang yang proposional dengan bobotnya. Misal bobot 5digambarkan lebih panjang dari 7.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 9/26
Istilah pada graph
Incident Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis
e=(v,w), maka v dan w disebut “terletak” padae, dan e disebut incident dengan v dan w.Degree (derajat), indegree dan outdegree
Degree sebuah simpul adalah jumlah busur yangincident dengan simpul tersebut.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 10/26
Indegree sebuah simpul pada graph
berarah adalah jumlah busur yangkepalanya incident dengan simpultersebut, atau jumlah busur yang “masuk”atau menuju simpul tersebut.
Outdegree sebuah simpul pada graphberarah adalah jumlah busur yangekornya incident dengan simpul tersebut,atau jumlah busur yang “keluar” atauberasal dari simpul tersebut.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 11/26
3. AdjacentPada graph tidah berarah, 2 buah
simpul disebut adjacent bila ada busuryang menghubungkan kedua simpultersebut. Simpul v dan w disebutadjacent.
Pada graph berarah, simpul v disebutadjacent dengan simpul w bila adabusur dari w ke v.
we
v
v
e w
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 12/26
4. Successor dan PredecessorPada graph berarah, bila simpul vadjacent dengan simpul w, maka simpulv adalah successor simpul w, dan simpulw adalah predecessor dari simpul v.
5. PathSebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacentsecara berturut-turut dari simpul satu ke
simpul berikutnya.1
43
2
4
2
4
2
4
21
3
1
3
1
3
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 13/26
Representasi Graph dalambentuk matrix• Adjacency Matrix Graph tak berarah
B
A C
D E
Graph
0 1 0 1 01 0 1 0 1
0 1 0 1 1
1 0 1 0 1
0 1 1 1 0
A B
A
0
B
C
1 2 43C D E
D
E
0
1
2
4
3
Urut abjad
Degree simpul : 3
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 14/26
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 15/26
• Adjency List graph tak berarah• Digambarkan sebagai sebuah simpul
yang memiliki 2 pointer.• Simpul vertex : Simpul edge :
Representasi Graph dalambentuk Linked List
info info
Menunjuk ke simpulvertex berikutnya,
dalam untaian simpulyang ada.
Menunjuk ke simpuledge pertama Menunjuk ke
simpul edgeberikutnya, bila
masih ada.Menunjuk ke simpulvertex tujuan yang
berhubungan dengansimpul vertex asal.
left right left right
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 16/26
• Define struct untuk sebuah simpulyang dapat digunakan sebagaivertex maupun edge.
typedef struct tipeS {
tipeS *Left;
int INFO;
tipeS *Right;
};
tipeS *FIRST, *PVertex, *PEdge;
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 17/26
Contoh : untuk vertex A, memiliki 2edge yang terhubung yaitu e1 dan e2.
A
C
D
B
E
e2
Graph
e1B
A C
D E
e1e3
e4
e7e5e2
e6
Urut abjad
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 18/26
Gambar di atas dapat disusun denganlebih sederhana, sbb :
A
C
D
B
E
D
A
B
A
B
C E
D E
C
C D
B
A C
D E
Graph
B
E
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 19/26
Adjency List graph berarah
A
C
D
B
E
D
A
B
C
E
C
B
E
B
A C
D E
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 20/26
Graph berarah danberbobot
B
A C
D E
5 3
2
14
12
6
7
12
0 5 0 2 06 0 3 0 00 0 0 0 90 0 12 0 7
0 14 0 0 0
A
A
0
B
C
1 2 43
D
E
0
1
2
4
3
B C D E
Perhatikan pemilihan nilai 0.
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 21/26
Penyelesaian kasus Graphhalaman sebelumnya :
• Define simpul untuk vertex dan edge• Mengidentifikasi Simpul pertama
sebagai vertex yang pertama• Tambahkan vertex sisanya• Tambahkan edge pada masing-
masing vertex yang telah terbentuk• Tampilkan representasi graphberikut bobotnya
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 22/26
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 23/26
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 24/26
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 25/26
Hasil :
8/14/2019 Struktur Data Graf
http://slidepdf.com/reader/full/struktur-data-graf 26/26
Next
• Fungsi Rekursif