Download - Graph & Tree Full

Transcript
Page 1: Graph & Tree Full

STRUKTUR DATA

Disusun oleh:

Kelompok V

Risky andriasRisky andrias 09340150400934015040

Buya.pBuya.p 09340150540934015054

M misbachurM misbachur 09340150450934015045

Eric YuliantoEric Yulianto 09340150440934015044

Deny AndriantoDeny Andrianto 09340150390934015039

Nama Dosen :

Rizky Parlika, S.Kom

FTI - TEKNIK INFORMATIKA

UNIVERSITAS PEMBANGUNAN NASIONAL ” VETERAN ” JAWA TIMUR

2010

Page 2: Graph & Tree Full

3 Mempelajari Graph & Tree Dalam Struktur Data

GRAPH & TREE

BAB IX

Page 3: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 4

BAB IX

GRAPH & TREE

Dalam bab ini ditampilkan uraian mengenai graph & tree dalam struktur

data, dengan sub pokok bahasan mengenai graph dan tree.

Setelah mempelajari bab ini, mahasiswa diharapkan mampu:

Memahami konsep graph & tree dan mengerti kegunaannya

Mengimplementasikan struktur graph & tree dalam

pemrograman

Mengidentifikasi permasalahan-permasalahan pemrograman

yang harus diselesaikan dengan menggunakan graph & tree

dan menyelesaikannya.

Ruang Lingkup Pembahasan

Tujuan

Tujuan

Page 4: Graph & Tree Full

5 Mempelajari Graph & Tree Dalam Struktur Data

GRAPH & TREE

Pengertian.

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 GÈH adalah

graph dengan V(GÈH)=V(G) ÈV(H) dan E(GÈH)=E(G) ÈE(H).

JoinJoin

Join dari dua graph G dan H yang saling lepas, ditulis G+H, adalah graph

yang diperoleh dari GÈH dimana setiap simpul di G adjacent dengan setiap

simpul di H demikian juga sebaliknya. Dengan kata lain, jika G dan H

9

Page 5: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 6

masing-masing mempunyai m dan n simpul, kita harus menambahkan sisi

sebanyak mn pada graph GÈH.

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,yÎE

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 Hutan (Forest) adalah graph yang tidak

mengandung sirkuit. Jadi pohon adalah hutan yang terhubung. Untuk itu

perlu diingat kembali bahwa :

• Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari

graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.

• Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap

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) G terhubung dan tak mengandung sirkuit, atau

(2) G tidak mengandung sirkuit dan mempunyai n - 1 buah ruas, atau

Page 6: Graph & Tree Full

7 Mempelajari Graph & Tree Dalam Struktur Data

(3) G mempunyai n - 1 buah ruas dan terhubung

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.

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.

Page 7: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 8

2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan,

dengan

ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf

menjadi

tidak terhubung.

KRUSKAL

1. Urutkan ruas dari G menurut bobotnya, dari kecil ke besar.

2. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan,

dengan

ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya

sirkuit.

PRIM’S

= Kruskal + menjaga graf tetap terhubung

Contoh :

POHON BERAKAR (ROOTED TREE)

Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r

yang dirancang/ditunjuk sebagai akar (root) dari R.

Page 8: Graph & Tree Full

9 Mempelajari Graph & Tree Dalam Struktur Data

• 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 :

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

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

Page 9: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 10

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 :

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.

Page 10: Graph & Tree Full

11 Mempelajari Graph & Tree Dalam Struktur Data

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

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

POHON - 2

Page 11: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 12

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

lingkaran. Biasanya berfungsi sebagai operator.

• Simpul dengan 0 anak disebut simpul eksternal, digambarkan sebagai

segi-empat. Biasanya berfungsi sebagai operand.

Contoh : Pohon-2 yang menyajikan ekspresi (a-b)/((c+d)*e)

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 :

Page 12: Graph & Tree Full

13 Mempelajari Graph & Tree Dalam Struktur Data

Derivasi adalah proses pembentukan untai terminal dengan melakukan

sederetan produksi menggunakan himpinan produksi yang ada. Himpunan

produksi dari pohon sintaks diatas adalah :

1. <Kalimat> → <Subjek> <Predikat>

2. <Subjek> → <Kata Sandang> <Kata Benda> <Kata Keadaan>

3. <Predikat> → <Kata Kerja> <Objek>

4. <Objek> → <Kata Benda> <Kata Keadaan>

5. <Kata Sandang> → si

6. <Kata Benda> → kucing | bola

7. <Kata Keadaan> → kecil |besar

8. <Kata Kerja> → menendang

.

Page 13: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 14

http://aqwamrosadi.staff.gunadarma.ac.id/Downloads/files/13568/

PENGERTIAN+STRUKTUR+DATA.doc

http://www.kutukutubuku.com/2008/open/11462/

algorithms_in_c_part_5_graph_algorithms_3e

REFERENSI

Page 14: Graph & Tree Full

15 Mempelajari Graph & Tree Dalam Struktur Data

1. Buatlah suatu program dengan menggunakan tree?

#include<stdio.h>#include<conio.h>#include<process.h>#include<malloc.h>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->info=item; temp->llink=NULL; temp->rlink=NULL; if(root==NULL) return temp;

Page 15: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 16

prev=NULL; cur=root; while(cur!=NULL)

{ prev=cur; if(item==cur->info) { printf("NO Duplicate nodes are allowed\n"); return root; } if(item<cur->info) cur=cur->llink; else cur=cur->rlink;}

if(item<prev->info)prev->llink=temp;

elseprev->rlink=temp;

return root; }void preorder(NODE root) { if(root!=NULL) { printf("%d\t",root->info); preorder(root->llink); preorder(root->rlink); } }

void inorder(NODE root) { if(root!=NULL) {

inorder(root->llink);printf("%d\t",root->info);inorder(root->rlink);

} }

void postorder(NODE root) { if(root!=NULL) { postorder(root->llink); postorder(root->rlink);

Page 16: Graph & Tree Full

17 Mempelajari Graph & Tree Dalam Struktur Data

printf("%d\t",root->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",&ch);

switch(ch) {

case 1: printf("Enter the item to insert\n"); scanf("%d",&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

{ printf("\nPostorder Traversal\n"); postorder(root);}

Page 17: Graph & Tree Full

Bab 9: Struktur Data Tahun Ajaran 2010/1011 18

break;case 5: exit(0);default: printf("Invalid inputs");

}getch();

} }

OUTPUT

Page 18: Graph & Tree Full

19 Mempelajari Graph & Tree Dalam Struktur Data


Top Related