2013 struktur data by andi arfian 1

graph

3/12/2013

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 3/12/2013


2

Contoh sebuah graph v2 Simpul=Titik.node,vortex(V)

B e3

e1 v1

C v3

e4

A

V=v1,v2,,,,,v5 Busur =arc,egde (E) E1,e2,,,,e7

e5

e2

e7 E

D v4

3/12/2013

e6

v5


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

3/12/2013


4

Terminologi GRAPH adalah suatu struktur data yang berbentuk network/jaringan dimana hubungan antara elemen-elemennya adalah many-tomany. 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

3/12/2013


5

Terminologi SIMPLE PATH Jika node dalam path tersebut hanya muncul 1 kali.

B

D

A

B F

C

A

D F

E A-F

3/12/2013


6

Terminologi CYCLE GRAPH Jika node pertama dan node terakhir dalam GRAPH adalah sama.

B A

C

3/12/2013


7

Tipe  Directed GRAPH (DiGraph)/ berarah  Undirected GRAPH/tidak berarah  Connected GRAPH  Unconnected GRAPH  Weighted GRAPH/berbobot  Unweighted GRAPH

3/12/2013


8

Directed Graph Jika sepasang node yg membentuk edge dalam GRAPH mempunyai arah/arti B A

C

Directed Graph

3/12/2013


9

Contoh direct graph Busur ab adalah satu busur.

b

Busur b->a dengan busur lainnya

c

a

d

3/12/2013

e


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 B A

C

Undirected Graph

3/12/2013


11

Connected Graph/terhubung Bila setiap pasang node punya hubungan di antara keduanya dalam GRAPH.

B

D

A

F C

E

Connected Graph

3/12/2013


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

a

Dimana m=jumlah busur N=jumlah simpul

d

e

Terlihat : untuk simpul n=5, maka busur m=5(5-1)/2=10

3/12/2013


13

Unconnected Graph Bila terdapat SubGraph yang terisolasi.

B

D

A

F C

E

Unconnected Graph

3/12/2013


14

Weighted Graph Jika semua edge dalam GRAPH diberi nilai.

A

4 2

B

5

C 3 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

3/12/2013


15

Graph berlabel hubungan dengan jarak dan diameter

 Graph berbobot adalah graph yang diberikan bobot disetiap garisnya.bobot tersebut bisa merupakan pengambaran suatu besaran mengenai jarak,biaya atau apa saja(Sesuai aplikasi yang akan dibahas) f 5 a 4

Jarak antara dua titik didalam graphadalah jalur terpendek yg menghubungkan kedua simpul tersebut

3 5

b

7

4

d

e 6

Diameter Graph (Terhubung) adalah nilai maksimum dari jarak(antara dua titik) yang ada didalam graph Ex, dari titik D menuju titik F minimal dapat dilakukan sebayak 2 langkah(sehingga,jarak D ke F adalah 2) 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 jarakjarak tersebut.

3/12/2013


16

Unweighted Graph Jika semua edge dalam GRAPH tidak ada nilai. A

C

B

D

Weighted Graph

3/12/2013


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

3/12/2013

Graph G1

Graph G2 Graph G1 adalah subgraph dari G


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

Sebuah multigraph karena ada garis e1dan e2 yang menghubungkan titik A dan B atau terdapat Loop e5 di titik C

e6

e8

e7

a

c e2

e4

e5 e3

e1

b multigraph 3/12/2013


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 trail.panjang(Leght) dari sebuah path adalah banyaknya garis yang dilalui

3/12/2013


20

Smr

Walk terbuka ,path dan trail

Sby

•Titik Jkt,Bdg,Yog,Smr dan S by Jkt

Walk Tebuka Bdg

Yog

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 3/12/2013


21

Diskusi A B

D

C

E

F

Apakah tree tersebut juga merupakan Graph ? Jika merupakan Graph, termasuk dalam tipe yang mana ?

3/12/2013


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. 3/12/2013


23

Adjacency B

D

A

F C

E

Undirected Graph

NODE A B C D E A 0 1 1 0 0 B 1 0 1 1 1 C 1 1 0 0 1 D 0 1 0 0 1 E 0 1 1 1 0 F 0 0 0 1 1 Adjacency Matrix 3/12/2013

F 0 0 0 1 1 0

NODE A B C D E F


EDGE LIST B C A C D E A B E B E F B C D F D E Adjacency List 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.

3/12/2013


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

3/12/2013


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

3/12/2013


27

Contoh Traversal B

D

A

F

C

E

Undirected Graph

BFT ? DFT ?

3/12/2013

NODE A B C D E F


EDGE LIST B C A C D E A B E B E F B C D F D E Adjacency List

28

BFT start node A Langkah Node_N 1 2 3 4 5 6 7 8 9 10 11 12 13 3/12/2013

QUEUE

A A A B B C C D D E E F

B-C C C-D-E D-E D-E E E-F F F

A 1 2 3 3 3 3 3 3 3 3 3 3 3

Status Node B C D E 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 3 2 1 1 3 2 2 2 3 3 2 2 3 3 2 2 3 3 3 2 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3


F 1 1 1 1 1 1 1 1 1 2 2 2 3

Hasil

A A A-B A-B A-B-C A-B-C A-B-C-D A-B-C-D A-B-C-D-E A-B-C-D-E A-B-C-D-E-F 29

Selesai 3/12/2013


30

3/12/2013


31

3/12/2013


32

3/12/2013


33

3/12/2013


34

3/12/2013


35

3/12/2013


36

2013 struktur data by andi arfian 1

Recommend Documents