Pengertian dan Penjelasan tentang Garph pada struktur data

assalamualaikum

pada artikel kali ini admin bocah ngoding akan berbagi ilmu nih tentang Pengertian dan Penjelasan tentang Garph pada struktur data. graph identik dengan pencarian sebuah nilai atau data dimana data akan dicari berdasarkan jalur dari satu data ke data yang lain. oke simak penjelasan lengapnya.

Graph

Graph adalah kumpulan node (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 node, bulatan atau titik (vertex), sedangkan hubungan antara objek dinyatakan dengan garis (edge). ^[1]

G = (V, E)

Dengan :

G = Graph

V = Simpul atau vertex, atau node, atau Titik

E = Busur atau edge

Gambar 5 .1 Ilustrasi graph

Terdapat beberapa istilah yang berkaitan dengan graph yaitu ^[10]:

Vertex

Vertex adalah himpunan node atau titik pada sebuah graph.

Edge

Edge adalah himpunan garis yang menghubungkan tiap node atau vertex.

Adjacent

Dua buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut.

Incident

Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e = (v,w), maka v dan w disebut “terletak” pada e dan e disebut incident dengan v dan w.

Degree

Degree adalah jumlah busur yang incident dengan simpul.

Path

Path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya

Jenis - Jenis Graph

Berikut ini jenis – jenis graph ^[7]:

Graph tak berarah (undirected graph atau non-directed graph)

Graph tak berarah adalah graph dimana urutan simpul dalam sebuah busur tidak dipentingkan.

Gambar 5 .2 Graph tak berarah

Graph berarah (directed graph)

Graph berarah adalah graph dimana urutan simpul dalam sebuah busur memiliki arti atau dipentingkan.

Gambar 5 . 3 Graph berarah

Metode Pencarian Vertex

Pencarian vertex adalah proses umum dalam graph. Terdapat 2 metode pencarian, yakni Depth First Search (DFS) dan Breadth First Search (BFS).

Depth First Search (DFS)

Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi.^[1]

Gambar 5 . 4 Depth first searc h

Proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan akhir ( goal). Depth first search memiliki kelebihan diantaranya adalah cepat mencapai kedalaman ruang pencarian.^[1]

Breadth First Search (BFS)

Breadth first search (BFS) merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap level hingga keadaan tujuan (goal state) ditemukan. Atau dengan kata lain, penelusuran yang dilakukan adalah dengan mengunjungi tiap-tiap node padalevel yang sama hingga ditemukan goal state-nya. ^[1]

Gambar 5 . 5 Breadth first searc h

Pengimplementasian BFS dapat ditelusuri dengan menggunakan daftar ( list), open dan closed, untuk menelusuri gerakan pencarian di dalam ruang keadaan. Keuntungan menggunakan breadth first search ini, diantaranya adalah tidak akan menemui jalan buntu dan jika ada satu solusi maka breadth first search akan menemukannya, dan jika ada lebih dari satu solusi maka solusi minimum akan ditemukan.^[1]