123doku.com

Pertemuan 15:INF202: Struktur DataGRAPH & Persiapan UASDosen: Wayan Suparta, PhD

Informasi UAS dan TUGAS: Bahan UAS (close book): 100 menit Ujian Teori:1.2.3.4.5.6.Stack (Tumpukan)Queue (Antrian)Linked list (SenaraiBerantai)Tree (Pohon)GrafAda penggalan program Ujian Praktek (salah satu):1.2.3.STACKQUEUETREE Tugas 3:1. Topik individu yang telah dipilih melalui undian.2. Kumpulkan pada Waktu UAS (20 Mei 2019) dimanasoftcopy (EDMODO) dan print Hardcopy.

SOAL LATIHAN UAS1.2.3.4.Buat fungsi menambah simpul/node dalam linked-list.Buat fungsi menghapus data dalam antrian.Buat fungsi preorder dalam pohon biner.Tentukan traversal tree dari tree:(a). A B - ( C - D) E (F * G)(b). A * B C D * (E F) (G - H / I) J5. Gambarkan pohon binernya dari traversal dari tree:(a). Pre-Order: S E L A N G M U(b). Post-Order: CENTURY6. 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.8.9.10.11.12.Implementasikan sebuah single linked list yang dapatmerepresentasikan data mahasiswa berupa NIM, Nama,Alamat dan No HP. Buatlah fungsi-fungsi untuk menelusuri,menambah simpul dan menghapus simpul.Buat program untuk menyiapkan array dua dimensi yangakan digunakan untuk mengisi Stack S sebanyak 5 elemen,bertipe karakter.Buatlah algoritma yang dapat menampilkan data antrianpasien masuk rumah sakit.Buatlah algoritma yang dapat menyisipkan data di belakangdalam model linked list seperti antrian mobil di kapalpenyeberangan (ferry). Penyisipan data adalah serentak.Sebuah graf dengan 6 simpul, berapakah minimum danmaksimum jumlah busur?Jika ada 5 kota yang saling berdekatan dan terhubung jalurdarat, berapa jalur lintasan terpendek yang dapat dilakukan.

13. Buatlah program untuk menyetor simpanan ke bank denganmenu pilihan: 1. Masukkan Antrian (nama, nomer rekeningdan jumlah setoran), 2. Proses Antrian, 3. Tampilkan Antriandan 4. EXIT. Input data adalah serentak.14. Buatlah program yang dapat menentukan Pre-Order dan InOrder jika nilai Post-Ordernya: 20 70 90 60 40 30 5015. Buatlah program untuk menyimpan balok-balok kayu dalamsebuah gudang berukuran panjang 5 m, lebar 30 cm dantinggi 540 cm. Program harus dapat menampilkan menu : 1.Masukkan data balok (kode balok, jenis balok dan jumlahbalok), 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 dataadalah secara serentak.17. Ubahlah notasi aritmatika PREFIX berikut ke notasiPOSTFIX: * A / B C – D E F

GRAPH Graph adalah kumpulan dari simpul dan busuryang secara matematis dinyatakan sebagai:G (V, E)DimanaG GraphV Vertex, atau Simpul, atau Node, atau TitikE Edge, atau Busur, atau arc

Contoh graph :vertexe1v1Av2Be4e3C v3edgee2v4 DCiri-Ciri Graphe5e6e7Ev5Gb. 1. Undirected graphV terdiri dari v1, v2, , v5E terdiri dari e1, e2, , e7 Sebuah graphmungkin hanyaterdiri dari satusimpul Sebuah graphmungkinmempunyai simpulyang tak terhubungdengan simpulyang lain Sebuah graphmungkin semuasimpulnya salingberhubunganGb. 2. Ciri graph

Graph Berarah dan Graph Tak BerarahBe8e1v1v2v2e3e4Ae2Ce10Dv4e5e6Be9e7E v5Gb. 3. Directed graphe1v3v1Ae2v4 De3e4C v3e5e6e7Ev5Gb. 4. Undirected graphDapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2simpul.

