Graph_matakuliah_algoritma_dan_struktur.pdf

GRAPH Matakuliah Algoritma dan Struktur Data Annisa Puspa Kirana, S.Kom, M.Kom

Target Study 

Pengantar  Definisi  Contoh  Istilah



Jenis Graph  Undirected Graph  Directed Graph (Digraph)  Weight Graph

Target Study Cont…

 Representasi graph  Adjacency Matrix  Adjacency Lists  Metode Penelusuran Graph  DFS (Depth First Search) : Pencarian Mendalam  BFS (Breadth First Search) : Pencarian Melebar  Minimum Spanning Tree  Algoritma Kruskal  Algoritma Solin

DEFINISI GRAPH 

Graph adalah struktur data yang memiliki relasi many to many, yaitu tiap element dapat memiliki 0 atau lebih dari 1 cabang.



Graph terbentuk dari 2 bagian, yaitu node dan edge.



Node : digunakan untuk menyimpan data



Edge : cabang, untuk menghubungkan node satu dengan node lain.

DEFINISI GRAPH CONT… 

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

GRAPH 

Sebuah graph mungkin hanya terdiri dari satu simpul



Sebuah graph belum tentu semua simpulnya terhubung dengan busur



Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain



Sebuah graph mungkin semua simpulnya saling berhubungan

CONTOH GRAPH 

Jaringan pertemanan pada Facebook. Nina Firda

Riza

Toni

Joko Ale

Graph dengan 6 node dan 7 edge yang merepresentasikan jaringan pertemanan pada Facebook

PENJABARAN 

Jika => G = (N,E)



Dimana : G adalah Graph, N adalah Node, dan E adalah Edge.



Sehingga dari contoh graph facebook tersebut dapat dijabarkan: N = {Nina, Toni, Ale, Riza, Joko, Firda} E = {{Nina,Toni},{Toni,Riza},{Nina, Riza}, {Toni,Ale}, {Ale,Joko},{Riza,Joko},{Firda,Joko}}

*N: para anggota Facebook E : pertemanan antara member satu dengan yang lain.

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” pada e, dan e disebut incident dengan v dan w. Degree (derajat)

Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.

ISTILAH PADA GRAPH CONT… Indegree Jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut. Outdegree

Jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.

ISTILAH PADA GRAPH CONT.. Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent. Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v. e

w

v

e v

w

ISTILAH PADA GRAPH CONT.. Successor dan Predecessor

Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

Path Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

1

2

3

4

1

2

1

2

1

2

4

3

4

3

4

3

CONTOH GRAPH vertex v2

V terdiri dari v1, v2, …, v5

B

e1

v1

A

e4

e3

C v3

edge

e2 v4 D

e5

e6

E terdiri dari e1, e2, … , e7

e7

E

v5

Undirected graph

JENIS GRAPH 

Graph dibedakan menjadi beberapa jenis, antara lain :

1.

Undirected Graph

2.

Directed Graph (Digraph)

3.

Weight Graph

UNDIRECTED GRAPH 

Biasa disingkat : undi-graph.



Yaitu graph yang tidak memiliki arah.



Setiap sisi berlaku dua arah.



Misalkan : {x,y} Arah bisa dari x ke y, atau y ke x.



Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

U

V

{U,V} atau {V,U}

GAMBAR UNDI-GRAPH

Notasional G = {V, E}

V = {A, B, C, D, E, F, G, H, I,J, K, L, M} E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E},

{D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}.

Contoh Undi-Graph 2

3

1 4

5

6

7

Directed Graph 

Biasa disingkat : Di-graph.



Yaitu graph yang memiliki arah.



Setiap edge Digraph memiliki anak panah yang mengarah ke node tertentu.



Secara notasi sisi digraph ditulis sebagai vektor (u, v). u = origin (vertex asal) v = terminus (vertex tujuan)

u

v

Gambar Digraph

Notasional G = {V, E} V = {A, B, C, D, E, F, G, H, I,J, K, L, M} E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M),

(L,K), (L,M)}.

Contoh Digraph 2

3

1 4

5

6

7

GRAPH BERARAH DAN GRAPH TAK BERARAH B

