Pertemuan 15:

Struktur Data

GRAPH & Persiapan UAS

 Informasi UAS dan TUGAS:
• Bahan UAS (close book): 70 menit
• Ujian Teori: • Ujian Praktek (salah satu):
1. Stack (Tumpukan) 1. STACK
2. Queue (Antrian) 2. QUEUE
3. Linked list (Senarai 3. TREE
Berantai)
4. Tree (Pohon)
5. Graf
6. Ada penggalan program
 SOAL LATIHAN
1. UAS
Buat fungsi menambah simpul/node dalam linked-list.
2. Buat fungsi menghapus data dalam antrian.
3. Buat fungsi preorder dalam pohon biner.
4. Tentukan traversal tree dari tree:
(a). A + B - ( C - D)^E + (F * G)
(b). A * B + C + D * (E + F) + (G - H / I) ^ J
5. Gambarkan pohon binernya dari traversal dari tree:
(a) Pre-Order: S E L A N G M U
(b) Post-Order: CENTURY
6. Gambarkan pohon binernya dari huruf/bilangan:
(a). DEWI ABG METU LORONG
(b). 90, 45, 55, 50, 40, 50, 60, 70, 40, 35, 30, 20,
80, 75, 85
7. Implementasikan sebuah single linked list yang dapat
merepresentasikan data mahasiswa berupa NIM, Nama,
Alamat dan No HP. Buatlah fungsi-fungsi untuk menelusuri,
menambah simpul dan menghapus simpul.
8. Buat program untuk menyiapkan array dua dimensi yang
akan digunakan untuk mengisi Stack S sebanyak 5 elemen,
bertipe karakter.
9. Buatlah algoritma yang dapat menampilkan data antrian
pasien masuk rumah sakit.
10. Buatlah algoritma yang dapat menyisipkan data di belakang
dalam model linked list seperti antrian mobil di kapal
penyeberangan (ferry). Penyisipan data adalah serentak.
11. Sebuah graf dengan 6 simpul, berapakah minimum dan
maksimum jumlah busur?
12. Jika ada 5 kota yang saling berdekatan dan terhubung jalur
darat, berapa jalur lintasan terpendek yang dapat dilakukan.
13. Buatlah program untuk menyetor simpanan ke bank dengan
menu pilihan: 1. Masukkan Antrian (nama, nomer rekening
dan jumlah setoran), 2. Proses Antrian, 3. Tampilkan
Antrian dan 4. EXIT. Input data adalah serentak.
14. Buatlah program yang dapat menentukan Pre-Order dan In-
Order jika nilai Post-Ordernya: 20 70 90 60 40 30 50
15. Buatlah program untuk menyimpan balok-balok kayu dalam
sebuah gudang berukuran panjang = 5 m, lebar 30 cm dan
tinggi 540 cm. Program harus dapat menampilkan menu : 1.
Masukkan data balok (kode balok, jenis balok dan jumlah
balok), 2. Proses, 3. View Balok dan 4. EXIT.
16. Buat program untuk (1) menyimpan, (2) menghapus dan
(3) cetak elemen dalam stack berupa huruf-huruf. Entry
data
adalah secara serentak.
17. Ubahlah notasi aritmatika PREFIX berikut ke notasi
 GRAPH
• Graph adalah kumpulan dari simpul dan
busur yang secara matematis dinyatakan
sebagai:
G = (V, E)
Dimana
G = Graph
V = Vertex, atau Simpul, atau Node, atau Titik
E = Edge, atau Busur, atau arc
 Contoh graph :
Ciri-Ciri Graph
v2 • Sebuah graph
vertex
B mungkin hanya
e1 e4 e3 terdiri dari
satu simpul
v1 A edge C v3 • Sebuah graph
mungkin
e5 e7 mempunyai simpul
e2
yang tak
E terhubung dengan
v4 D e6
v5 simpul yang lain
Gb. 1. Undirected graph
• Sebuah graph
mungkin semua
V terdiri dari v1, v2, …,
simpulnya saling
v5 E terdiri dari e1, e2, berhubungan
Gb. 2. Ciri graph
… , e7
 Graph Berarah dan Graph Tak Berarah
