MATERI KULIAH 04 September 2026 1 menit baca 5

Struktur Data & Algoritma: Graph

Graph merupakan struktur data yang digunakan untuk merepresentasikan hubungan antarobjek melalui vertex dan edge. Materi Sesi 9 membahas definisi graph, edge, bobot, path, derajat vertex, subgraph, graph terhubung dan lengkap, serta representasi graph menggunakan adjacency matrix dan adjacency linked list. Materi juga mengenalkan graph berarah, graph tidak berarah, loop, vertex terisolasi, lintasan berbobot, dan siklus.

## Konsep Dasar Graph

Graph merupakan struktur data yang lebih umum daripada tree. Tree dapat dipandang sebagai salah satu bentuk khusus dari graph. Graph digunakan untuk merepresentasikan hubungan antarelemen dalam berbagai persoalan nyata, seperti jaringan jalan, penerbangan antarkota, koneksi Internet, maupun hubungan antarkomputer.

Secara formal, sebuah graph dapat dinyatakan sebagai:

$$
G = (V,E)
$$

dengan $V$ sebagai himpunan **vertex** atau simpul dan $E$ sebagai himpunan **edge** atau garis. Vertex merupakan bagian fundamental dari graph. Sebuah vertex dapat mempunyai nama atau **key** dan dapat menyimpan informasi tambahan atau **payload**.

Edge menghubungkan dua vertex untuk menunjukkan adanya hubungan. Hubungan tersebut dapat bersifat satu arah atau dua arah. Jika seluruh edge pada graph mempunyai arah, graph tersebut disebut **directed graph** atau **digraph**. Sebaliknya, graph yang edge-nya tidak memiliki arah disebut **undirected graph**.

### Visual: Komponen Graph

## Istilah dan Sifat Graph

Edge dapat diberi **bobot** untuk menunjukkan biaya perpindahan dari satu vertex ke vertex lain. Dalam graph jalan, misalnya, bobot dapat digunakan untuk menyatakan jarak antarkota. Graph berbobot dapat digunakan untuk menentukan lintasan dengan biaya tertentu.

Dua vertex disebut **bertetangga** apabila keduanya dihubungkan oleh sebuah edge. Sebuah edge juga dapat menghubungkan sebuah vertex dengan dirinya sendiri. Kondisi ini disebut **loop** atau kalang.

Vertex yang tidak terhubung dengan vertex lain disebut **vertex terisolasi**. Sementara itu, **derajat vertex** didefinisikan sebagai jumlah edge yang melibatkan vertex tersebut.

Graph juga dapat memiliki hubungan yang lebih kompleks. **Subgraph** adalah graph yang himpunan vertex dan edge-nya merupakan bagian dari graph yang lebih besar. Graph tidak berarah disebut terhubung apabila setiap vertex dapat mencapai vertex lain, baik secara langsung maupun melalui vertex perantara. Graph disebut lengkap apabila setiap vertex terhubung dengan vertex lainnya melalui edge.

## Path, Siklus, dan Lintasan Berbobot

**Path** atau lintasan merupakan urutan vertex yang saling dihubungkan oleh edge. Secara formal, sebuah path dapat dinyatakan sebagai:

$$
w_1,w_2,\ldots,w_n
$$

dengan hubungan:

$$
(w_i,w_{i+1}) \in E
$$

untuk $1 \leq i \leq n-1$.

Panjang lintasan tidak berbobot merupakan jumlah edge yang dilewati. Jika lintasan terdiri atas $n$ vertex, panjangnya adalah $n-1$. Pada lintasan berbobot, panjang lintasan dihitung dengan menjumlahkan bobot seluruh edge yang dilalui.

Graph juga dapat mempunyai **siklus**, yaitu path yang berawal dan berakhir pada vertex yang sama. Graph yang tidak memiliki siklus disebut graph asiklik. Jika graph berarah tidak mempunyai siklus, graph tersebut disebut **Directed Acyclic Graph (DAG)**.

## Representasi Graph

Terdapat dua metode yang umum digunakan untuk menyatakan graph, yaitu **adjacency matrix** dan **adjacency linked list**.

Pada **adjacency matrix**, hubungan antarvertex direpresentasikan menggunakan array dua dimensi. Untuk graph tidak berarah, elemen $L_{ij}$ diberi nilai $1$ apabila vertex $i$ dan vertex $j$ terhubung oleh edge. Sebaliknya, nilai $0$ digunakan apabila keduanya tidak memiliki edge. Karena hubungan graph tidak berarah bersifat dua arah, nilai $L_{ij}$ dan $L_{ji}$ akan menunjukkan hubungan yang sama.

Selain matriks, graph dapat direpresentasikan menggunakan **adjacency linked list**. Representasi ini menggunakan list untuk menyimpan vertex-vertex yang bertetangga dengan setiap vertex. Pemilihan representasi bergantung pada karakteristik graph dan kebutuhan operasi yang dilakukan terhadapnya.

### Visual: Adjacency Matrix dan Adjacency List

## Kesimpulan

Graph merupakan struktur data yang efektif untuk merepresentasikan hubungan antarobjek. Komponen utamanya adalah vertex dan edge, sedangkan bobot dapat digunakan untuk menyatakan biaya atau jarak. Graph dapat berupa berarah atau tidak berarah, memiliki loop, vertex terisolasi, subgraph, lintasan, dan siklus.

Dalam pemrograman, graph dapat direpresentasikan menggunakan adjacency matrix maupun adjacency linked list. Pemahaman terhadap komponen, sifat, lintasan, dan representasi graph menjadi dasar untuk menerapkan algoritme graph pada persoalan seperti pencarian jalur, hubungan jaringan, dan berbagai masalah yang memiliki struktur hubungan antarelemen.

#struktur data #algoritma #pemrograman #graph #informatika #grafik #vertex #edge #simpul #garis #graph berarah #graph tidak berarah #bobot #path #lintasan #derajat vertex #subgraph #adjacency matrix #adjacency linked list #siklus #DAG

Komentar (0)

Belum ada komentar. Jadi yang pertama berkomentar di bawah.

Struktur Data & Algoritma: Graph

Komentar (0)

Tulis Komentar

Artikel Terkait

Estetika Humanisme: Psikologi Humanistik

Estetika Humanisme: Leadership

Estetika Humanisme: Manajemen Konflik