struktur data graph

STRUKTUR DATA GRAPH


pengertian 

Graph adalah jenis struktur data umum yang susunan datanya tidak berdekatan satu sama lain (non-linier). Graph terdiri dari kumpulan simpul berhingga untuk menyimpan data dan antara dua buah simpul terdapat hubungan saling keterkaitan.Simpul pada graph disebut dengan verteks (V), sedangkan sisi yang menghubungkan antar verteks disebut edge (E). Pasangan (x,y) disebut sebagai edge, yang menyatakan bahwa simpul x terhubung ke simpul y.

jenis - jenis


 undirected Graph

Pada undirected graph, simpul-simpulnya terhubung dengan edge yang sifatnya dua arah. Misalnya kita punya simpul 1 dan 2 yang saling terhubung, kita bisa menjelajah dari simpul 1 ke simpul 2, begitu juga sebaliknya.

Directed Graph


Kebalikan dari undirected graph, pada graph jenis ini simpul-simpulnya terhubung oleh edge yang hanya bisa melakukan jelajah satu arah pada simpul yang ditunjuk. Sebagai contoh jika ada simpul A yang terhubung ke simpul B, namun arah panahnya menuju simpul B, maka kita hanya bisa melakukan jelajah (traversing) dari simpul A ke simpul B, dan tidak berlaku sebaliknya.

 label bobot pada koneksinya, yaitu weighted graph dan unweighted graph.

Weighted Graph


Weighted graph adalah jenis graph yang cabangnya diberi label bobot berupa bilangan numerik. Pemberian label bobot pada edge biasanya digunakan untuk memudahkan algoritma dalam menyelesaikan masalah.


Contoh implementasinya misalkan kita ingin menyelesaikan masalah dalam mencari rute terpendek dari lokasi A ke lokasi D, namun kita juga dituntut untuk mempertimbangkan kepadatan lalu lintas, panjang jalan dll. Untuk masalah seperti ini, kita bisa mengasosiasikan sebuah edge e dengan bobot w(e) berupa bilangan ril.

Nilai bobot ini bisa apa saja yang relevan untuk masalah yang dihadapi: misalnya jarak, kepadatan, durasi, biaya, probabilitas, dan sebagainya.

Unweighted Graph

Berbeda dengan jenis sebelumnya, unweighted graph tidak memiliki properti bobot pada koneksinya. Graph ini hanya mempertimbangkan apakah dua node saling terhubung atau tidak.

kegunaan

Fungsi dan kegunaan graph di antaranya:

Graph digunakan untuk merepresentasikan aliran komputasi.

Digunakan dalam pemodelan grafik.

Graph dipakai pada sistem operasi untuk alokasi sumber daya.

Google maps menggunakan graph untuk menemukan rute terpendek.

Graph digunakan dalam sistem penerbangan untuk optimasi rute yang efektif.

Pada state-transition diagram, graph digunakan untuk mewakili state dan transisinya.

Di sirkuit, graph dapat digunakan untuk mewakili titik sirkuit sebagai node dan kabel sebagai edge.

Graph digunakan dalam memecahkan teka-teki dengan hanya satu solusi, seperti labirin.

Graph digunakan dalam jaringan komputer untuk aplikasi Peer to peer (P2P).

Umumnya graph dalam bentuk DAG (Directed acyclic graph) digunakan sebagai alternatif blockchain untuk cryptocurrency. Misalnya crypto seperti IOTA

Komentar

Posting Komentar

Postingan populer dari blog ini

algoritma pemrograman

ALGORITMA PEMROGRAMAN  pengertian  Algoritma pemrograman adalah langkah atau instruksi sistematis yang dipergunakan dalam perhitungan atau pemecahan masalah. Dalam aktivitas pemrograman, algoritma digunakan untuk membuat dan mengembangkan program menggunakan alur logika tertentu. Algoritma merupakan tahapan awal sekaligus aspek paling dasar dalam pembuatan program. Pasalnya, ketika pengembang membuat suatu program menggunakan bahasa pemrograman apapun, hasil akhirnya tetap bergantung pada penulisan algoritma. fungsi  Secara garis besar, algoritma berfungsi untuk untuk memecahkan masalah. Seperti yang telah Dewaweb singgung bahwa logika merupakan aspek penting yang menjadi dasar pembuatan program. Adapun fungsi lain algoritma pemrograman, di antaranya: Memecahkan masalah pada program yang melibatkan perhitungan-perhitungan rumit. Alur prosesnya jelas sehingga kamu dapat menemukan titik kesalahan secara akurat ketika mendapati bug atau error. Penggunaan yang lebih efektif dan efisien kar
Baca selengkapnya

literasi sains

  LITERASI SAINS pengertian  Literasi sains adalah kemampuan untuk membaca, memahami, mengevaluasi, dan menggunakan informasi dan pengetahuan sains untuk membuat keputusan yang tepat dan berpikir kritis dalam kehidupan sehari-hari. Literasi sains bukan hanya tentang memahami konsep-konsep sains, tetapi juga tentang memahami bagaimana sains diterapkan dalam kehidupan nyata. Seseorang yang memiliki literasi sains yang baik dapat mengenali dan memahami masalah sains, menemukan informasi sains yang diperlukan, mengevaluasi kebenaran dan validitas informasi sains, serta menggunakannya untuk membuat keputusan yang berbasis fakta. Literasi sains juga mencakup kemampuan untuk berkomunikasi tentang konsep-konsep sains secara jelas dan efektif dengan orang lain. Pentingnya literasi sains terletak pada keterampilan dan pemahaman yang diperlukan untuk mengambil keputusan berdasarkan fakta dan bukti-bukti yang ada, terutama dalam hal-hal yang terkait dengan kesehatan, lingkungan, teknologi, dan keb
Baca selengkapnya

DATA NAMA

NAMA     : ANGGUN WIDYA KARTIKA  TTL          :KEDIRI,04 MEI 2011 KELAS.    :8A ABSEN.    : 05 ALAMAT : DSN.KARTOSARI , RT 02 ,RW 01 ,DS KANDAT ,KEC.KANDAT ,KAB. KEDIRI EMAIL     : anggunwidyakartika@gmail.com  SITUS       :https://anggunwidyakartika.blogspot.com/?m=1 IG                   :@wdya_4511 TT                   :@wdya_4511 FB                   :Anggun Widya Kartika HOBBY           : MEMASAK MAKANAN F :BAKSO MINUMAN F. : ES TEH                    
Baca selengkapnya