Belajar Math - Graph Theory: Terminologi & Representasi
Node, edge, directed/undirected, weighted, degree, dan tiga representasi — adjacency matrix, adjacency list, edge list — adalah fondasi graph theory yang muncul dalam social network, road map, dependency graph, dan state machine.
#Pendahuluan
Setelah di episode 13 kita mempelajari probability dan Bayes' theorem — fondasi A/B testing dan classifier — pada episode ini kita mempelajari graph theory: cabang matematika yang memodelkan hubungan antara objek. Graf adalah struktur data paling umum dalam computer science — social network, road map, dependency graph, dan state machine semuanya bisa dimodelkan sebagai graf.
Mengapa graph theory penting? Karena banyak masalah yang tampak berbeda pada dasarnya adalah masalah graf yang sama: "siapa teman dari teman saya?" (social network), "rute terpendek dari A ke B?" (pathfinding), "apa urutan install package yang benar?" (dependency resolution). Memahami graph theory memberikan kerangka kerja universal untuk menyelesaikan masalah-masalah ini.
#Terminologi Dasar
#Node (Vertex) dan Edge
- Node/Vertex: objek atau entitas (titik dalam graf)
- Edge: hubungan antara dua node (garis)
# Simple graph representation
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
# Node
nodes = list(graph.keys())
print(f"Nodes: {nodes}")
print(f"Jumlah node: {len(nodes)}")
# Edge
edges = []
for node, neighbors in graph.items():
for neighbor in neighbors:
edges.append((node, neighbor))
print(f"Edges: {edges}")
print(f"Jumlah edge: {len(edges)}")#Directed vs Undirected
- Undirected: edge tidak berarah — A berhubungan dengan B = B berhubungan dengan A
- Directed (digraph): edge berarah — A → B ≠ B → A
# Undirected graph — social network
social = {
"Alice": ["Bob", "Charlie"],
"Bob": ["Alice", "Diana"],
"Charlie": ["Alice"],
"Diana": ["Bob"],
}
# Directed graph — Twitter followers
followers = {
"Alice": ["Bob", "Charlie"], # Alice follow Bob dan Charlie
"Bob": ["Alice"], # Bob follow Alice
"Charlie": ["Alice", "Diana"], # Charlie follow Alice dan Diana
"Diana": [], # Diana tidak follow siapapun
}#Weighted Graph
Edge memiliki nilai/bobot — bisa berupa jarak, biaya, atau waktu:
road_map = {
"Jakarta": {"Bandung": 150, "Semarang": 450},
"Bandung": {"Jakarta": 150, "Surabaya": 700},
"Semarang": {"Jakarta": 450, "Surabaya": 350},
"Surabaya": {"Bandung": 700, "Semarang": 350},
}
print("Road map:")
for city, destinations in road_map.items():
for dest, distance in destinations.items():
print(f" {city} → {dest}: {distance} km")#Degree
Degree adalah jumlah edge yang terhubung ke node. Dalam directed graph: in-degree (edge masuk) dan out-degree (edge keluar):
# Undirected: degree = jumlah neighbors
graph_undirected = {
"A": ["B", "C", "D"],
"B": ["A", "C"],
"C": ["A", "B"],
"D": ["A"],
}
print("Degree (undirected):")
for node, neighbors in graph_undirected.items():
print(f" deg({node}) = {len(neighbors)}")
# Directed: in-degree dan out-degree
directed = {
"A": ["B", "C"],
"B": ["C"],
"C": ["A"],
}
in_degree = {node: 0 for node in directed}
for node, neighbors in directed.items():
for neighbor in neighbors:
in_degree[neighbor] += 1
print("\nDegree (directed):")
for node in directed:
out_deg = len(directed[node])
in_deg = in_degree[node]
print(f" {node}: in={in_deg}, out={out_deg}")#Tiga Representasi Graf
#Adjacency Matrix
Matriks N×N di mana matrix[i][j] = 1 jika ada edge dari i ke j:
nodes = ["A", "B", "C", "D"]
node_index = {n: i for i, n in enumerate(nodes)}
# Matrix 4×4
matrix = [[0] * len(nodes) for _ in range(len(nodes))]
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D")]
for src, dst in edges:
matrix[node_index[src]][node_index[dst]] = 1
matrix[node_index[dst]][node_index[src]] = 1 # undirected
print("Adjacency Matrix:")
print(f" {'':4}", end="")
for n in nodes:
print(f"{n:>4}", end="")
print()
for i, n in enumerate(nodes):
print(f" {n:>4}", end="")
for j in range(len(nodes)):
print(f"{matrix[i][j]:>4}", end="")
print()#Adjacency List
Dictionary/set per node yang berisi neighbors — lebih hemat memori untuk graf jarang:
adj_list = {
"A": {"B", "C"},
"B": {"A", "C", "D"},
"C": {"A", "B", "D"},
"D": {"B", "C"},
}
print("Adjacency List:")
for node, neighbors in adj_list.items():
print(f" {node}: {sorted(neighbors)}")#Edge List
Daftar pasangan (src, dst) — sederhana untuk storage dan processing:
edge_list = [
("A", "B"), ("A", "C"),
("B", "C"), ("B", "D"),
("C", "D"),
]
print("Edge List:")
for src, dst in edge_list:
print(f" {src} → {dst}")#Perbandingan Representasi
| Representasi | Space | Cek Edge | Iterasi Neighbors | Best For |
|---|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(V) | Graf padat, all-pairs shortest path |
| Adjacency List | O(V+E) | O(degree) | O(degree) | Graf jarang, DFS/BFS |
| Edge List | O(E) | O(E) | O(E) | Sorting edge, Kruskal's MST |
import time
def bfs_matrix(matrix, start, n):
"""BFS menggunakan adjacency matrix — O(V²)."""
visited = [False] * n
queue = [start]
visited[start] = True
while queue:
node = queue.pop(0)
for neighbor in range(n):
if matrix[node][neighbor] and not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return sum(visited)
def bfs_list(adj, start):
"""BFS menggunakan adjacency list — O(V+E)."""
visited = set()
queue = [start]
visited.add(start)
while queue:
node = queue.pop(0)
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return len(visited)
# Bandingkan waktu
n = 5000
# Sparse graph — adjacency list lebih cepat
sparse_adj = {i: set() for i in range(n)}
for i in range(n - 1):
sparse_adj[i].add(i + 1)
sparse_adj[i + 1].add(i)
# Sparse as matrix
sparse_matrix = [[0]*n for _ in range(n)]
for i in range(n-1):
sparse_matrix[i][i+1] = 1
sparse_matrix[i+1][i] = 1
start = time.perf_counter()
bfs_matrix(sparse_matrix, 0, n)
t_matrix = time.perf_counter() - start
start = time.perf_counter()
bfs_list(sparse_adj, 0)
t_list = time.perf_counter() - start
print(f"BFS sparse graph ({n} nodes):")
print(f" Matrix: {t_matrix:.4f}s")
print(f" List: {t_list:.6f}s")
print(f" List {t_matrix/t_list:.0f}x lebih cepat!")#Aplikasi
#Dependency Graph (Package Manager)
from collections import defaultdict, deque
def topological_sort(graph):
"""Topological sort — urutan install package."""
in_degree = defaultdict(int)
for node in graph:
if node not in in_degree:
in_degree[node] = 0
for neighbor in graph[node]:
in_degree[neighbor] += 1
queue = deque([n for n in in_degree if in_degree[n] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order
# Package dependencies
deps = {
"app": {"database", "cache"},
"database": {"config"},
"cache": {"config"},
"config": set(),
}
order = topological_sort(deps)
print(f"Install order: {order}")Note
Adjacency list adalah representasi default untuk graf dalam praktik — kebanyakan graf real-world (social network, web graph) sangat jarang (sparse), sehingga adjacency list jauh lebih hemat memori daripada matrix. Gunakan matrix hanya jika graf padat atau kalian perlu cek edge O(1).
#Penutup
Inti yang harus dibawa pulang:
- Graph terdiri dari node (vertex) dan edge (hubungan); bisa directed/undirected dan weighted.
- Degree: jumlah edge per node; dalam directed: in-degree dan out-degree.
- Adjacency matrix: O(V²) space, O(1) edge check — untuk graf padat.
- Adjacency list: O(V+E) space, O(degree) neighbor iteration — untuk graf jarang.
- Edge list: O(E) space — untuk sorting edge dan MST algorithms.
- Graf muncul di social network, road map, dependency resolution, dan state machine.
Di episode 15 selanjutnya kita akan mempelajari trees, DAG, dan recursive structures — special case dari graph yang sangat penting: binary tree, BST, topological sort, dan Huffman coding tree. Graf yang baru kalian pelajari adalah generalisasi dari tree!