Graph

    GraphDinyatakan dalam suatu fungsi G = (V , E ) dim anaV = kum pulan sim pul/ vertex/ nodeE = kum pulan busur / edge/ arcTiap busur pasti menghubungkan 2 simpul. Ada 2 macam graph1. Graph tak terarah (Undirected graph)2. Graph terarah (Directed graph)
Pengertian Graf PerbedaannyaGraf 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 darigraph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).
G = (V, E)DimanaG = GraphV = Simpul atau Vertex, atau Node, atau TitikE = Busur atau Edge, atau arcGraf 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 memmanipulasi 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.

• 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• Graph berarah (directed graph) :• Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8.• 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.

Adapun Perbedaan Graph dengan Tree sebagai berikut:a. Pada Tree tidak terdapat Cycleb. Pada Graph tidak memiliki root

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau (directed graph). Digraf dengan sisi berbobot disebut jaringan.
Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah




Pada digraf maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.
Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

• Degree
 atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.

• Path
 suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path 

• Cycle
 siklus ? path yang kembali melalui titik asal 2  kembali ke 2.

• Tree
 merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex

• Graf Tak Berarah (Undirected Graph)
 Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (v_i,v_j)=(v_j,v_i)

• Graf Berarah (Directed Graph)
 Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.

graph untitled {
        graph[bgcolor="transparent"];
        node [fontname="Bitstream Vera Sans", fontsize="22.00", shape=circle, style="bold,filled" fillcolor=white];
        edge [style=bold];
        1;2;3;4;5;6;
        6 -- 4 -- 5 -- 1 -- 2 -- 3 -- 4;
        2 -- 5;
}

tree binary tree

  Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data dimana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Sebuah struktur data ringkas adalah sesuatu yang mengambil tempat minimum mutlak yang mungkin, yang berdiri sebagai teori informasi bawah. Jumlah dari pohon biner yang berbeda pada  simpul adalah , Bilangan Catalan ke (asumsikan kita melihat pohon dengan struktur yang identik sebagai sebuah kesamaan). Untuk besarnya , ini berkisar kira-kira sehingga kita membutuhkan setidaknya kira-kira  bit untuk menyalinnya. Oleh sebab itu sebuah pohon biner ringkas hanya membutuhkan 2 bit setiap simpul.

Salah satu penggambaran sederhana yang masih berhubungan dengan ini adalah mengunjungi simpul dari pohon dengan preoder, meletakkan "1" untuk sebuah simpul dalan dan "0" untuk sebuah daun.Jika pohon ini memuat data, kita dapat menyimpanya secara serempak dalam sebuah array yang berurutan dengan preoder. Fungsi ini memenuhi:

function EncodeSuccinct(node n, bitstring structure, array data) {

    if n = nil then

        append 0 to structure;

    else

        append 1 to structure;

        append n.data to data;

        EncodeSuccinct(n.left, structure, data);

        EncodeSuccinct(n.right, structure, data);

}

String structure hanya memiliki  bit pada bagian akhir, dimana adalah angka dari simpul dalam; kita bahkan tidak memerlukan untuk menyimpan panjangnya. Untuk menunjukkan bahwa tidak ada informasi yang hilang, kita dapat mengubah hasilnya kembali seperti pohon aslinya seperti ini:

function DecodeSuccinct(bitstring structure, array data) {

    remove first bit of structure and put it in b

    if b = 1 then

        create a new node n

        remove first element of data and put it in n.data

        n.left = DecodeSuccinct(structure, data)

        n.right = DecodeSuccinct(structure, data)

        return n

    else

        return nil

}

Penggambaran secara ringkas dan rumit memungkinkan tidak hanya penyimpanan yang rapi pada pohon tetapi bahkan operasi yang berguna secara langsung pada pohon tersebut, meskipun mereka masih dalam bentuk yang ringkas.

Penyandian pohon n-er sebagai pohon biner

Terdapat sebuah pemetaan satu-satu antara pohon terurut general dan pohon biner, yang biasanya digunakan oleh Lisp untuk menggambarkan pohon terurut general sebagai pohon biner. Setiap simpul N dalam pohon terurut terhubung ke sebuah simpul N dalam pohon biner; anak kiri dari N merupakan simpul yang terhubung ke anak pertama dari N, dan anak kanan dari N merupakan simpul yang terhubung ke saudara selanjutnya dari N yang merupakan simpul selanjutnya dalam urutan di antara anak-anaknya dari ayahnya N

Suatu cara untuk menyelesaikan ini adalah bahwa setiap anak simpul berada dalam sebuah linked list, dihubungkan bersama dengan bidang kanan mereka, dan simpul yang hanya memiliki sebuah petunjuk ke awalnya atau kepala dari daftar ini, melalui bidang kiri nya.