e8 e1

v1

A e2

e10

D

v4

v2

v2 e3 e4

e5 e6

B

e9

C

e1 v3

e7

E v5

Directed graph

v1

e3 e4

A e2

C v3

e5

v4 D

e6

e7

E

v5

Undirected graph

Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul.

GRAPH BERBOBOT (WEIGHTED GRAPH)  Jika

setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.

 Bobot

sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

 Graph

nilai.

yang memiliki bobot, yaitu pada tiap edge-nya memiliki

CONTOH WEIGTH GRAPH A 2 E

2 D 2 4

5

B

4

F C

GRAPH BERBOBOT B

4 5

v1

A e2

12

8 v4

B

7 3

10

D

v2

v2

3

5

C

v3

6

E v5

Directed graph

v1

3 12

A 4 v4 D

C v3

8

3

6

E

v5

Undirected graph

Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.

Representasi Graph 

1.

Representasi graph dibedakan menjadi 2 : Adjacency Matrix dapat direpresentasikan dengan matriks (array 2 Dimensi).

2.

Adjacency Lists dapat direpresentasikan dengan array (bukan berupa matriks) maupun linked list.

Adjacency Matrix 

Representasi Graph berupa Matrik ordo nxn. dimana n = node.  Baris berisi Node asal, sedangkan kolom berisi Node tujuan.  Jika graph tidak berbobot,maka nilai matriks diisi dengan 1 atau 0. nilai 1 jika ada edge, dan 0 jika tidak ada edge antar node. A(i,j) = 1, jika antara node i dan node j terdapat edge/terhubung.  Jika graph berbobot, maka nilai matriks diisi dengan bobot dari edge. A(i,j) = nilai bobot.

Undi-graph

j 2

3

1 4

i 5

1

2

3

4

5

1

0

1

0

1

0

2

1

0

0

0

1

3

0

0

0

0

1

4

1

0

0

0

1

5

0

1

1

1

0

•Diagonal entries are zero.

•Adjacency matrix of an undirected graph is symmetric. A(i,j) = A(j,i) for all i and j.

Adjacency Matrix

j 2

3

1 4

i 5

1

2

3

4

5

1

0

1

0

1

0

2

1

0

0

0

1

3

0

0

0

0

1

4

1

0

0

0

1

5

0

1

1

1

0

Di-graph

j 2

3

1 4



i 5

1

2

3

4

5

1

0

0

0

1

0

2

1

0

0

0

1

3

0

0

0

0

0

4

0

0

0

0

1

5

0

1

1

0

0

Dimungkinkan tidak simetris jika terdapat loop.

REPRESENTASI GRAPH DALAM BENTUK MATRIX 

Adjacency Matrix Graph tak berarah Urut abjad

A 0

B 1

C 2

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

B

A

C

D Graph

E

D 3

E 4

Degree simpul : 3

REPRESENTASI GRAPH DALAM BENTUK MATRIX 

Adjacency Matrix Graph berarah ke dari

B

A

C

D

E Graph

A 0

B 1

C 2

D 3

E 4

0

1

0

1

0

1

0

1

0

1

A

0

B

1

C

2

D

3

0

1

0

1

1

E

4

0

0

1

0

1

0

0

0

0

0

out

in

REPRESENTASI GRAPH DALAM BENTUK LINKED LIST 

Adjency List graph tak berarah



Digambarkan sebagai sebuah simpul yang memiliki 2 pointer.



Simpul vertex :

left

info

Simpul edge :

right

left

info

Menunjuk ke simpul edge pertama Menunjuk ke simpul vertex berikutnya, dalam untaian simpul yang ada.

Menunjuk ke simpul vertex tujuan yang berhubungan dengan simpul vertex asal.

right Menunjuk ke simpul edge berikutnya, bila masih ada.

Adjacency List 

Direpresentasikan dengan linked list atau array.  Array

list : array dua dimensi namun tidak ber-ordo nxn.

 Linked

list : array of single linked list

Array Lists 2

3

1

aList[1] = (2,4) aList[2] = (1,5)

4

5

aList[3] = (5)

aList[4] = (5,1) aList[5] = (2,4,3)

