Belajar Data Structure - Representasi Graph

#Pendahuluan

Setelah di episode 14 kita menutup Fase 3: Trees dengan Trie, pada episode ini kita memasuki Fase 4: Graphs dengan membahas representasi graph. Graph adalah struktur data paling general — trees, linked lists, dan bahkan hash tables pada dasarnya bisa dianggap sebagai special cases dari graph. Memahami bagaimana graph direpresentasikan adalah langkah pertama sebelum kita masuk ke algoritma traversal (BFS/DFS), shortest path, dan minimum spanning tree.

Graph muncul di mana-mana dalam software engineering: jaringan komputer, social network, peta navigasi, dependency management, dan masih banyak lagi. Representasi yang tepat menentukan efisiensi algoritma yang kalian gunakan.

#Variasi Graph

#Directed vs Undirected

Directed graph (digraph): edge memiliki arah — dari A ke B tidak sama dengan dari B ke A. Contoh: follower di social media, dependency di build system.

Undirected graph: edge tidak memiliki arah — hubungan A ke B sama dengan B ke A. Contoh: pertemanan di Facebook, jarak antar kota.

#Weighted vs Unweighted

Weighted graph: setiap edge memiliki bobot (weight) — bisa berupa jarak, biaya, waktu, atau metrik lainnya. Contoh: peta jalan dengan jarak antar kota.

Unweighted graph: semua edge dianggap sama. Contoh: pertemanan (ada atau tidak ada hubungan).

#Representasi Utama

#Adjacency List

Setiap node menyimpan list dari tetangganya. Cocok untuk sparse graph (edge jauh lebih sedikit dari V^2).

Adjacency list dengan dictionary

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

#Adjacency Matrix

Matriks V×V di mana matrix[i][j] = 1 (atau weight) jika ada edge dari i ke j. Cocok untuk dense graph.

Adjacency matrix

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

#Perbandingan

#Buat Graph dengan Kedua Representasi

6 node graph dengan kedua representasi

# Adjacency list
adj_list = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2, 5],
    4: [2, 5],
    5: [3, 4]
}
 
# Adjacency matrix
size = 6
adj_matrix = [[0] * size for _ in range(size)]
for node, neighbors in adj_list.items():
    for neighbor in neighbors:
        adj_matrix[node][neighbor] = 1
        adj_matrix[neighbor][node] = 1
 
# Hitung memory usage
list_memory = sum(len(v) for v in adj_list.values())
matrix_memory = sum(sum(row) for row in adj_matrix)
print(f"List edges: {list_memory}, Matrix edges: {matrix_memory}")

#Weighted Graph

#Adjacency List dengan Weight

Weighted adjacency list

weighted = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 3)],
    'C': [('A', 2), ('D', 5)],
    'D': [('B', 3), ('C', 5)]
}

#Adjacency Matrix dengan Weight

Weighted adjacency matrix

inf = float('inf')
w_matrix = [
    [0, 4, 2, inf],
    [4, 0, inf, 3],
    [2, inf, 0, 5],
    [inf, 3, 5, 0]
]

#Penutup

Inti yang harus dibawa pulang:

• Graph: directed/undirected, weighted/unweighted.
• Adjacency list: O(V + E) memory, cocok untuk sparse graph.
• Adjacency matrix: O(V^2) memory, O(1) edge lookup, cocok untuk dense graph.
• Weighted graph: tambahkan weight pada edge (list of tuples atau matrix value).
• Di production, adjacency list lebih umum digunakan.

Di episode 16 selanjutnya kita akan membahas BFS dan DFS — dua metode traversal fundamental untuk graph. BFS menggunakan queue untuk eksplorasi level-by-level (shortest path unweighted), DFS menggunakan stack/recursion untuk eksplorasi depth-first (cycle detection, pathfinding). Pastikan kalian sudah paham adjacency list karena BFS dan DFS akan menggunakannya!