Graph & Tree Full

Download Graph & Tree Full

Post on 03-Jul-2015

284 views

Category:

Documents

3 download

Embed Size (px)

TRANSCRIPT

<p>STRUKTUR DATA</p> <p>Disusun oleh:Kelompok V</p> <p>Risky andrias Buya.p M misbachur Eric Yulianto Deny Andrianto</p> <p>0934015040 0934015054 0934015045 0934015044 0934015039</p> <p>Nama Dosen :</p> <p>Rizky Parlika, S.Kom</p> <p>FTI - TEKNIK INFORMATIKA UNIVERSITAS PEMBANGUNAN NASIONAL VETERAN JAWA TIMUR</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data 2010</p> <p>3</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/10114</p> <p>GRAPH &amp; TREE</p> <p>BAB IX</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data</p> <p>5</p> <p>BAB IX GRAPH &amp; TREE</p> <p>Ruang Lingkup Pembahasan</p> <p>Dalam bab ini ditampilkan uraian mengenai graph &amp; tree dalam struktur data, dengan sub pokok bahasan mengenai graph dan tree.</p> <p>TujuanTujuan</p> <p>Setelah mempelajari bab ini, mahasiswa diharapkan mampu:</p> <p>Memahami konsep graph &amp; tree dan mengerti kegunaannya Mengimplementasikan pemrograman Mengidentifikasi permasalahan-permasalahan yang pemrograman struktur graph &amp; tree dalam</p> <p>harus diselesaikan dengan menggunakan graph &amp; tree</p> <p>dan menyelesaikannya.</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/10116</p> <p>9GRAPH &amp; TREEPengertian.Graph atau graf merupakan sekumpulan dari item yang dihubungkan oleh sisi (edge). Setiap item disebut sebagai vertex atau node atau simpul. Secara formal, graf adalah suatu kumpulan dari simpul dan relasi di antara simpul-simpul yang berhubungan. Graph biasanya direpresentasikan sebagai G = ( V, E ), dimana V adalah set (kumpulan) dari simpul dan E adalah set (kumpulan) dari sisi. V merupakan set tidak kosong terhingga (finite) dari simpul yang umumnya diberi nomor 1, 2, 3, , n dan E adalah set terbatas pasangan (pair) dari simpul-simpul. Setiap pasangan pada E merupakan sebuah sisi dari graf G. Operasi-Operasi Pada Graph Union Misal G dan H adalah dua graph yang saling asing. Union GH adalah graph dengan V(GH)=V(G) V(H) dan E(GH)=E(G) E(H). JoinJoin Join dari dua graph G dan H yang saling lepas, ditulis G+H, adalah graph yang diperoleh dari GH dimana setiap simpul di G adjacent dengan setiap simpul di H demikian juga sebaliknya. Dengan kata lain, jika G dan H</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data</p> <p>7</p> <p>masing-masing mempunyai m dan n simpul, kita harus menambahkan sisi sebanyak mn pada graph GH. Penghapusan Jika v adalah simpul di G, graph G-v adalah graph yang diperoleh dari G dengan menghapus v dan semua sisi yang incident menghapus v dan semua sisi yang incident dengan v.Jika e adalah sisi di G, graph G-e adalah graph yang diperoleh dari G dengan menghapus sisi e Graph Garis (Line graph) Graph garis G=(V,E), ditulis L(G) adalah graph pada E yang mana x,yE adjacent sebagai simpul jika hanya jika keduanya adjacent sebagai sisi di G. POHON (TREE) Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit.Sedangkan perlu diingat kembali bahwa : Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut. simpul dua. Sifat : Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur diantara setiap pasang simpul dari Graf G. Teorema : Suatu Graf G dengan n buah simpul adalah Pohon jika : (1) (2) G terhubung dan tak mengandung sirkuit, atau G tidak mengandung sirkuit dan mempunyai n - 1 buah ruas, atau Hutan (Forest) adalah graph yang tidak</p> <p>mengandung sirkuit. Jadi pohon adalah hutan yang terhubung. Untuk itu</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/10118</p> <p>(3)</p> <p>G mempunyai n - 1 buah ruas dan terhubung</p> <p>Teorema : Pohon (dan hutan) adalah berwarna 2. POHON RENTANGAN (SPANNING TREE) Suatu pohon rentangan atau spanning tree adalah suatu subgraf dari graf G yang mengandung semua simpul dari G dan merupakan suatu pohon.</p> <p>POHON RENTANGAN MINIMAL (MINIMAL SPANNING TREE) Apabila G suatu Graf berbobot (Suatu Network), maka pohon rentangan minimal dari graf adalah pohon rentangan dengan jumlah bobot terkecil. Untuk mendapatkan pohon rentangan minimal dapat digunakan Algoritma berikut : SOLIN 1. Urutkan ruas dari G menurut bobotnya, dari besar ke kecil.</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data 2.</p> <p>9</p> <p>Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan,</p> <p>dengan ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi tidak terhubung. KRUSKAL 1. 2. Urutkan ruas dari G menurut bobotnya, dari kecil ke besar. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan,</p> <p>dengan ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit. PRIMS = Kruskal + menjaga graf tetap terhubung Contoh :</p> <p>POHON BERAKAR (ROOTED TREE) Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r yang dirancang/ditunjuk sebagai akar (root) dari R.</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/101110</p> <p> Seperti diketahui bahwa hanya terdapat satu jalur antara r dengan simpul lain v pada pohon pohon tersebut. Panjang jalur antara r dengan simpul v disebut level atau kedalaman simpul v. Simpul bukan akar, yang berderajat satu disebut daun. Jalur antara suatu simpul dengan suatu daun disebut cabang (branch). Contoh :</p> <p>Simpul u dikatakan mendahului simpul v jika jalur dari akar r ke v melalui u. Dikatakan u mendahului langsung v bila u mendahului v serta simpul u dan v berdampingan. Pada contoh di atas, a mendahului d, mendahului e, dan mendahului h. Suatu pohon berakar dapat digunakan untuk menelusuri semua</p> <p>kemungkinan dari kejadian, dengan masing-masing kejadian dapat muncul dalam sejumlah hingga cara. Bebarapa contoh lain yang penting dari pohon berakar adalah pohon binar (binary tree) dan pohon sintaks (syntax tree) atau pohon derivasi (derivation tree). POHON BINAR (BINARY TREE) Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka. Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data</p> <p>11</p> <p>binary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul, sedemikian sehingga : a. T adalah hampa (disebut pohon null) atau b. T mengandung simpul R yang dipilih disebut akar (root) dari T, dan simpul sisanya membentuk 2 pohon binary T1 dan T2 yang saling lepas. Setiap simpul didalam pohon binar hanya dapat mempunyai 0, 1 atau 2 successor (turunan langsung). Untuk menyajikan pohon binar, simpul akar adalah simpul yang digambar pada bagian paling atas. Sedangkan suksesor kiri (left successor) digambarkan sebagai garis ke kiri bawah dan suksesor kanan (right successor) sebagai garis ke kanan bawah. Contoh :</p> <p>B adalah left successor dan C adalah right successor dari simpul A Left subtree dari root A terdiri dari simpul B, D, E, F Right subtree dari root A terdiri dari simpul C, G, H, J, K, L F adalah left successor dari simpul E L adalah right successor dari simpul J Kedalaman atau ketinggian (depth/height) dari pohon binar T adalah banyak maksimum simpul dari cabang di T. Untuk pohon binar di atas, ketinggiannya adalah 5.</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/101112</p> <p>Pohon biner T dan T disebut similar jika strukturnya (bentuknya) sama. Pohon biner T dan T disebut salinan (copy) jika strukturnya (bentuknya) sama dan nama simpulnya sama. Contoh : Gambar semua kemungkinan pohon biner yang non-similar dengan 3 simpul</p> <p>POHON BINAR LENGKAP Suatu pohon binar T dikatakan lengkap bila setiap tingkatnya, kecuali mungkin tingkat yang terakhir, mempunyai semua simpul yang mungkin, yaitu 2 .simpul untuk tingkat ke-r, dan bila semua simpul pada tingkat terakhir muncul di bagian kiri pohon. Kedalaman atau ketinggian pohon binar lengkap T dengan n simpul : INT(2log n) + 1</p> <p>POHON - 2</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data</p> <p>13</p> <p>Pohon binar T dikatakan pohon-2 atau pohon binar yang diperluas (extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak. Simpul dengan 2 anak disebut simpul internal, digambarkan sebagai Simpul dengan 0 anak disebut simpul eksternal, digambarkan sebagai lingkaran. Biasanya berfungsi sebagai operator. segi-empat. Biasanya berfungsi sebagai operand. Contoh : Pohon-2 yang menyajikan ekspresi (a-b)/((c+d)*e)</p> <p>POHON SINTAKS (SYNTAX TREE) Untuk menjelaskan mengenai bahasa secara teoritis dan formal, kita lihat terlebih dahulu sebuah kalimat sehari-hari dalam bahasa Indonesia, yaitu : Si kucing kecil menendang bola besar Gambar penguraian kalimat di atas membentuk struktur pohon, yang disebut pohon sintaks dari kalimat. Disini kalimat dibagi-bagi berdasar jenis dan fungsi kata. Dari pelajaran bahasa Indonesia kita tahu bahwa kalimat di atas telah benar susunannya, atau telah benar tata bahasanya. Pohon sintaks dari kalimat di atas dapat dilihat sebagai berikut :</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/101114</p> <p>Derivasi adalah proses pembentukan untai terminal dengan melakukan sederetan produksi menggunakan himpinan produksi yang ada. Himpunan produksi dari pohon sintaks diatas adalah : 1. 2. 3. 4. 5. si kucing | bola kecil |besar menendang 6. 7. 8. </p> <p>.</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data</p> <p>15</p> <p>REFERENSI</p> <p>http://aqwamrosadi.staff.gunadarma.ac.id/Downloads/files/13568/PENG ERTIAN+STRUKTUR+DATA.doc</p> <p>http://www.kutukutubuku.com/2008/open/11462/algorithms_in_c_part_5 _graph_algorithms_3e</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/101116</p> <p>1.</p> <p>Buatlah suatu program dengan menggunakan tree?</p> <p>#include #include #include #include struct node { int info; struct node *llink; struct node *rlink; }; typedef struct node *NODE; NODE getnode() { NODE x; x=(NODE) malloc(sizeof(struct node)); if(x==NULL) { printf("\nOut of memory\n"); exit(0); } return x; } NODE insertion(int item,NODE root) { NODE temp,prev,cur; temp=getnode(); temp-&gt;info=item; temp-&gt;llink=NULL; temp-&gt;rlink=NULL; if(root==NULL)</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data return temp; prev=NULL; cur=root; while(cur!=NULL) { prev=cur; if(item==cur-&gt;info) { printf("NO Duplicate nodes are allowed\n"); return root; } if(iteminfo) cur=cur-&gt;llink; else cur=cur-&gt;rlink; } if(iteminfo) prev-&gt;llink=temp; else prev-&gt;rlink=temp; return root; } void preorder(NODE root) { if(root!=NULL) { printf("%d\t",root-&gt;info); preorder(root-&gt;llink); preorder(root-&gt;rlink); } } void inorder(NODE root) { if(root!=NULL) { inorder(root-&gt;llink); printf("%d\t",root-&gt;info); inorder(root-&gt;rlink); } } void postorder(NODE root) { if(root!=NULL) {</p> <p>17</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/101118</p> <p>postorder(root-&gt;llink); postorder(root-&gt;rlink); printf("%d\t",root-&gt;info); } } void main() { NODE root=NULL; int item,ch; for(;;) { printf("\n1: INSERT\n2: PREORDER\n3: INORDER\n4: POSTORDER\n5. EXIT\n"); printf("\nEnter ur choice : "); scanf("%d",&amp;ch); switch(ch) { case 1: printf("Enter the item to insert\n"); scanf("%d",&amp;item); root=insertion(item,root); break; case 2: if(root==NULL) printf("Tree is empty\n"); else { printf("\nPreorder Traversal\n"); preorder(root); } break; case 3: if(root==NULL) printf("Tree is empty\n"); else { printf("\nInorder Traversal\n"); inorder(root); } break; case 4: if(root==NULL) printf("Tree is empty\n"); else {</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data printf("\nPostorder Traversal\n"); postorder(root); } break; case 5: exit(0); default: printf("Invalid inputs"); } getch(); } }</p> <p>19</p> <p>OUTPUT</p> <p>Bab 9: Struktur Data Tahun Ajaran 2010/101120</p> <p>Mempelajari Graph &amp; Tree Dalam Struktur Data</p> <p>21</p>