Jawaban dari "Jelaskan tentang graph dalam struktur data"

Jika kamu sedang melihat jawaban mengenai soal Jelaskan tentang graph dalam struktur data kamu berada di halaman yang tepat. Kami mempunyai 1 jawaban mengenai Jelaskan tentang graph dalam struktur data. Silakan lihat jawaban selanjutnya di bawah ini:

Jawaban:

• Teori graf mempelajari tentang graf yaitu struktur yang menggambarkan relasi antar objek dari sebuah koleksi objek.

• Suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung oleh sisi (atau edge atau arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Definisi tersebut dituangkan dalam notasi matematika sebagai

berikut : G = (V,E) dimana :

G = graf

V = himpunan tidak kosong dan berhingga dari simpul-simpul

(verteks) = v1, v2, … , vn

E = himpunan sisi (edges) yang menghubungkan sepasang simpul =

e1, e2, … , en

Penjelasan:

Dalam bidang ilmu komputer, sebuah graf dapat dinyatakan sebagai sebuah struktur data, atau secara spesifik dinamakan sebagai ADT (abstract data type) yang terdiri dari kumpulan simpul dan sisi yang membangun hubungan antar simpul. Konsep ADT graf ini merupakan turunan konsep graf dari bidang kajian matematika.

• Jika berbicara masalah implementasi struktur data graf, isu utama yang dihadapi adalah bagaimana informasi itu disimpan dan dapat diakses dengan baik, ini yang dapat disebut dengan representasi internal.

• Secara umum terdapat dua macam representasi dari struktur data graf yang dapat diimplementasi. Pertama, disebut adjacency list, dan diimplementasi dengan menampilkan masing-masing simpul sebagai sebuah struktur data yang mengandung senarai dari semua simpul yang saling berhubungan.

• Yang kedua adalah representasi berupa adjacency matrix dimana baris dan kolom dari matriks (jika dalam konteks implementasi berupa senarai dua dimensi) tersebut merepresentasikan simpul awal dan simpul tujuan dan sebuah entri di dalam senarai yang menyatakan apakah terdapat sisi di antara kedua simpul tersebut.

Ada dua traversal (penelusuran) graf yang fundamental, yaitu Breadth First

Search dan Depth First Search.

Breadth First Search (BFS) dan Depth First Search (DFS) adalah dua traversal berbeda yang

berjalan mengunjungi simpul dan sisi pada graf.

• BFS (pencarian melebar) bermula dari suatu akar dan akan mengunjungi simpul tujuan dengan urutan bergantung pada jarak mereka dari akar. Tentu akibatnya, simpul terdekat akandikunjungi terlebih dahulu.

• DFS (pencarian mendalam) lebih memilih untuk mengunjungi langsung, simpul yang belum ditemukan, sehingga pohon pencarian (search tree) hasil traversal akan lebih dalam,dibandingkan dengan BFS, yang akan lebih seimbang.