Adjacency Lists (Linked List) 2

3

1 4

5

aList [1]

2

4

[2]

1

5

[3]

5

[4]

5

1

[5]

2

4

3



Define struct untuk sebuah simpul yang dapat digunakan sebagai vertex maupun edge. typedef struct tipeS { tipeS *Left; int INFO; tipeS *Right; };

tipeS *FIRST, *PVertex, *PEdge;

CONTOH : UNTUK VERTEX A, MEMILIKI 2 EDGE YANG TERHUBUNG YAITU E1 DAN E2.

e1

Urut abjad

B e4

e3

A e2

e5

D

e6

A C

B

e7

C

E D

Graph E

e1

e2

Gambar di atas dapat disusun dengan lebih sederhana, sbb :

B

A

C

D Graph

E

A

B

D

B

A

C

E

C

B

D

E

D

A

C

E

E

B

C

D

ADJENCY LIST GRAPH BERARAH

B

A

C

D

E

A

B

D

B

A

C

C

E

D

C

E

B

E

GRAPH BERARAH DAN BERBOBOT A 0

B

6

3

5

14

A 2

C 12

12

D

7

E

A

0

B

1

C

2

D

3

E

4

B 1

0 5 6 0 0 0 0 0 0 14

C 2

D 3

E 4

0 3 0 12 0

2 0 0 0 0

0 0 9 7 0

Perhatikan pemilihan nilai 0.

Penelusuran Graph

Metode Penelusuran 

Graph Traversal : Mengunjungi tiap simpul/node secara sistematik.



Metode : 

DFS (Depth First Search) : Pencarian Mendalam



BFS (Breadth First Search) : Pencarian Melebar

Algoritma BFS 

BFS diawali dengan vertex yang diberikan, yang mana di level 0.



Dalam stage pertama, kita kunjungi semua vertex di level 1.



Stage kedua, kita kunjungi semua vertex di level 2. Disini vertex baru, yang mana adjacent ke vertex level 1, dan seterusnya.



Penelusuran BFS berakhir ketika setiap vertex selesai ditemui.

Langkah-langkah algoritma BFS 1) Masukkan simpul ujung (akar) ke dalam antrian 2) Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi 3) Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan. 4) Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian 5) Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan 6) Ulangi pencarian dari langkah kedua

Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1. Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1 Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

Breadth First Search (BFS)

Urutan verteks hasil penelusuran :

Penerapan BFS

Contoh BFS Diketahui sebuah kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar kota dibentuk dengan sebuah graph

Pertanyaan: sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal perjalanan adalah kota no. 1. Gunakan algoritma BFS!

Pembahasan Contoh Maka dengan menggunakan algoritma BFS, rute tercepat yang didapat adalah sebagai berikut: 1–2–3–4–5–6–7–8 1. Pertama-tama, pointer menunujuk pada daun yang ada sebelah kanan, yaitu no.2 (1 – 2) 2. Setelah itu, proses dilanjutkan pada tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada tetangga terdekat, yakni no.4 (1-2-3-4). 3. Pointer mencari tetangga no.4, namun karna tidak ada, maka pointer kembali ke kota no.2 dan masuk ke daun berikutnya, yakni no.5. 4. Proses diulang hingga pointer menunjuk angka 8

Depth First Search (DFS) 

Pada setiap pencabangan, penelusuran verteks-verteks yang belum dikunjungi dilakukan secara lengkap pada pencabangan pertama, kemudian selengkapnya pada pencabangan kedua, dan seterusnya secara rekursif.

Urutan verteks hasil penelusuran :

Depth First Search (DFS)

Depth First Search (DFS)

….

….

Algoritma DFS 

Traversal dimulai dari simpul v.



Algoritma: 1.

Kunjungi simpul v,

2.

Kunjungi simpul w yang bertetangga dengan simpul v.

3.

Ulangi DFS mulai dari simpul w.

4.

Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.

5.

Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi.

Minimum Spanning Tree (MST) Pencarian biaya yang minimum dari suatu graph sehingga membentuk pohon . Syarat Graph yang dapat dicari minimum spanning treenya : a.