v2
v2
B e9 B
e8
e3 e1 e3
e1
e4 v3 e4
v1 A C v1 A C v3
e10
e2 e5 e7 e5 e7
e2

D e6 E v5 E
v4 v4 D e6
v5
Gb. 3. Directed graph Gb. 4. Undirected graph

Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan
2
simpul.
• Graph tak berarah (undirected graph atau non-
directed graph)
– Urutan simpul dalam sebuah busur tidak dipentingkan.
Misal busur e1 dapat disebut busur AB atau BA

• Graph berarah (directed graph)

– Urutan simpul mempunyai arti. Misal busur AB adalah
e1 sedangkan busur BA adalah e8.
• 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 Berbobot :
v2
v2
B 7 B
4
3 5 3
5
12 v3 v1 12
v1 A C A C v3
10
e2 6 4 8 6
8
D 3 E E
v4 v4 D 3
v5 v5
Gb. 5. Directed graph Gb. 6. Undirected graph

Panjang busur (atau bobot) mungkin tidak digambarkan secara

panjang yang proposional dengan bobotnya. Misal bobot 5
digambarkan lebih panjang dari 7.
 Istilah pada graph
1. 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.
2. Degree (derajat), indegree, dan outdegree
Degree sebuah simpul adalah jumlah busur yang incident dengan
simpul tersebut.
 Indegree sebuah simpul pada graph berarah adalah jumlah
busur yang kepalanya incident dengan simpul tersebut, atau
jumlah busur yang “masuk” atau menuju simpul tersebut.
 Outdegree sebuah simpul pada graph berarah adalah jumlah
busur yang ekornya incident dengan simpul tersebut, atau
jumlah busur yang “keluar” atau berasal dari simpul tersebut.
3.
Adjacent
Pada graph tidah berarah, 2 buah simpul
disebut adjacent bila ada busur yang
menghubungkan kedua simpul tersebut.
Simpul v dan w disebut adjacent.
e
w
v Gb. 7. Adjacent tak
berarah
Pada graph berarah, simpul v disebut
adjacent dengan simpul w bila ada busur dari
w ke v.
e w
Predecessor

v Gb. 8. Adjacent
Successor berarah
4. 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.
5. Path
Sebuah path adalah serangkaian simpul-simpul
yang berbeda, yang adjacent secara berturut-turut
dari simpul satu ke simpul berikutnya.
1 2 1 2 1 2 1 2

3 4 4 3 4 3 4
3
Gb. 9. Path berarah dan tak berarah
 Representasi Graph dalam bentuk
matrix
• Adjacency Matrix Graph tak berarah
Urut abjad A B C D E
1 2 3
B
0 4
A 0 0 1 0 1 0
A C B 1 1 0 1 0 1
C 2 0 1 0 1 1
D E D 3 1 0 1 0 1
E 4 0 1 1 1 0
Gb. 10. Graf tak berarah

Degree simpul : 3
 Representasi Graph dalam bentuk
matrix
• Adjacency Matrix Graph berarah
ke A B C D E
dari 1 2 3
B
0 4

A 0 0 1 0 1 0 out
A C (Baris)
B 1 1 0 1 0 1
C 2 0 1 0 1 1
D E D 3 0 0 1 0 1
Gb. 11. Graph berarah
E 4 0 0 0 0 0

