Graph
Graf adalah
kumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan
sekumpulan garis (sisi). Graph dapat
digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara
objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau
titik (Vertex), sedangkan hubungan
antara objek dinyatakan dengan garis (Edge). G = (V, E) Dimana :
G = Graph
V = Simpul atau Vertex,
atau Node, atau Titik
E = Busur atau Edge,
atau arc
Graf merupakan
suatu cabang ilmu yang memiliki banyak terapan. Banyak sekali struktur yang
bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan
dengan bantuan graf. Seringkali graf digunakan untuk merepresentasikan suaru
jaringan. Misalkan jaringan jalan raya dimodelkan graf dengan kota sebagai
simpul (vertex/node) dan jalan yang
menghubungkan setiap kotanya sebagai sisi (edge)
yang bobotnya (weight) adalah panjang
dari jalan tersebut.
Ada beberapa
cara untuk menyimpan graph di dalam
sitem komputer. Struktur data bergantung pada struktur graph dan algoritma yang digunakan untuk memanipulasi graph. Secara teori salah satu dari
keduanya dapat dibedakan antara struktur list
dan matriks, tetapi dalam penggunaannya struktur terbaik yang sering digunakan
adalah kombinasi keduanya.
a.
Graph
tak berarah (undirected graph atau non-directed graph) :
-
Urutan simpul dalam sebuah busur tidak
dipentingkan. Misal busur e1 dapat disebut busur AB atau BA
b.
Graph
berarah (directed graph) :
-
Urutan simpul mempunyai arti. Misal busur AB
adalah e1 sedangkan busur BA adalah e8.
c.
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.
Istilah – istilah
dalam Graph :
Terdapat istilah – istilah yang
berkaitan dengan graph, yaitu :
a. Vertex
Vertex adalah himpunan node/titik pada sebuah graph.
b.
Edge
Edge adalah garis yang menghubungkan tiap node/vertex.
c.
Adjacent
Adjacent adalah dua buah titik dikatakan berdekatan juka dua buah
titik tersebut terhubung dengan sebuah sisi.
d.
Weight
Sebuah graph dikatakan berbobot apabila terdapat sebuah fungsi bobot
bernilai real pada himpunan Edge.
e.
Path
Path adalah walk dengan setiap vertex berbeda. Walk
didefinisikan sebagai ururtan vertex
dan edge. Diawali dengan origin vertex dan diakhiri dengan terminus vertex.
f.
Cycle
Cycle adalah siklus atau sirkuit yang berawal dan berakhir pada
simpul yang sama.
Contoh program :
Contoh program :
#include <stdfix.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
int ordo[5][5];
void masukkan(int a, int b, int c)
{
for (int i = 1; i <= 4; i++)
{
for (int j = 1; j <= 4; j++)
if (i == a && j == b)
{
ordo[a][b] = ordo[i][j];
ordo[a][b] = c;
}
}
}
void tampilkan(int a, int b, int c)
{
for (int i = 1; i <= 4; i++)
{
for (int j = 1; j <= 4; j++)
cout << ordo[i][j] << " ";
cout << endl;
}
}
void inisialisasi()
{
for (int i = 1; i <= 4; i++)
{
for (int j = 1; j <= 4; j++)
ordo[i][j] = 0;
}
}
void menu()
{
cout << "-----------------MENU-----------------\n";
cout << "1. Masukkan Data\n";
cout << "2. Tampilkan\n";
cout << "0. Keluar\n";
cout << "Masukkan Pilihan Anda: ";
}
int main()
{
inisialisasi();
int a, b, c;
int m;
do
{
system("cls");
menu();cin >> m;
switch (m)
{
case 1:
cout << "\nMasukkan Koordinat x : "; cin >> a;
cout << "Masukkan Koordinat y : "; cin >> b;
cout << "Masukkan Isi : "; cin >> c;
if (a <= 4 && b <= 4)
{
masukkan(a, b, c);
}
else
{
cout << "\nIndeks harus kurang dari 4\n";
}
break;
system("pause");
case 2:
system("cls");
tampilkan(a, b, c);
break;
system("pause");
}
system("pause");
}
while (m != 0);
}
Hasil Running :
Pohon
Tree merupakan salah satu
bentuk struktur data tidak linear
yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan
simpul/node dengan satu elemen khusus
yang disebut Root dan node lainnya. Tree juga adalah suatu graph
yang acyclic, simple, connected yang
tidak mengandung loop.
Sebuah binary search tree (bst) adalah sebuah
pohon biner yang boleh kosong, dan setiap nodenya
harus memiliki identifier/value. Value pada semua node
subpohon sebelah kiiri adalah selalu lebih kecil dari value dari root,
sedangkan value subpohon di sebelah
kanan adalah sama atau lebih besar dari value
pada root, masing-masing subpohon
tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree. Struktur data bst sangat penting dalam struktur
pencarian, misalkan dalam kasus pencarian dalam sebuah list, jika list sudah
dalam keadaan terurut maka proses pencarian akan semakin cepat, jika kita
menggunakan list contigue dan melakukan pencarian biner, akan tetapi jika kita ingin melakukan perubahan isi list (insert atau delete),
menggunakan list contigue akan sangat
lambat, karena prose insert dan delete dalam list contigue butuh memindahkan linked-list,
yang untuk operasi insert atau delete tinggal mengatur- atur pointer, akan tetapi pada n-linked list, kita tidak bisa melakukan
pointer sembarangan setiap saat,
kecuali hanya satu kali dengan kata lain hanya secara squential.
Istilah – istilah di dalam Tree :
Berikut ini merupakan istilah yang berhubungan dengan
tree.
1.
Predesesor
Node
yang berada diatas node
tertentu. (contoh : B predesesor
dari E dan F)
2.
Succesor
Node yang berada dibawah node
tertentu. (contoh : E dan F merupakan succesor dari B)
3.
Ancestor
Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur
yang sama. (contoh : A dan B merupakan ancestor dari F)
4.
Descendant
Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur
yang sama. (contoh : F dan B merupakan ancestor dari A)
5.
Parent
Predesesor
satu level diatas satu node. (contoh
: B merupakan parent dari F)
6.
Child
Succesor
satu level dibawah satu node. (contoh
: F merupakan child dari B)
7.
Sibling
Node yang memiliki parent
yang sama dengan satu node (contoh :
E dan F adalah sibling)
8.
Subtree
Bagian dari tree yang berupa suatu node beserta descendant-nya (contoh : Subtree
B, E, F dan Subtree D, G, H)
9.
Size
Banyaknya node dalam suatu tree
(contoh : gambar tree diatas memiliki
size = 8)
10. Height
Banyaknya tingkat/level dalam suatu tree (contoh : gambar tree
diatas memiliki height = 3)
11. Root (Akar)
Node
khusus dalam tree yang tidak memiliki
predesesor (Contoh : A)
12. Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun (contoh : Node E,F,C,G,H)
13. Degree
(Derajat)
Banyaknya child yang dimiliki oleh suatu node (contoh : Node A memiliki derajat 3, node
B memiliki derajat 2)
Contoh Program
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
class kruskal
{
private:
int n ;//no of nodes
int noe; //no edges in the graph
int graph_edge[100][100];
int tree[100][100];
int sets[100][100];
int top[100];
public:
int read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};
int kruskal::read_graph()
{
///cout<<"Program ini Mengimplementasikan Algoritma Kruskal\n";
cout<<"Banyak titik bandara : ";
cin>>n;
noe=0;
cout<<"\nJarak antar tiap bandara:\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout<<"("<<i<<" , "<<j<<") = ";
int w;
cin>>w;
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
cout << endl;
}
}
void kruskal::sort_edges()
{
/** Sort the edges using bubble sort in increasing order******/
for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
cout<<"\n\nSetelah Jarak diurutkan adalah ::\n";
for(int i=1;i<=noe;i++)
cout<<"("<< graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" ) = "<<graph_edge[i][3]<<endl;
}
void kruskal::algorithm()
{
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
cout<<"\nRentang Yang di Pakai\n\n";
for(int i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
cout<<"Rentang yg masuk ke pohon ::"
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<endl<<endl;
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
// Mix the two sets
for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
cout<<"Jika "
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<"di masukkan, maka terbentuk siklus. jadi di hapus\n\n";
}
}
}
int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
int main(int argc, char *argv[])
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.algorithm();
system("PAUSE");
return EXIT_SUCCESS;
}
Hasil Running
No comments:
Post a Comment