STRUKTUR DATA By : Sri Rezeki Candra Nursari
2 SKS
Literatur • Sjukani Moh., (2007), “Struktur Data (Algoritma & Struktur Data 2) dengan C, C++”, Mitra Wacana Media • Utami Ema. dkk, (2007),”Struktur Data (Konsep & Implementasinya Dalam Bahasa C & Free Pascal di GNU/Linux)”, Graha Ilmu • Hubbard Jhon, R., Ph.D, (2000), “Schaum’s Outline Of Theory and Problems of Data Structures With C++” McGraw-Hill • Bambangworawan Paulus., (2004), “Struktur Data Dengan C”, Andi Yogyakarta
Materi 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Data dan Struktur Data Array Struktur dan Record Pointer Linked List Stack (Tumpukan) Queue (Antrian) Tree (Pohon) AVL Tree Heap dan B-Tree Sorting Search Hashing Graph
GRAPH Pertemuan 15
2 SKS
GRAPH • Sekumpulan elemen yang saling berhubungan – Sebuah elemen yang dapat terhubung dengan beberapa elemen lain – Beberapa elemen dapat terhubung ke beberapa elemen yang lain
• Graph terdiri dari node/vertex/titik dan edges/arc/busur • Graph tidak memiliki root node
GRAPH • Graph, termasuk struktur non linear • Graph adalah kumpulan dari simpul dan busur yang secara matematis dapat dinyatakan sebagai berikut: – G = (V, E) • G = Graph • V = Simpul/vertex/node/titik • E = Busur/edge/arc
• Graph dibedakan menjadi 2 macam: 1. Graph tak berarah (undirect graph/non-direct graph) 2. Graph berarah(direct graph/digraph)
GRAPH TAK BERARAH • Graph tak berarah (undirect graph/non-directed graph) • Urutan simpul pada busur e1, dapat disebut busur A,B atau B,A • Diidentikkan dengan sebuah jalan yang menghubungkan dua buah titik, yang dapat dilalui 2 arah B v2 e1
e3 e4
v1 A
C v3
e5 e2
e7
D v4
E e6
v5
GRAPH TAK BERARAH • Graph tak berarah biasa juga disebut tipe data abstract graph • Merupakan sekumpulan node yang saling terhubung melalui edges • Setiap edge menghubungkan dua node. Tidak semua node harus saling terhubung
GRAPH BERARAH • • • •
Graph berarah (directed graph) Busur A,B adalah busur e1 Busur B,A adalah busur e8 Diidentikkan apabila dari A ke B dapat menggunakan jalan e1, sedangkan dari B ke A hanya menggunakan jalan e8 e8
e9
B v2 e1
v1 A
e4
C v3
e10 e2
e3
e5
e7
D v4
E e6
v5
ISTILAH-ISTILAH GRAPH 1. Incident 2. Degree/derajat, indegree dan outdegree 3. Adjacent 4. Successor dan Predecessor 5. Path 6. Cycle
1. INCIDENT • Apabila 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 B e v
A
w
2. DEGREE, INDEGREE, OUTDEGREE • Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut. • Degree simpul A atau v1=2 • Degree simpul B atau v2=3 B v2 e1
e3 e4
v1
A
C v3
e5 e2
e7
D v4
E e6
v5
2. DEGREE, INDEGREE, OUTDEGREE • Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya (head) incident pada simpul tersebut atau dapat dikatakan jumlah busur masuk atau menuju simpul tersebut B v2 e1
e3 e4
v1
A
C v3
e5 e2
e7
D v4
E e6
v5
2. DEGREE, INDEGREE, OUTDEGREE • Outdedegree sebuah simpul pada graph berarah adalah jumlah busur yang buntutnya (tail) incident pada simpul tersebut atau dapat dikatakan jumlah busur yang keluar atau berasal dari simpul tersebut e B v e 2
1
3
e4 v1
A
C v3
e5 e2
e7
D v4
E e6
v5
3. ADJACENT • Pada graph tak berarah, dua simpul tersebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut – Simpul v dan simpul w disebut adjacent
• Pada graph berarah, sebuah simpul v disebut adjacent dengan simpul w apabila ada busur dari w ke v B – Simpul v adjacent dgn simpul w v
w
e
B e
A v
A
w
4. SUCCESSOR dan PREDECESSOR • Pada graph berarah, bila simpul v adjacent dengan simpul w • Simpul v adalah successor (pengganti/ pelanjut) simpul w • Simpul w adalah predecessor (pendahulu) dari simpul v B e v
A
w
5. PATH • Sebuah path adalah serangkaian (a sequence) simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya • Menggambarkan path dari simpul 1 ke simpul 4 1
2
3
4
6. CYCLE • Cycle adalah path yang terdiri dari sekurang-kurangnya 3 simpul sedemikian rupa simpul yang terakhir adjacent dengan simpul pertama • Menggambarkan cycle 4 buah simpul pada graph tak berarah 1
2
3
4
REPRESENTASI GRAPH • Agar data yang ada dalam grpah dapat diolah, maka graph harus dinyatakan dalam suatu struktur data yang dapat mewakili graph tersebut • Graph perlu direpresentasikan kedalam bentuk array dua dimensi yang sering juga disebut matrix, atau direpresentasikan dalam bentuk linked list
REPRESENTASI GRAPH • Representasi graph dalam bentuk matrix 1. 2. 3. 4.
Adjacency matrix Inverse adjacency matrix) Insidence matrix Vector matrix
• Representasi graph dalam bentuk Link List 1. Adjacency list 2. Inverse adjacency list
Kisi-kisi UAS 1. Jumlah soal = 5 2. Materi dari setelah UTS (tree, avl, heap, btree, sort, search, graph) 3. Soal memperbaiki koding ada 2 soal 4. Perbaikan koding (sort & search) 5. Dua soal dalam bentuk teori 6. Satu soal materi Graph
