graph
DESCRIPTION
GRAPH. GRAPH. ISTILAH GRAPH. MATRIX GRAPH. STRUKTUR DATA. JENIS GRAPH. DFS DAN BFS. MST. Disusun Oleh : Agung Juliansyah • Akbar Aswad • Indra Putra Nafisatul Hasanah • Nur had i Jumain Fantri. JAVA GRAPH. 1 SIM C. DEFINISI GRAPH. GRAPH. SIFAT GRAPH. CONTOH. - PowerPoint PPT PresentationTRANSCRIPT
GRAPHDisusun Oleh :
Agung Juliansyah • Akbar Aswad • Indra Putra Nafisatul Hasanah • Nurhadi Jumain Fantri
STRUKTUR DATA
GRAPH
ISTILAH GRAPHMATRIX GRAPH
JENIS GRAPH
DFS DAN BFS
MST
JAVA GRAPH
1 SIM C
GRAPHDefinisi Graph
Sifat –Sifat GraphContoh Graph
DEFINISI GRAPH
SIFAT GRAPH
CONTOH
DEFINISI GRAPHGraph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E)Dimana : G = GraphV = Simpul atau Vertex, atau NodeE = Busur atau Edge, atau arc
SIFAT – SIFAT GRAPH Sebuah graph mungkin hanya
terdiri dari satu simpul
Sebuah graph belum tentu semua simpulnya terhubung dengan busur
Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain
Sebuah graph mungkin semua simpulnya saling berhubungan
CONTOH GRAPHV terdiri dari V1, V2, V3 .....,V5E terdiri dari e1, e2, e3, .....,e5
Dimana :V = VertexE = Edge
ISTILAH - ISTILAH DALAM
GRAPH
PART 1
PART 2
PART 3
ISTILAH - ISTILAH DALAM GRAPH 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.
DegreeDegree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan simpul tersebut.
IndegreeIndegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
ISTILAH - ISTILAH DALAM GRAPH Out Degree
Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.
AdjacentPada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.
Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
ISTILAH - ISTILAH DALAM GRAPH 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.
PathSebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.
REPRESENTASI GRAPH DALAM
MATRIK
DIRECT
WEIGHT DIRECT
REPRESENTASI GRAPH DALAM MATRIK
Kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut.
REPRESENTASI GRAPH DALAM MATRIK
Pada Weighted Direct Graph, penulisan matrix tidak menggunakan angka no 1 dan 0 lagi, melainkan menggunakan nilai (bobot) jika ada edge yang menghubungkan dua buah verterx dan nilai 0 jika tidak ada edge yang menghubungkan vertex - vertex tersebut.
JENIS GRAPHDirected Graph
Undirected GraphWeighted Graph
DIRECTED
UNDIRECTED
WEIGHTED
DIRECTED GRAPHSebuah Graph yang sisi atau busurnya berlaku satu arah saja, sesuai dengan arah tanda panah.
Misal :e1 = (A,B)Berarti hanya berlaku untuk Graph A ke B saja, tidak berlakuUntuk B ke A
UNDIRECT GRAPHGraph yang sisi atau busurnya bisa berlaku ke dua Arah. Secara Grafik dapat dilihat tidak ada arah panah pada Busur.
Edge pada Undigraph bisa direpresentasikan sebagai garis dengan panah 2 arah.
Misal :e1 = (A,B)e1 = Bisa dikatakan Graph A ke B atau Graph B ke A
WEIGHTED GRAPH
Weighted Graph adalah Graph yang sisi / busurnya memiliki nilai (bobot). Weighted Graph terdiri dua jenis :- Weighted Direct Graph Bobot berlaku satu arah saja- Weighted Undirect Graph
Bobot Berlaku 2 arah
METODE PENCARIAN
VERTEXDepth Fast Search (DFS)
Breadth Fast Search (BFS)
DFS
BFS
DEPTH FIRST SEARCH (DFS)
Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan
Kelebihan :- Cepat Mencapai kedalaman ruang pencarian- Tidak boros waktu, jika lintasannya panjang- Lebih efisien
Kekurangan- Memungkinkan tidak ditemukan tujuan yang di harapkan- Pada setiap pencarian hanya menghasilkan 1 solusi saja
BREADTH FIRST SEARCH (BFS) Prosedur Breadth First
Search merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap level hingga keadaan tujuan (goal state) ditemukan.
Kelebihan- Tidak akan menemukan jalan Buntu- Jika lebih dari solusi, maka BFS akan solusi minimum akan ditemukan
Kekurangan- Menyimpan memori yang besar karena menyimpan semua node yang ada dalam satu pohon
MINIMUM SPANNING TREE
(MST)
PART 1
PART 2
MINIMUM SPANNING TREE Spanning Tree adalah sebuah cabang yang
terbentuk dari subset edge-edge serta menghubungkan setiap vertex dalam suatu Graph.
Minimum Spanning Tree adalah total bobot minimal dari edge-edge yang menghubungkan setiap vertex
Algoritma MST :1. Algoritma Kruskal2. Algoritma Prim
MINIMUM SPANNING TREE Contoh Minimum Spanning Tree
Unweighted Undirect Graph
Kemungkinan MST :
GRAPH PADA JAVA
Dengan Software Eclipse
ECLIPSE
SCRIPT
OUTPUT
GRAPH PADA JAVA Untuk pengaplikasian teori Graph
dapat di lakukan pada program Java.Software yang kita gunakan pada Program yang kita buat adalah Eclipse
Pada Package GRAPH_BASICTerdapat 5 file berextensi .javayang saling berhunbungan
GRAPH PADA JAVAUntuk melakukan Logika pada package GRAPH_BASICterdapat pada file main.java
GRAPH PADA JAVAOutput yang di hasilkan akan seperti di Bawah ini
Tugas Kelompok
“ Graph “
Struktur dataUniversitas Internasional Batam
Oleh : Nurhadi Jumain Fantri
Agung JuliansyahNasfisatul Hasanah
Indra PutraAkbar Aswad Terima Kasih