graph dalam struktur data

STRUKTUR DATAGRAPH

Created By

I Made Godya A 065112308

MARI KITA MULAI

INTRO: DEFINISI

Graph adalah  sekelompok simpul-simpul (nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. Bayangkan simpul-simpul tersebut sebagai lokasi-lokasi, maka himpunan dari simpul-simpul tersebut adalah himpunan lokasi-lokasi yang ada. Dengan analogi ini, maka sisi merepresentasikan jalan yang menghubungkan pasangan lokasi-lokasi tersebut.

Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge atau arc). biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

G = (V, E)

Dimana G = GraphV = Simpul atau Vertex, atau Node, atau Titik E = Busur atau Edge, atau arc

Bagian IIImplementasi Pada Struktur Data

Graf Tak Berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. salah satu contoh graf tak berarah dimana sisi-sisi yang menghubungkan antar simpul dalam graf tersebut tidak memiliki orientasi arah.

Graf Berarah (directed graph)

Graf yang setiap sisinya memiliki orientasi arah disebut sebagai graf berarah. Sisi berarah dalam graf ini dapat dinamakan sebagai busur (arc). Lain halnya dengan graf tak-berarah, urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. contoh dari graf berarah yang memiliki sisi-sisi dengan orientasi arah (busur).

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.

Bagian IIIIstilah-Istilah dalam Graft

Istilah-Istilah dalam Grafta. VertexAdalah himpunan node / titik pada sebuah graph.b. EdgeAdalah himpunan garis yang menghubungkan tiap node / vertex.c. AdjacentAdalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4. Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan titik v4.

d. WeightAdalah Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E, W : E ® R, nilai W(e) disebut bobot untuk sisi e, " e Î E. Graf berbobot tersebut dinyatakan pula sebagai G = (V, E, W).

Graf berbobot G = (V, E, W) dapat menyatakan * suatu sistem perhubungan udara, di mana · V = himpunan kota-kota· E = himpunan penerbangan langsung dari satu kota ke kota lain· W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu suatu sistem jaringan komputer, di mana· V = himpunan komputer· E = himpunan jalur komunikasi langsung antar dua komputer· W = fungsi bernilai real pada E yang menyatakan jarak atau ongkos atau waktu

e. PathAdalah Walk dengan setiap vertex berbeda. Contoh, P = D5B4C2A Sebuah walk (W) didefinisikan sebagai urutan (tdk nol) vertex & edge. Diawali origin vertex dan diakhiri terminus vertex. Dan setiap 2 edge berurutan adalah series. Contoh, W = A1B3C4B1A2.f. CycleAdalah Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama

Bagian IVDigraph & Undigraph

Digraph

Graph Berarah (directed graph atau digraph): jika sisi-sisi pada graph, misalnya {x, y} hanya berlaku pada arah-arah tertentu saja, yaitu dari x ke y tapi tidak dari y ke x; verteks x disebut origin dan vertex y disebut terminus dari sisi tersebut. Secara grafis maka penggambaran arah sisi-sisi digraph dinyatakan dengan anak panah yang mengarah ke verteks terminus, secara notasional sisi graph berarah ditulis sebagai vektor dengan (x, y).

Konektivitas pada Digraph• Adjacency ke / dari: Jika terdapat sisi (x,y) maka dalam digraph

dikatakan bahwa x "adjacent ke" y atau y "adjacent dari" x. Demikian pula jika terdapat path dari x ke y maka belum tentu ada path dari y ke x Jadi dalam digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.

• Terkoneksi dengan kuat: Himpunan bagian verteks S dikatakan terkoneksi dengan kuat (strongly connected) bila setiap pasangan verteks berbeda x dan y dalam S, x berkoneksi dengan y dan y berkoneksi dengan x (dpl., ada path dari x ke y dan sebaliknya dari y ke x).