Graph harus terhubung

b.

Ruasnya punya bobot

c.

Graph tidak berarah

Algoritma yang dipakai untuk menentukan minimum spanning tree : a.

Algoritma Kruskal

b.

Algoritma Solin

Aplikasi MST / Pohon Rentangan Minimum 

Dalam aplikasinya problem ini misalnya :  Hendak

direntangkan jaringan kabel listrik yang menghubungkan sejumlah lokasi dengan panjang kabel yang digunakan sependek-pendeknya mungkin.

 Melihat

pengelompokan data yang tersebar pada suatu

ruang.  Perencanaan

jaringan transportasi/distribusi barang.

Algoritma Kruskal 

Himpunan sisi dari G diurutkan membesar sesuai bobot sisi tersebut.



Buat T dengan memasukan 1 sisi terpendek dari G tersebut.



Ulang (banyak sisi T = (banyak simpul G)-1) 

Ambil sisi selanjutnya dari G.



Jika sisi itu tidak membuat sirkuit di T  Masukan

sisi itu ke T

 Masukan

simpul-simpul sisi itu ke T



Pseudo-code algoritma kruskal

Algoritma solin Algoritma Solin untuk MST merupakan kebalikan dari algoritma Kruskal, yaitu membuat tree didahului dengan melakukan pengurutan garis dari garis yang mempunyai bobot terbesar.

Contoh

Penyelesaian dengan Algoritma Solin

Penyelesaian dengan Algoritma Solin Cont..

Penyelesaian dengan Algoritma Kruskal

Implementasi Program

Operasi-operasi Menggunakan adjacency matriks, operasi-operasinya sebagai berikut : 1.

Deklarasi

2.

Inisialisasi

3.

Penambahan node

4.

Penambahan edge

5.

Menandai Node

6.

Traversal

7.

Display node

Contoh Program 

Deklarasi

public class AdjacencyMatriksGraph { private final int MAX_VERTS = 20; private Vertex vertexList[]; private int adjMat[][]; private int nVerts; private StackX theStack; private Queue theQueue;

Contoh Program 

Inisialisasi

public AdjacencyMatriksGraph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int j=0; j<MAX_VERTS; j++) // set adjacency for(int k=0; k<MAX_VERTS; k++) // matrix to 0 adjMat[j][k] = 0; theStack = new StackX(); theQueue = new Queue(); }

Contoh Program 

Tambah Node

public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); }

Contoh Program 

Tambah Edge

public void addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; }

Contoh Program 

Menandai Node public int getAdjUnvisitedVertex(int v) { for(int j=0; j


DFS

public void dfs() // depth-first search { // begin at vertex 0 vertexList[0].wasVisited = true; // mark it displayVertex(0); // display it theStack.push(0); // push it while( !theStack.isEmpty() ) // until stack empty, { int v = getAdjUnvisitedVertex( theStack.peek() ); if(v == -1) // if no such vertex, theStack.pop(); else // if it exists, { vertexList[v].wasVisited = true; displayVertex(v); // display it theStack.push(v); // push it } } // end while for(int j=0; j


BFS

public void bfs() // breadth-first search { // begin at vertex 0 vertexList[0].wasVisited = true; // mark it displayVertex(0); // display it theQueue.insert(0); // insert at tail int v2; while( !theQueue.isEmpty() ) { int v1 = theQueue.remove(); // until it has no unvisited neighbors while( (v2=getAdjUnvisitedVertex(v1)) != -1 ) { // get one, vertexList[v2].wasVisited = true; // mark it displayVertex(v2); // display it theQueue.insert(v2); // insert it } // end while } // end while(queue not empty) // queue is empty, so we're done for(int j=0; j
Contoh Program 

Display Node

public void displayVertex(int v) { System.out.print(vertexList[v].label); }

Daftar Pustaka 

Kadir, Abdul. 2013. Teori dan Aplikasi Struktur Data menggunakan C++. Yogyakarta : Penerbit ANDI



Sartaj Sahni , “Data Structures & Algorithms”, Presentation L20-24.



Mitchell Waite, “Data Structures & Algorithms in Java”, SAMS, 2001