Graph tak berarah (undirected graph atau nondirected 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 adalahe1 sedangkan busur BA adalah e8. Graph Berbobot (Weighted Graph)– Jika setiap busur mempunyai nilai yang menyatakanhubungan antara 2 buah simpul, maka busur tersebutdinyatakan memiliki bobot.– Bobot sebuah busur dapat menyatakan panjang sebuahjalan dari 2 buah titik, jumlah rata-rata kendaraanperhari yang melalui sebuah jalan, dll.

Graph Berbobot :B45v1B73512Ae2v2v2C108Dv436E v5Gb. 5. Directed graphv3v1A4v4 D312C v3836Ev5Gb. 6. Undirected graphPanjang busur (atau bobot) mungkin tidak digambarkan secara panjangyang proposional dengan bobotnya. Misal bobot 5 digambarkan lebihpanjang dari 7.

Istilah pada graph1.2.IncidentJika e merupakan busur dengan simpul-simpulnya adalah v danw yang ditulis e (v,w), maka v dan w disebut “terletak” pada e,dan e disebut incident dengan v dan w.Degree (derajat), indegree, dan outdegreeDegree sebuah simpul adalah jumlah busur yang incident dengansimpul tersebut. Indegree sebuah simpul pada graph berarah adalah jumlahbusur yang kepalanya incident dengan simpul tersebut, ataujumlah busur yang “masuk” atau menuju simpul tersebut. Outdegree sebuah simpul pada graph berarah adalah jumlahbusur yang ekornya incident dengan simpul tersebut, ataujumlah busur yang “keluar” atau berasal dari simpul tersebut.

3. AdjacentPada graph tidah berarah, 2 buah simpul disebutadjacent bila ada busur yang menghubungkankedua simpul tersebut. Simpul v dan w disebutadjacent.ewGb. 7. Adjacent tak berarahvPada graph berarah, simpul v disebut adjacentdengan simpul w bila ada busur dari w ke v.evSuccessorwPredecessorGb. 8. Adjacent berarah

4. Successor dan PredecessorPada graph berarah, bila simpul v adjacent dengansimpul w, maka simpul v adalah successor simpulw, dan simpul w adalah predecessor dari simpul v.5. PathSebuah path adalah serangkaian simpul-simpulyang berbeda, yang adjacent secara berturut-turutdari simpul satu ke simpul berikutnya.1234132121243434Gb. 9. Path berarah dan tak berarah

Representasi Graph dalam bentukmatrix Adjacency Matrix Graph tak berarahUrut abjadBACDEGb. 10. Graf tak 10Degree simpul : 3

Representasi Graph dalam bentukmatrix Adjacency Matrix Graph berarahkedariBAACDEGb. 11. Graph 0out(Baris)in(kolom)

Representasi Graph dalam bentukLinked List Adjency List graph tak berarah Digambarkan sebagai sebuah simpul yangmemiliki 2 pointer. Simpul vertex :Simpul edge :leftinfoMenunjuk ke simpulvertex berikutnya,dalam untaian simpulyang adarightleftMenunjuk ke simpuledge pertamainfoMenunjuk ke simpulvertex tujuan yangberhubungan dengansimpul vertex asalrightMenunjuk kesimpul edgeberikutnya, bilamasih ada

Contoh : untuk vertex A, memiliki 2 edge yangterhubung yaitu e1 dan e2.e1Urut abjadBe4e3Ae2e5De6ACBe7CEGb. 12. Graph tak berarahDEe1e2

1. Gambar graph dapat disusun dengan lebih sederhana:BACDEBACDEGb. 13. Adjency List graph berarahABDBACECBDEDACEEBCDABDBACCEDCEBE

Graph berarah dan berbobotA0B63514A2C1213D7EGb. 14. Graph berbobotA0B1C2D3E4B10 56 00 00 00 14C2D3E40301302000000970Perhatikan pemilihan nilai 0.

Define struct untuk sebuah simpul yang dapatdigunakan sebagai vertex maupun edge. Deklarasinya:typedef struct tipeS{tipeS *Left;int INFO;tipeS *Right;};tipeS *FIRST, *PVertex, *PEdge;Penyelesaian kasus GraphGambar 14: Define simpul untuk vertex danedge Mengidentifikasi Simpul pertamasebagai vertex yang pertama Tambahkan vertex sisanya Tambahkan edge pada masingmasing vertex yang telah terbentuk Tampilkan representasi graphberikut bobotnya

Contoh 1: Dari Gambar 5*#include stdio.h #include iostream #include conio.h using namespace std;typedef struct tipeS {struct tipeS *Left;int INFO;struct tipeS *Right;};typedef struct tipeS simpul;simpul *P,*FIRST,*LAST,*PVertex,*PEdge,*Q,*R,*S;simpul *PointS[5];int main() {int A[5][5] {0,5,0,2,0, 6,0,3,0,0, 0,0,0,0,9, 0,0,12,0,7,0,14,0,0,0};char NmS[6] "ABCDE";int I, J;//Simpul Vertex yang pertamaI 0;J 0;P new simpul;P- INFO NmS[0];FIRST P; LAST P;P- Left NULL; P- Right NULL;PointS[0] P;printf("\n%c", P- INFO);printf(" Alamat %d ", PointS[0]);printf("\n");//Simpul Vertex yang berikutnyafor (I 1;I 4;I ) {P new simpul;P- INFO NmS[I];LAST- Left P;LAST LAST- Left;P- Left NULL;P- Right NULL;PointS[I] P;printf("\n %c ", P- INFO);printf("Alamat %d \n", PointS[I]);}

//Simpu2 Edge untuk semua VertexQ 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 TitikOutput:B63514A2C1213D7ECarilah jarak terpendek dariA ke E.Algoritma:1.2.3.4.(1)Menentukan jumlah simpul(vertex)Pembentukan garisMenentukan panjang busurHitung jarak-jarak dari A ketitik E.(2)(3)(4)

Programnya adalah#include iostream #include string using namespace std;class graf{public :void masukan();void keluaran();private:char kata1; //Achar kata2; //Bchar kata3; //Cchar kata4; //Dchar kata5; //Eint a, b, c, d, e, f, g, h, i, j;};void graf::masukan (){cout "Hitung Jarak pada Graf dengan 5Titik Simpul" endl endl;cout " Titik 1: ";cin kata1;cout " Titik 2: ";cin kata2;cout " Titik 3: ";cin kata3;cout " Titik 4: ";cin kata4;cout " Titik 5: ";cin kata5; cout endl;cout "Garis yang dapat dibentuk: " endl;cout kata1 kata2 ", "; //AB acout kata2 kata3 ", "; //BC bcout kata3 kata5 ", "; //CE ccout kata4 kata3 ", "; //DC dcout kata4 kata5 “,”; //DE ecout kata1 kata4 ", "; //AD fcout kata2 kata1 ", "; //BA gcout kata5 kata2 endl endl; //EB h

Sambungan .#1cout "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 1k a b c; //Alternatif 2l f d c; //Alternatif 3cout "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 " " kata1 kata4 " " kata4 kata3 " " kata3 kata5 " Jarak : " l endl;

Sambungan .#2//Pilihan jalur/laluanif (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;x.masukan(); cout endl;x.keluaran(); cout endl;system("PAUSE");return EXIT SUCCESS;return 0;}