• Terkoneksi dengan Lemah: Himpunan bagian verteks S dikatakan terkoneksi dengan lemah (weakly connected) bila setiap pasangan verteks berbeda x dan y dalam S, salah satu: x berkoneksi dengan y (atau y berkoneksi dengan x) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu path: dari x ke y atau sebaliknya dari y ke x).

Undigraph

Graph Tak Berarah (undirected graph atau undigraph): setiap sisi {x, y} berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal.

Dalam masalah-masalah graph undigraph bisa dipandang sebagai suatu digraph dengan mengganti setiap sisi tak berarahnya dengan dua sisi untuk masing-masing arah yang berlawanan.

Konektivitas pada Undigraph• Adjacency: Dua verteks x dan y yang berlainan disebut

berhubungan langsung (adjacent) jika terdapat sisi {x, y} dalam E.

• Path: Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat berada disebelahnya.

• Panjang dari path: jumlah sisi yang dilalui path. • Siklus: suatu path dengan panjang lebih dari satu yang dimulai

dan berakhir pada suatu verteks yang sama.

Graph Berbobot

Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut merupakan "biaya" dari keterhubungan ybs. Pengertian "biaya" ini menggeneralisasikan banyak aspek: biaya ekonomis dari proses/aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya.

Bagian 5Representasi Graph

Linked ListBila ingin direpresentasikan dalambentuk linked list, dapat diilustrasikan secara sederhana seperti gambar 4b. Dari ilustrasi sederhana tersebut terlihat ada 5 buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari masing-masing simpul ’keluar’ pointer kearah kanan yang menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk simpul B dan simpul D.

Struct tipes{ Struct tipes *Left; int INFO; Struct tipes *Right; }; Struct tipes *First,*Pvertex,*Pedge;

Contoh Program #include <iostream> #include <cstdlib> #include <stdio.h> #include <cstring> #include <math.h> #include <conio.h>   using namespace std;   int main() { bool ketemu,nolsemua; int matrix[10] [10]; int i,j,jumlah_simpul,jumlah_sisi,asal,tujuan; cout<<"||=====================================||"<<endl; cout<<"||PROGRAM MENGECEK KETERHUBUNGAN SIMPUL||"<<endl; cout<<"||=====================================||"<<endl; cout<<"|| ||"<<endl; cout<<"||Press Enter to Continue ||"<<endl; cout<<"||=====================================||"<<endl; cin.get(); system("CLS"); cout<<endl; cout<<" Masukan jumlah simpul: ";

cin>>jumlah_simpul; cout<<endl<<" Masukan jumlah_sisi:"; cin>>jumlah_sisi; for (i=1;i<=jumlah_simpul;i++) for (j=1;j<=jumlah_simpul;j++) matrix[i][j]=0; for (i=1;i<=jumlah_sisi;i++) { cout<<endl<<" Masukan simpul asal:"; cin>>asal; cout<<endl<<" Masukan simpul tujuan:"; cin>>tujuan; matrix[asal][tujuan]=1; matrix[tujuan][asal]=1; } i=1;nolsemua=false; while (i<=jumlah_simpul && !nolsemua) {

j=1;ketemu=false; while (j<=jumlah_simpul && !ketemu) { if (matrix[i][j]==1) ketemu=true; else j++; } if (!ketemu) nolsemua=true; else i++; } if(nolsemua) cout<<endl<<" graf tidak terhubung"; else cout<<endl<<" Hasilnya Adalah: "<<endl; cout<<endl<<" graf terhubung"; getch(); }

Selesai

Thanks for Watching and your Attention

Mohon Maaf untuk kelebihan dan kekurangan dalam Slide ini, dibuat semata-mata untuk tugas, tanpa bermaksud menyinggung pihak-pihak tertentu.

http://t4urusboy08.blogspot.com/http://brawlyvonfabre.blogspot.com/p/graph.htmlhttp://abeazis.blogspot.com/p/graph.htmlhttp://lukmanreza.blogspot.com/2011/06/program-c-graph.htmlhttp://adekdik.wordpress.com/2009/09/02/colouring-graph-dengan-c/