STRUKTUR DATA GRAPHH:

Struktur Data Graph: Pengertian, Jenis, dan Kegunaannya


 Struktur data menyediakan cara dalam menyimpan data agar dapat dikelola dengan mudah, ditangani secara efektif, serta tertata dengan baik. 

Adanya berbagai jenis struktur data bertujuan untuk mengelola beberapa jenis data yang berbeda. Biasanya ada data yang perlu penanganan khusus yang tidak dapat disimpan dalam format sederhana.

Kita sebagai seorang yang bergelut di bidang IT dituntut agar memahami berbagai jenis struktur data agar dapat memilih struktur data yang tepat sesuai dengan kasus yang dihadapi.

Nah, di kesempatan ini, kita akan belajar salah satu struktur data yang tak kalah penting, yaitu graph.

Apa itu graph? Kita akan mengulasnya bersama-sama melalui artikel ini.

Pengertian Graph

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.graph seperti berikut:


Contoh Kasus Struktur Data Graph

Sumber: programiz.com

Graph di atas terdiri atas 4 buah verteks dan 4 pasang sisi atau edge. Dengan verteks disimbolkan sebagai V, edge dilambangkan E, dan graph disimbolkan G, ilustrasi di atas dapat ditulis dalam notasi berikut:


V = {0, 1, 2, 3}

E = {(0,1), (0,2), (0,3), (1,2)}

G = {V, E}

Graph banyak dimanfaatkan untuk menyelesaikan masalah dalam kehidupan nyata, dimana masalah tersebut perlu direpresentasikan atau diimajinasikan seperti sebuah jaringan. Contohnya adalah jejaring sosial (seperti Facebook, Instagram, LinkedIn, dkk)

Pengguna di Facebook dapat dimisalkan sebagai sebuah simpul atau verteks, sementara hubungan pertemanan antara pengguna tersebut dengan pengguna lain direpresentasikan sebagai edge. Tiap tiap verteks dapat berupa struktur yang mengandung informasi seperti id user, nama, gender, dll.

Jenis-jenis Graph

Graph dapat dibedakan berdasarkan arah jelajahnya dan ada tidaknya label bobot pada relasinya.

Berdasarkan arah jelajahnya graph dibagi menjadi Undirected graph dan Directed graph.

Karakteristik Graph

Graph memiliki beberapa karakteristik sebagai berikut:

Jarak maksimum dari sebuah simpul ke semua simpul lainnya dianggap sebagai eksentrisitas dari simpul tersebut.
Titik yang memiliki eksentrisitas minimum dianggap sebagai titik pusat dari graph.
Nilai eksentrisitas minimum dari semua simpul dianggap sebagai jari-jari dari graph terhubung

Fungsi dan Kegunaan Graph

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

Kelebihan Graph

Keunggulan dari struktur data graph adalah sbb:

  • Dengan menggunakan graph kita dapat dengan mudah menemukan jalur terpendek dan tetangga dari node
  • Graph digunakan untuk mengimplementasikan algoritma seperti DFS dan BFS.
  • Graph membantu dalam mengatur data.
  • Karena strukturnya yang non-linier, membantu dalam memahami masalah yang kompleks dan visualisasinya.

Kekurangan Graph

Adapun kekurangan dari struktur data graph di antaranya

Graph menggunakan banyak pointer yang bisa rumit untuk ditangani.
Memiliki kompleksitas memori yang besar.
Jika graph direpresentasikan dengan adjacency matrix maka edge tidak memungkinkan untuk sejajar dan operasi perkalian graph juga sulit dilakukan.


Penutup

Demikianlah penjelasan lengkap mengenai struktur data graph. Semoga bermanfaat.
Apabila suka dengan artikel seperti ini, Anda bisa mengunjungi rubrik Data Structure atau membaca artikel lainnya mengenai "Struktur Data Tree".

Komentar

Posting Komentar

Postingan populer dari blog ini

ALGORITMA A*(A STAR)

  Algoritma A* (A Star): Pengertian, Cara Kerja, dan Kegunaannya  Algoritma pencarian merupakan algoritma yang dirancang untuk mencari atau mengambil elemen dari struktur data, tempat data tersebut disimpan. Aspek vital dari algoritma pencarian adalah path finding, yang digunakan untuk menemukan jalur yang dapat diambil untuk melintasi dari satu titik ke titik lainnya, dengan mencari rute yang paling optimal.Salah satu algoritma pencarian yang digunakan sebagai path finding adalah algoritma A* atau A Star.Di artikel ini kita akan menjelaskan lebih detail mengenai pengertian, cara kerja, dan kegunaan algoritma A star. Pengertian Algoritma A* (A star) Algoritma A* (A Star) adalah algoritma pencarian yang digunakan untuk menemukan jalur terpendek antara titik awal dan akhir. Algoritma ini sering digunakan untuk penjelajahan peta guna menemukan jalur terpendek yang akan diambil. A* awalnya dirancang sebagai masalah penjelajahan graph (graph traversal), untuk membantu robot agar dapat menem
Baca selengkapnya

STRUKTUR DATA HEAP

Struktur Data Heap: Pengertian, Karakteristik, dan Operasinya Heap merupakan struktur data yang sangat berguna dan perlu diketahui dengan baik oleh setiap programmer. Struktur data heap digunakan dalam heap sort dan priority queue.Di blog ini, kita akan membahas lebih lanjut mengenai pengertian, karakteristik, dan operasi-operasi yang ada pada struktur data heap. Yuk, simak! Pengertian Struktur Data Heap Heap adalah  struktur data  berbentuk complete binary tree yang memenuhi heap property. Complete binary tree sendiri dapat didefinisikan sebagai binary tree di mana semua level terisi penuh, kecuali level terakhir. Semua kunci atau nilai pada level terakhir harus rata kiri apabila tidak terisi penuh. Adapun jenis-jenis heap property di antaranya: Max-Heap: Kunci atau nilai yang ada di simpul mana pun harus lebih besar dari kunci/nilai yang ada di kedua simpul anaknya. Kunci terbesar ada di simpul akar (root node). Min-Heap: Kunci yang ada di simpul mana pun harus lebih kecil dari kunc
Baca selengkapnya

STRUKTUR DATATREE

  Struktur Data Tree: Pengertian, Jenis, dan Kegunaannya Struktur data adalah cara atau teknik untuk mengatur elemen data ke dalam bentuk tertentu. Urutan dalam menyusun elemen data akan sangat menentukan apakah elemen data yang hendak diakses dapat diproses dalam waktu yang lebih singkat dan mudah atau tidak. Elemen data yang disusun secara berurutan dimana setiap elemen saling berdekatan antara satu elemen dengan elemen lain disebut sebagai struktur data linier. Contohnya seperti array, linked list, stack, dan queue.Selain struktur data linier, ada juga struktur data nonlinier, yaitu struktur data yang tidak kontigu atau tidak bertetangga. Salah satunya adalah tree. Pengertian Struktur Data Tree Tree adalah tipe struktur data yang sifatnya non-linier dan berbentuk hierarki.Mengapa tree disebut sebagai struktur data non-linier? Alasannya karena data pada tree tidak disimpan secara berurutan. Sebaliknya, data diatur pada beberapa level yang disebut struktur hierarkis. Karena itu, tree
Baca selengkapnya