in
(kolom
 Representasi Graph dalam bentuk
Linked List
• Adjency List graph tak berarah
• Digambarkan sebagai sebuah simpul yang
memiliki 2 pointer.
• Simpul vertex : Simpul edge :

left right left right

info Menunjuk ke simpul
info
edge pertama Menunjuk ke
simpul edge
Menunjuk ke simpul Menunjuk ke simpul berikutnya, bila
vertex berikutnya, vertex tujuan yang masih ada
dalam untaian simpul berhubungan
yang ada dengan simpul
vertex asal
 Contoh : untuk vertex A, memiliki 2 edge yang
terhubung yaitu e1 dan e2.

B Urut abjad
e1 A e1 e2
e3
e4
A C B

e2 e5 e7 C

D E
e6
D

Gb. 12. Graph tak berarah E

1. Gambar graph dapat disusun dengan lebih sederhana:

B A B D
E
B
A C
C. B D E
A

D. A C E
C

D E C D
E. B

B A B D

B A C

A C
C E

D C E

D E E B
Gb. 13. Adjency List graph
 Graph berarah dan berbobot

A B C D E
6 B
0 1 2 3 4
5
3 A 0 0 5 0 2 0
A 14 C B 1 6 0 3 0 0
C 2 0 0 0 0 9
2 13 12
D 3 0 0 13 0 7
D 7 E E 4 0 14 0 0 0
Gb. 14. Graph berbobot Perhatikan pemilihan nilai 0.
• Define struct untuk sebuah simpul yang dapat
digunakan sebagai vertex maupun edge.
• Deklarasinya:
typedef struct tipeS Penyelesaian kasus Graph
Gambar 14:
{
• Define simpul untuk vertex dan
tipeS *Left; edge
• Mengidentifikasi Simpul pertama
int INFO;
sebagai vertex yang pertama
tipeS *Right; • Tambahkan vertex sisanya
}; • Tambahkan edge pada masing-
tipeS *FIRST, masing vertex yang telah terbentuk
*PVertex, *PEdge; • Tampilkan representasi graph
berikut bobotnya
 Contoh 1: Dari Gambar 5*
#include<stdio.h> //Simpul Vertex yang
#include<iostream> pertama I=0;J=0;
#include<conio.h> P=new simpul;
using namespace P->INFO = NmS[0];
std; FIRST = P; LAST = P;
typedef struct tipeS P->Left = NULL; P-
{ struct tipeS >Right = NULL;
*Left; int INFO; PointS[0] = P; printf("\n
struct tipeS *Right; %c", P->INFO);
}; printf(" Alamat %d ",
PointS[0]);
typedef struct tipeS simpul; printf("\n");
//Simpul Vertex yang berikutnya
simpul *P,*FIRST,*LAST,*PVertex,*PEdge,*Q,*R,*S; for (I=1;I<=4;I++) {
simpul *PointS[5]; P = new simpul;
P->INFO = NmS[I];
int main() { LAST->Left = P;
int A[5][5] = {0,5,0,2,0, 6,0,3,0,0, 0,0,0,0,9, LAST = LAST->Left;
0,0,12,0,7, P->Left = NULL;
0,14,0,0,0}; P->Right = NULL;
char NmS[6] = "ABCDE"; PointS[I] = P;
int I, J; printf("\n %c ", P-
>INFO);
printf("Alamat %d \
n", PointS[I]);
}
//Simpu2 Edge untuk semua Vertex
Q = FIRST;
for (I=0; I<=4; I++)
{
R=Q;
printf("Vertex %c ...", Q->INFO); for
(J=0; J<=4; J++)
{
if(A[I][J]!=0)
{
P = new simpul;
P->INFO = A[I][J];
R->Right = P;
P->Left = PointS[J];
printf("berhubungan dengan %c: ", P->Left->INFO);
printf("bobot %d;", P->INFO);
P->Right = NULL; R =
P;
}
}
printf("\n");
Q = Q->Left;
}
}

Outputnya:
 Contoh 2: Hitung Jarak Antar
Titik
6 B Output:
3
5
A 14 C
(1)
2 13 12

(2)
D 7 E

Carilah jarak terpendek dari

A ke E. (3)
Algoritma:
1. Menentukan jumlah simpul
(vertex)
2. Pembentukan garis
3. Menentukan panjang busur
4. Hitung jarak-jarak dari A
ke (4)
titik E.
 Programnya adalah
#include <iostream> void graf::masukan (){
cout<<"Hitung Jarak pada Graf dengan 5
#include <string>
Titik Simpul"<<endl<<endl;
using namespace std; cout<<" Titik 1: ";cin>>kata1;
cout<<" Titik 2:
class graf{ ";cin>>kata2; cout<<" Titik
public : 3: ";cin>>kata3; cout<<"
Titik 4: ";cin>>kata4;
voi cout<<" Titik 5: ";cin>>kata5;
d cout<<endl; yang dapat dibentuk: "<<endl;
cout<<"Garis
ma cout<<kata1<<kata2<<", "; //AB = a
su cout<<kata2<<kata3<<", "; //BC = b
cout<<kata3<<kata5<<", "; //CE = c
ka
cout<<kata4<<kata3<<", "; //DC = d
n() cout<<kata4<<kata5<<“,”; //DE = e
; cout<<kata1<<kata4<<", "; //AD = f
voi cout<<kata2<<kata1<<", "; //BA = g
d cout<<kata5<<kata2<<endl<<endl; //EB = h
kel
uar
 Sambungan ….#1
cout<<"Busur simpul "<<kata1<<" dengan "<<kata2<<" : ";cin>>a;
cout<<"Busur simpul "<<kata2<<" dengan "<<kata3<<" :
";cin>>b; cout<<"Busur simpul "<<kata3<<" dengan
"<<kata5<<" : ";cin>>c; cout<<"Busur simpul "<<kata4<<"
dengan "<<kata3<<" : ";cin>>d; cout<<"Busur simpul
"<<kata4<<" dengan "<<kata5<<" : ";cin>>e; cout<<"Busur
simpul "<<kata1<<" dengan "<<kata4<<" : ";cin>>f;
cout<<"Busur simpul "<<kata2<<" dengan "<<kata1<<" : ";cin>>g;
cout<<"Busur simpul "<<kata5<<" dengan "<<kata2<<" :
";cin>>h;
}

void graf::keluaran() {
cout<<"Jadi panjang jarak totalnya = "<<a+b+c+d+e+f+g+h<<endl<<endl;
cout<<"Mencari jalur terpendek dari "<<kata1<<" menuju "<<kata4<<" : "<<endl;
int j, k, l;
j=e+d; //Alternatif 1
k=a+b+c; //Alternatif 2
l=f+d+c; //Alternatif 3
cout<<"Alternatif Pertama : "<<kata1<<" -> "<<kata4<<" -> "<<kata5<<" = "<<kata1<<kata4<<"
+ "<<kata4<<kata5<< " Jarak : "<<j<<endl;
cout<<"Alternatif Kedua : "<<kata1<<" -> "<<kata2<<" -> "<<kata3<<" -> "<<kata5<<"
= "<<kata1<<kata2<<" + "<<kata2<<kata3<<" + "<<kata3<<kata5<< "Jarak :
"<<k<<endl;
cout<<"Alternatif Ketiga : "<<kata1<<" -> "<<kata4<<" -> "<<kata3<<" -> "<<kata5<<" =
 Sambungan ….#2
//Pilihan jalur/laluan
if (j<e && j<f) cout<<"JALUR YANG DIPILIH ADALAH YANG JARAKNYA " <<j;
if (k<a && k<b && k<c) cout<<"JALUR YANG DIPILIH ADALAH YANG JARAKNYA " <<k;
if (l<c && l<d && n<f) cout<<"JALUR YANG DIPILIH ADALAH YANG JARAKNYA " <<l;
}

int main(int argc, char *argv[])

{
graf x;
[Link](); cout<<endl;
[Link](); cout<<endl;

system("PAUSE");
return EXIT_SUCCESS;
return 0;
}
 LATIHAN 20
1. Perhatikan graph berarah berikut:
P a. Carilah bobot graph tersebut
5 b. Buat linked listnya
4
20 c. Susun ke dalam matrik
R
8 U berbobot
Q
2 d. Buatlah program graphnya
10
3
15 yang dapat menampilkan
keterhubungan antar simpul itu.
S 9 T

2. Seperti soal nomer 1, namun untuk graph yang tidak berarah.

3. Ada 7 kota (A,…,G) yang diantaranya dihubungkan langsung dengan
jalan darat. Hubungan antar kota didefinisikan sebagai A terhubung dg
B dan D; B terhubung dg D; C terhubung dg B, dan E terhubung dg
F. Buatlah graf yang menunjukkan keadaan transportasi di 7 kota
tersebut !
4. Gambar di bawah menyatakan peta kota A..G dan jalan-jalan
yang menghubungkan kota-kota tersebut. Seorang salesman akan
mengunjungi tiap kota masing-masing 1 kali dari kota F
kembali lagi ke kota F. Carilahlah (buat program) rute
perjalanan yang harus dilalui salesman tersebut.
B 12 C

4 10 3
6
9 5 E
A 7 F 5
8 D
13
G

5. Dari soal 4 di atas, tentukan path tak berarah terpendek dan

terpanjang dari titik E ke titik B !