Pengertian dan Konsep Graph dalam Struktur Data

GRAPH

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 ata u arc). biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).
contoh implementasi graf pada struktur data :

1. 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.

2. 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).

Digraph & Undigraph

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). 

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. 


Selain itu, berdasarkan definisi ini maka struktur data linear maupun hirarkis adalah juga graph. Node-node pada struktur linear atupun hirarkis adalah verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node tersebut secara linear atau hirarkis. Sementara kita telah ketahui bahwa struktur data linear adalah juga tree dengan pencabangan pada setiap node hanya satu atau tidak ada. Linear 1-way linked list adalah digraph, linear 2-way linked list bisa disebut undigraph. 

Aspek Algoritmis

Walau secara konseptual struktur linear adalah subset dari tree dan demikian pula tree adalah subset dari graph, dalam aplikasinya perlu dibedakan cara penanganan struktur-struktur tersebut untuk mencapai efisiensi algoritmis. Algoritma-algoritma untuk graph secara umum terlalu mahal apabila digunakan pada struktur hirarkis (tree), apalagi pada struktur linear. Jadi apabila masalah yang dihadapi pada dasarnya hanya merupakan masalah dengan struktur data hirarkis saja maka cukup lah kita menggunakan representasi dan algoritma-algoritma tree.

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.
• Siklus sederhana: dalan undigraph, siklus yang terbentuk pada tiga atau lebih verteks-verteks yang berlainan yang mana tidak ada verteks yang dikunjungi lebih dari satu kali kecuali verteks awal/akhir.
• Dua verteks x dan y yang berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika terdapat path yang menghubungkannya.
• Himpunan bagian verteks S disebut terkoneksi (connected) apabila dari setiap verteks x dalam S terdapat path ke setiap verteks y (y bukan x) dalam S.
• Suatu komponen terkoneksi (connected components) adalah subgraph (bagian dari graph) yang berisikan satu himpunan bagian verteks yang berkoneksi.
• Suatu undigraph dapat terbagi atas beberapa komponen yang terkoneksi; jika terdapat lebih dari satu komponen terkoneksi maka tidak terdapat path dari suatu verteks dalam satu komponen verteks di komponen lainnya.
• Pohon bebas (free tree): suatu undigraph yang hanya terdapat satu komponen terkoneksi serta tidak memiliki siklus sederhana.

Konektivitas pada Digraph

Terminologi di atas berlaku juga pada Digraph kecuali dalam digraph harus dikaitkan dengan arah tertentu karena pada arah yang sebaliknya belum tentu terdefinisi.

• 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).

Himpunan Keterhubungan Langsung

Cara pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan langsung Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan dari verteks-verteks yang adjacent dari x. Secara formal:

Vx = {y | (x,y) Î E}

