Graph (Graf)

---

🧭 1. Pengertian Graph

6

📖 Definisi

Graph adalah struktur data non-linear yang terdiri dari sekumpulan simpul (vertex/node) dan sisi (edge) yang menghubungkan antar simpul.

---

🧠 Narasi Konseptual

Bayangkan peta jalan antar kota:

• Kota = node (vertex)
• Jalan = edge (garis penghubung)

➡️ Graph digunakan untuk merepresentasikan hubungan antar objek dalam dunia nyata.

---

🎯 2. Komponen Graph

📊 Tabel Komponen

Komponen	Penjelasan
Vertex (V)	Titik/node
Edge (E)	Hubungan antar vertex
Path	Jalur antar node
Degree	Jumlah edge pada node

---

🧠 Narasi

Graph tidak hanya menyimpan data, tetapi juga hubungan antar data.

---

🔄 3. Jenis Graph

---

🔹 A. Undirected Graph

8

📖 Konsep

Edge tidak memiliki arah.

🧠 Narasi

Seperti hubungan pertemanan:

• Jika A berteman dengan B
• Maka B juga berteman dengan A

---

🔹 B. Directed Graph (Digraph)

8

📖 Konsep

Edge memiliki arah.

🧠 Narasi

Seperti Instagram:

• A follow B ≠ B follow A

---

🔹 C. Weighted Graph

6

📖 Konsep

Setiap edge memiliki bobot (cost, jarak, waktu).

---

🧠 Narasi

Seperti peta jalan:

• Setiap jalan punya jarak atau biaya

---

🧱 4. Representasi Graph

---

🔹 A. Adjacency Matrix

7

📖 Konsep

Graph direpresentasikan dalam bentuk matriks 2D.

---

📊 Contoh

	A	B	C
A	0	1	1
B	1	0	0
C	1	0	0

---

🧠 Narasi

• 1 = ada hubungan
• 0 = tidak ada hubungan

---

🔹 B. Adjacency List

4

📖 Konsep

Setiap node menyimpan daftar tetangga.

---

💻 Contoh

A → B, C  
B → A  
C → A  

---

🧠 Narasi

Lebih hemat memori dibanding matriks.

---

🔍 5. Traversal Graph

---

🔹 A. BFS (Breadth First Search)

6

📖 Konsep

Menjelajahi graph per level (melebar) menggunakan queue.

---

🧠 Narasi

Seperti menyebarkan informasi:

• Dari satu orang ke semua teman
• Lalu ke teman dari teman

---

⏱️ Kompleksitas

➡️ O(V + E)

---

🔹 B. DFS (Depth First Search)

6

📖 Konsep

Menjelajahi graph sedalam mungkin terlebih dahulu menggunakan stack/rekursi.

---

🧠 Narasi

Seperti menjelajah labirin:

• Masuk jauh dulu
• Jika buntu, kembali (backtracking)

---

⏱️ Kompleksitas

➡️ O(V + E)

---

⚙️ 6. Operasi Graph

📊 Tabel Operasi

Operasi	Deskripsi
Add Vertex	Menambah node
Add Edge	Menambah hubungan
Remove Vertex	Menghapus node
Remove Edge	Menghapus hubungan
Traversal	BFS/DFS

---

📊 7. Perbandingan Representasi Graph

📊 Tabel

Aspek	Matrix	List
Memori	Boros	Hemat
Akses Edge	Cepat	Lambat
Cocok untuk	Dense graph	Sparse graph

---

🌐 8. Aplikasi Graph dalam Dunia Nyata

📌 Contoh Penggunaan

Bidang	Contoh
Media Sosial	Friend / follow
GPS	Rute jalan
Internet	Routing jaringan
Game	Pathfinding AI
Google	PageRank

---

🧠 9. Ilustrasi Graph Dunia Nyata

6

---

⏱️ 10. Kompleksitas Graph

📊 Tabel Kompleksitas

Operasi	Kompleksitas
BFS	O(V + E)
DFS	O(V + E)
Add Edge	O(1)
Search Edge	O(V) (list)

---

⚠️ 11. Kelebihan dan Kekurangan Graph

📊 Tabel

Kelebihan	Kekurangan
Representasi hubungan kompleks	Implementasi rumit
Fleksibel	Boros memori (matrix)
Digunakan luas	Sulit dianalisis manual

---

🧪 12. Studi Kasus Nyata

📌 Sistem Navigasi (Google Maps)

• Node = lokasi
• Edge = jalan
• Bobot = jarak/waktu

➡️ Menggunakan weighted graph + shortest path

---

📌 Media Sosial

• Node = user
• Edge = follow/friend

---

💻 13. Implementasi Sederhana (C++)

#include <iostream>
#include <vector>
using namespace std;int main(){
    vector<int> adj[3];    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[2].push_back(0);    cout << "Graph adjacency list selesai dibuat";
}

---

📚 14. Ringkasan Materi

• Graph adalah struktur data berbasis node dan edge
• Jenis: directed, undirected, weighted
• Representasi: adjacency matrix & list
• Traversal: BFS & DFS
• Digunakan dalam banyak sistem dunia nyata

---

📝 15. Latihan / Diskusi

✏️ Soal Teori

1. Jelaskan pengertian graph
2. Apa perbedaan BFS dan DFS?
3. Kapan menggunakan adjacency list?

💻 Soal Praktikum

1. Buat graph sederhana
2. Implementasikan BFS
3. Implementasikan DFS

---

🎯 Penutup

Graph adalah struktur data paling penting untuk merepresentasikan hubungan kompleks, digunakan dalam:

• Internet
• GPS
• Media sosial
• AI dan Machine Learning