Graph Data Structure - Depth First Traversal - Breadth First Traversal

1. Graph Data Structure

Graph merupakan struktur data non-linier yang merepresentasikan visual dari beberapa simpul yang saling terhubung melalui sisi - sisi. Graph digunakan untuk merepresentasikan hubungan atau ketertarikan antara objek atau entitas yang berbeda. Graph pada dasarnya terdiri dari dua komponen utama, yaitu:

1.    Node

Node dalam graph direpresentasikan juga sebagai vertex. Node merupakan sebuah entitas individu didalam graph. Setiap node dapat merepresentasikan objek, entitas, atau elemen tertentu. Contohnya node dalam graph sosial bisa berupa manusia.

2.    Edge

Edge merupakan sebuah hubungan atau koneksi antara dua node dalam graph. Edge dapat menggambarkan berbagai jenis relasi antara node - node didalam graph.

2. Jenis - Jenis Graph

Graph dapat dibedakan berdasarkan arah jelajahnya dan ada atau tidaknya label bobot pada relasinya, untuk jenis - jenisnya dari graph diantaranya:

1.    Berdasarkan arah jelajah

a.    Undirected Graph

Pada undirected graph simpul - simpulnya terhubung dengan edge yang sifatnya dua arah. Lebih jelasnya dapat dilihat pada gambar dibawah yang dimana setiap simpul saling terhubung, sehingga kita bisa menjelajah dari simpul ke simpul begitu juga sebaliknya.

b.    Directed Graph

Pada directed graph simpul - simpulnya terhubung oleh edge dan hanya bisa melakukan jelajah satu arah pada simpul yang dituju. Lebih jelasnya dapat dilihat pada gambar dibawah yang dimana setiap simpul saling terhubung akan tetapi setiap edge memiliki arah, sehingga hanya dapat berjalan searah.

2.    Berdasarkan ada atau tidaknya label bobot

a.    Weighted Graph

Weighted graph merupakan jenis graph yang pada cabangnya diberi label bobot berupa bilangan numerik. Pemberian label bobot pada edge biasanya digunakan untuk memudahkan algoritma dalam menyelesaikan masalah. Lebih jelasnya dapat dilihat pada gambar dibawah 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.

b.    Unweighted Graph

Unweighted graph merupakan jenis graph yang di mana setiap edge atau sisinya tidak memiliki bobot atau nilai terkait. Dalam unweighted graph, setiap edge diperlakukan secara sama tanpa mempertimbangkan nilai atau jarak di antara dua simpul atau node yang terhubung. Graph ini hanya mempertimbangkan apakah dua node saling terhubung atau tidak.

3. Implementasi dari graph

Contoh Implementasi dari graph, diantaranya:

●     Graph digunakan untuk merepresentasikan aliran komputasi.

●     Graph 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.

4. Depth First Traversal

Depth First Traversal (DFS) merupakan salah satu algoritma pencarian yang sering digunakan pada struktur data graph. DFS merupakan algoritma pencarian yang melakukan eksplorasi sejauh mungkin ke dalam graph sebelum kembali. DFS menggunakan pendekatan "mendalam" dalam penelusuran graph. Jika ada lebih dari satu cabang pada simpul yang dikunjungi, DFS akan mengikuti salah satu cabang hingga mencapai simpul terakhir dalam cabang itu sebelum kembali untuk melanjutkan penelusuran pada cabang lainnya.

5. Breadth First Traversal

Breadth First Traversal (BFS) merupakan salah satu algoritma pencarian yang sering digunakan pada struktur data graph. BFS adalah algoritma pencarian yang melibatkan penjelajahan secara meluas pada level-level yang berbeda dalam graph. BFS menggunakan pendekatan "meluas" dalam penelusuran graph. Pada setiap langkah penelusuran, semua simpul tetangga yang belum dikunjungi pada level yang sama akan dijelajahi terlebih dahulu sebelum pindah ke level berikutnya.