Dalam digraph didefinisikan juga terminologi-terminologi berikut ini. Predesesor dari suatu verteks x (ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x. Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks yang adjacent dari x; yaitu adjacency set di atas. .

Degree

• Degree dari suatu verteks x dalam undigraph adalah jumlah sisi di mana di salah satu ujungnya terdapat x.
• Indegree dari suatu verteks x dalam digraph adalah jumlah dari predesesor x.
• Outdegree dari suatu verteks x dalam digraph adalah jumlah dari suksesor x.

Graph berbobot (weighted graph)

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. Dalam beberapa masalah lain bisa juga bobot tersebut memiliki pengertian "laba" yang berarti kebalikan dari "biaya" di atas. Dalam pembahasan algoritma-algoritma graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan dengan mencari laba maksimum.

Download disini

Dosen Pengampuh

 

Nama                                                  : M.Ropianto

NIDN                                                   : 102867804

Status                                                 : Dosen Tetap YAPISTA / STT Ibnu Sina

Pengampuh Mata kuliah                        : Struktur Data

Kunjungi Juga :

STT Ibnu Sina Batam 

Tipe Data Dalam PHP

Dalam PHP tipe data tidak dideklarasikan oleh programmer akan tetapi ditentukan secara otomatis oleh Intepreter PHP. Jadi anda tidak perlu deklarasikan tipe data tersebut jika ingin memberikan nilai pada suatu variabel. Anda dapat menuliskan fungsi gettype() untuk mengetahui type data dari nilai yang anda berikan.

           <?php
                $a = 0.3;
                $b = -3;
                $c = "Hallo Berooo";
                echo "$a adalah type data ". gettype($a)."<br />";
                echo "$b adalah type data ". gettype($b)."<br />";
                echo "$c adalah type data ". gettype($c)."<br />";
           ?>

Ada 8 macam tipe data pada PHP, diantaranya :

    1. Integer

Tipe data integer adalah tipe data yang berguna untuk menyimpan bilangan bulat, bukan desimal. Sebagai contoh (1),(2),(3),(4),(5),(-1),(-2),(-3),(-4) dan lain-lain. Tipe data ini memiliki range antara -2,147,483,648 sampai dengan +2,147,483,648 platform 32bit.

Namun bila terdapat data diluar jangkauan tersebut, maka secara otomatis PHP akan mengkonversikannya ke dalam tipe data Floating Point.

Integer merupakan Tipe Data yang berisikan bilangan bulat negatif dan positif atau tanpa ada nilai pecahan.

Tipe ini juga dapat dinyatakan dalam bentuk oktal (berbasis 8), desimal (berbasis 10), heksadesimal (berbasis 16). Seperti dalam contoh berikut :

            $oktal = 031;

            $desimal = 25;

            $heksadesimal = 0×10;

     2. Double Floating

Tipe data floating point numbers biasa juga disebut dengan “double”, ” float” atau “real” adalah tipe data yang berguna untuk menyimpan bilangan desimal. Sebagai contoh (0.1),(1.3),(1.7),(1.8),(9.7),(2.4) dan lain-lain.

Contoh penulisannya :

<?php

          $a = 1.234;

         $b = 1.2e3;

        $c = 2E-6;

        $d = 1.2E8;

?>

     3. Boolean dan string="0" mempunyai boolean false, selain itu true.

Tipe Data ini adalah tipe data yang paling sederhana. Hanya berupa true atau false. Cara memasukan ke dalam variabel adalah dengan memberikan nilai true atau falsepada variabel tersebut. Penulisannya tidak dipengaruhi penggunaan huruf besar atau kecil.

Contoh penulisannya :

     <?php

              $a = TRUE; // bernilai 1

             $b = true; // bernilai 1

             $c = FALSE; // bernilai 0

            $d = false; // bernilai 0

      ?>

 Setiap Tipe Data dalam PHP mempunyai Boolean untuk melakukan Seleksi Kondisi. dan .Tipe Data tersebut akan memberikan nilai true atau false pada seleksi kondisi tersebut.

    . Pada Variabel yang bertipe Data integer=0 (nol) mempunyai boolean false, selain itu true.

    . Pada Variabel yang bertipe Data float=0.0 (nol) mempunyai boolean false, selain itu true.

    . Pada Tipe Data string yang kosong,

    . Array yang tidak mempunyai element mempunyai boolean false, selain itu true.

    .Objek yang tidak mempunyai member mempunyai boolean false, selain itu true.

    .Tipe NULL dan Variabel yang belum terisi mempunyai boolean false.

     4.   String

String adalah sebuah tipe data yang terdiri dari kata, bisa berupa kata tunggal maupun kalimat. Penulisan string harus diapit oleh tanda petik, baik petik tunggal(‘ ‘) maupun petik ganda (” “)

Contoh penulisan tipe data string :
	<?php          $kata1 = 'string diapit petik tunggal';          $kata2 = "string diapit petik ganda"; ?>

Perbedaan antara petik ganda dan petik tunggal adalah, ketika kita menggunakan petik tunggal maka variabel tidak akan terbaca nilainya. Beda halnya dengan penggunaan petik genap yang akan membaca nilai dari suatu variabel.

Lebih spesifiknya :

<?php

           $kata = "Haloo Berooo";

           echo 'nama saya adalah $kata';

                     //jika menggunakan tanda petik tunggal browser

                   //akan menampilkan $kata

          echo "nama saya adalah $kata";

                    //jika menggunakan tanda petik tunggal browser

                   //akan menampilkan Haloo Beroo

?>

Jika string yang tertutup dalam tanda kutip ganda (” “), PHP akan menafsirkan escape sequence lebih untuk karakter khusus. Maka penulisan untuk karakter khusus tersebut harus ditambahkan slash didepan karakter tersebut.                                                               

     5.   Objek

Tipe data object dibuat dengan tujuan agar para programmer terbiasa dengan OOP. Tipe data object bisa berupa bilangan, variabel atau fungsi. Data ini dapat dimasukkan ke dalam kode program sehingga meringkas beberapa fungsi dan memperkecil ukuran file.

Agar lebih mudah dapat menggunakan variabel dengan nilai string :

class Nama {

               var $jenis = “Beroo Haloo”;

                function ganti_nama($jenis) {

                 $this->jenis = $jenis;

                }

}

$nama = new Nama;

echo $nama->jenis;

$nama->ganti_nama(“Haloo Beroo”);

echo “<br>”.$nama->jenis;

Hasilnya :

Beroo Haloo

Haloo Beroo

  

 6.   Array

Array atau Larik merupakan Tipe Compound Primitif, terdapat pada bahasa-bahasa pemrograman lain.

Tipe data array digunakan untuk menyimpan banyak data dalam satu variabel. Jenis array dalam php ada 3 (tiga) macam yakni :

·            Numeric Array

<?php

          $hari[0]="Senin";

          $hari[1]="Selasa";

          $hari[2]="Rabu";

          $hari[3]="Kamis";

          $hari[4]="Jum'at";

          $hari[5]="Sabtu";

          $hari[6]="Minggu";

                     //menampilkan tanpa perulangan.

           echo "sekarang adalah hari $hari[3] <br />" ;

                   //menampilkan menggunakan perulangan

                 //perulangan akan dijelaskan pada artikel berikutnya

           for($i=0;$i<=6;$i++){

                   echo $hari[$i]."<br/>";

           }

   ?>

Pada contoh numeric array diatas dapat disimpulkan bahwa pemanggilan data array tersebut menggunakan angka, angka dimulai dari 0 sampai jumlah data yang dimasukkan. $hari[0] adalah pemanggilan untuk data pertama, $hari[1] adalah pemanggilan untuk data kedua dan seterusnya.

·            Associative Array

<?php

$hari = array("Senin"=>"Ayam","Selasa"=>"Lele","Rabu"=>"Tempe","Kamis"=>"Tahu","Jum'at"=>"Teri","Sabtu"=>"Krupuk","Minggu"=>"Puasa");

    //menampilkan tanpa perulangan.

echo "Menu hari senin adalah $hari[Senin]" ;

?>

Pada contoh associative array diatas dapat disimpulkan bahwa pemanggilan data array tersebut menggunakan string yang ditentukan oleh kita, dengan kata lain pemanggilan menggunakan angka kita ganti menjadi string yang kita inginkan.

·         Multidimensional Array

Pengertian multidimension array adalah array didalam array. Pemanggilan array ini bisa menggunakan numeric array maupun associative array. $makan[0]["pagi"] dapat diartikan sebagai menampilkan nilai array pertama dan array pagi dari variabel makan, $makan["senin"]["pagi"] dapat diartikan sebagai menampilkan nilai array senin dan array pagi dari variabel makan.

<?php

       $makan = array(

              array("pagi"=>"bubur","siang"=>"ayam","sore"=>"bebek"),

             array("pagi"=>"bubur","siang"=>"tahu","sore"=>"tempe")

        );

             //menampilkan tanpa perulangan.

         echo "Menu makan pada hari senin pagi adalah " . $makan[0]["pagi"];

        echo "<br />";

        echo "Menu makan pada hari senin pagi adalah " . $makan[1]["sore"];

?>

     7.   Null

NULL adalah Tipe Data yang tidak memuat apapun. Setiap Variabel yang diset menjadi Tipe Data NULL ini akan menjadikan Variabel tersebut kosong, seperti dalam penggunaan fungsi unset(). Cara untuk menset Variabel menjadi NULL adalah dengan memasukan nilai NULL pada variabel yang dimaksud seperti pada

Contoh berikut:

<?php 

    # Nilai awal $foo adalan 10 

    $foo = 10; 

     # $foo akan menjadi NULL 

    $foo = NULL;      

    # Sama dengan memanggil unset() 

    unset($foo); 

?> 

     8.   Resources

Tipe Data Spesial yang satu ini di khususkan untuk menyimpan resource, sumber atau alamat. Variabel tersebut hanya dapat diciptakan oleh suatu fungsi khusus yang mengembalikan nilai berupa resource seperti penggunaan fungsi fopen, opendir, mysql_connect, mysql_query dan semacamnya.

 Download disini

Dosen Pengampuh


Nama                                                  : M.Ropianto

NIDN                                                   : 102867804

Status                                                 : Dosen Tetap YAPISTA / STT Ibnu Sina

Pengampuh Mata kuliah                        : Algoritma & Pemrograman II

Kunjungi Juga:

STT Ibnu Sina Batam