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



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



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



• 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



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.



• 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.



• 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.



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.



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.



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.



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



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



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



• 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



• Define struct untuk sebuah simpulyang dapat digunakan sebagaivertex maupun edge.

typedef struct tipeS {

tipeS *Left;

int INFO;

tipeS *Right;

};

tipeS *FIRST, *PVertex, *PEdge;



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



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



Adjency List graph berarah

A

C

D

B

E

D

A

B

C

E

C

B

E

B

A C

D E



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.



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



Hasil :



Next

• Fungsi Rekursif

struktur data graf

Documents