Sebagai contoh, dalam sebuah pohon bagian kirinya, A memiliki 6 anak {B,C,D,E,F,G}. Ini dapat diubah manjadi sebuah pohon biner bagian kanan.

Pohon biner dapat dianggap sebagai pohon asli yang membujur kesamping, dengan tepi kirinya yang berwarna hitam menggambarkan anak pertama dan tepi kanannya yang berwarna biru menggambarkan saudara selanjutnya. Daun dari bagian kiri pohon ini dapat dituliskan dalam Lips sebagai:

(((M N) H I) C D ((O) (P)) F (L))

yang akan diimplementasikan ke memori sebagai pohon biner kanan, tanpa huruf apapun pada simpul itu yang telah memiliki anak.

Single linked list Non Circular

      Single linked list Non Circular

single linked list non circular

Linked List

• Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.

• Linked List sering disebut juga Senarai Berantai

• Linked List saling terhubung dengan bantuan variabel pointer

• Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.

Bentuk Node Single Linked List non Circular

Pengertian:

• Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL

• Linked List : artinya node-node tersebut saling terhubung satu sama lain.

• Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.

• Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Deklarasi Node

typedef struct TNode{

int data;

TNode *next;

};

Penjelasan:

• Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode

• Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.

Pembuatan Single Linked List non Circular (2)

• Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.

TNode *baru;

baru = new TNode;

baru->data = databaru;

baru->next = NULL;

Single linked list Circular

   Single linked list Circular

 Salah satu jenis struktur data yang paling dasar adalah Linked List / Senarai Berantai. Linked List mempunyai beberapa variasi, dalam posting kali ini saya akan menulist Single Linked List. Single Linked List adalah terdiri dari elemen-elemen individu, dimana masing-masing dihubungkan dengan pointer   tunggal.  Masing-masing  elemen terdiri dari dua bagian, yaitu sebuah data dan sebuah pointer yang disebut dengan pointer next. Dengan menggunakan struktur two-member seperti ini, linked list dibentuk dengan cara menunjuk pointer next suatu elemen ke elemen yang mengikutinya.

Pointer next  pada elemen terakhir merupakan NULL, yang menunjukkan akhir dari suatu list.  Elemen pada awal suatu list disebut head, dan elemen terakhir dari suatu list disebut tail. ntuk mengakses elemen dalam linked list, dimulai dari head dan menggunakan pointer next dari elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai elemen yang diminta dicapai.Dengan single linke list, list dapat dilintasi hanya satu   arah   dari   head   ke   tail   karena   masing-masing   elemen   tidak   terdapat   link   dengan elemen sebelumnya.

 Sehingga, apabila kita mulai dari head dan berpindah ke beberapa elemen dan berharap dapat mengakses element sebelumnya, kita harus mulai dari head. Secara   konseptual,   linked   list   merupakan   deretan   elemen   yang   berdampingan. Akan tetapi, karena elemen-elemen tersebut dialokasikan secara dinamis bahwa  tapi kenyataannya,   linked   list   akan   terpencar- pencar   di   memory, pointer next menjamin bahwa element selanjutnya dapat diakses.

#include <iostream>

using namespace std;

class LinkList{

private:

struct node{

int data;

node *next;

};

node *head;

public:

LinkList();

void insertData(int num);

void deleteData (int num);

void displayData();

int count();

~LinkList();

};

LinkList::LinkList()

{

head=NULL;

}

void LinkList::insertData(int num)

{

node *temp;

node *t;

if( head == NULL)

{

head = new node;

head->data = num;

head->next = NULL;

}

else

{

temp = head;

while(temp->next != NULL)

{

temp = temp->next;

}

t = new node;

t->data = num;

t->next = NULL;

temp->next = t;

}

}

void LinkList::deleteData(int num)

{

node *q, *r;

q= head;

if(q->data == num)

{

head = q->next;

delete q;

return;

}

r = q;

while(q!= NULL)

{

if(q->data == num )

{

r->next = q->next;

delete q;

return;

}

r = q;

q = q->next;

}

cout << ” Nilai ” << num << “tidak ditemukan”;

}

void LinkList::displayData()

{

node *q;

for(q=head; q != NULL; q=q->next)

{

cout<<q->data<<endl;

}

}

int LinkList::count()

{

node *q;

int c=0;

for( q=head ; q != NULL ; q = q->next )

c++;

return c;

}

LinkList::~LinkList()

{

node *q;

if(head == NULL)

{

return;

}

while(head != NULL)

{

q = head->next;

delete head;

head = q;

}

}

int main()

{ LinkList list;

int temp;

int pilihan;

while(1)

{

cout<<”Link List Single”<<endl;

cout<<”1.Insert / Creation”<<endl;

cout<<”2.Delete Element”<<endl;

cout<<”3.View Element”<<endl;

cout<<”4.Count Element”<<endl;

cout<<”5.Exit”<<endl;

cout<<”Enter your choice:”;

cin>>pilihan;

switch(pilihan)

{  cout<<endl;

case 1:

cout<<”Insert Element Data”;

cin>>temp;

list.insertData(temp);

break;

case 2:

cout<<”Delete Element :”;

cin>>temp;

list.deleteData(temp);

break;

case 3:

list.displayData();

break;

case 4:

cout<<”Number Total Element at List : “<<list.count()<<endl;

break;

case 5:

return 0;

}

}

}

Double linked list Non Circular

A.   Double linked list Non Circular

#include <iostream.h> //File Header Iostream

#include <conio.h> //File Header Conio

typedef struct TNode { //Deklarasi Linked List

int data;   //data bertipe integer

TNode *next; //pointer Next

};  //penutup deklarasi

TNode *head;  //disini menggunakan head sebagai pointer utama dari linked list

void init(){  //Fungsi untuk inisialisasi awal linked list

head=NULL;  //Untuk pertama kali, head bernilai NULL

}

int IsEmpty(){  //Fungsi untuk mengetahui apakah Linked list kosong atau ada isinya

if(head==NULL)  // apabila head==NULL, maka return 1

return 1;

else

return 0;  // Selain itu maka Return 0

}

void insertdepan(int n){ //Fungsi untuk menambahkan data baru (n didapat dari input di program utama (main))

TNode *baru;  //Disini menggunakan baru sebagai pointer TNode nya

baru=new TNode;

baru->data=n;  //pointer baru->data berisi nilai variabel n

baru->next=NULL;  // pointer baru->next berisi NULL

if(IsEmpty()==1){ //periksa apakah linked list bernilai, jika return 1(tidak bernilai), maka akan mengeksekusi perintah hingga ‘}’

head=baru; //Nilai head= Nilai baru

head->next=NULL;

}

else {   // Jika return 0(linked list bernilai), maka akan mengeksekusi perintah berikut hingga ‘}’

baru->next=head;

head=baru;

}

cout<<”Data Terisi”;

}

void insertbelakang(int n){    //Fungsi untuk insert Belakang(Menambahkan data di belakang data lama)

TNode *baru,*bantu;  //Pointer yang digunakan yaitu baru dan bantu

baru=new TNode;

baru->data=n;

baru->next=NULL;

if(IsEmpty()==1){

head=baru;

head->next=NULL;

}

else {

bantu=head;

while(bantu->next!=NULL){

bantu=bantu->next;

}

bantu->next=baru;

}

cout<<”Data Terisi”;

}

void tampil(){   //Fungsi untuk menampilkan linked list yang telah di input / di delete

TNode *bantu;  //pointer yang digunakan yaitu bantu

bantu=head;  // Nilai bantu= Nilai yang ada di head

if(IsEmpty()==0){  // periksa apakah return 0(bernilai)

while(bantu!=NULL){ //Selama bantu tidak sama dengan NULL, maka di eksekusi

cout<<bantu->data<<endl;  // tampilkan di monitor nilai bantu->data

bantu=bantu->next;  //Nilai bantu= nilai bantu selanjutnya

}

}

else

cout<<”Masih Kosong”<<endl;

}

void hapusdepan(){ //Fungsi untuk menghapus Nilai paling depan

TNode *hapus;

int d;

if(IsEmpty()==0){  //periksa apakah return 0(ada nilai)

if(head!=NULL){ // jika head tidak sama dengan Null maka :

hapus=head;  // pointer hapus= head

d=hapus->data;  //nilai dari d = nilai dari hapus->data

head=hapus->next;  // Nilai head sekarang berisi nilai hapus->next

delete hapus;  //fungsi untuk menghapus nilai yang ada  di pointer hapus

}

cout<<d<<” Terhapus”<<endl;

}

else

cout<<”Masih Kosong”<<endl;

}

main(){  // Fungsi Utama dari program

int pil;

do{

clrscr();

int n;

cout<<”1.Insert Depan”<<endl;

cout<<”2.Insert Belakang”<<endl;

cout<<”3.Display”<<endl;

cout<<”4.Delete”<<endl;

cout<<”5.Exit”<<endl;

cout<<”Masukan Pilihan Anda :”;pil=getche();

switch(pil){

case’1′: clrscr();

cout<<”Masukan data :”;cin>>n;

IsEmpty();

insertdepan(n);

break;

case’2′: clrscr();

cout<<”Masukan data :”;cin>>n;

IsEmpty();

insertbelakang(n);

break;

case’3′: clrscr();

IsEmpty();

tampil();

break;

case’4′: clrscr();

IsEmpty();

hapusdepan();

break;

}

getch();