Graph representation — Adjacency list vs matrix, trade-off bộ nhớ

TL;DR: Graph lưu trong bộ nhớ theo 3 cách chính: adjacency matrix (bảng V×V), adjacency list (mỗi đỉnh giữ danh sách hàng xóm), và edge list (danh sách tất cả cạnh). Với graph 1 triệu đỉnh, matrix cần ~1 TB RAM trong khi list chỉ cần vài trăm MB — vì hầu hết real-world graph là sparse (ít cạnh so với V²). Pitfall lớn nhất: mặc định chọn matrix "vì đơn giản" rồi gặp OutOfMemory ngay khi V vượt vài nghìn.

Module 3 dạy graph algorithms — BFS, DFS, Dijkstra, MST. Tất cả đều bắt đầu bằng cùng một câu hỏi: lưu graph thế nào trong bộ nhớ?

Nghe tưởng đơn giản, nhưng choice này ảnh hưởng mạnh đến cả RAM lẫn thời gian chạy. Một graph 1 triệu đỉnh: adjacency matrix cần 1.000.000² ô = 10¹² byte ≈ 1 TB RAM — bất khả thi dù graph có ít cạnh. Adjacency list chỉ lưu các cạnh thực tế: với sparse graph (social network, road map — mỗi đỉnh vài cạnh) chỉ dùng vài trăm MB. Lookup một cạnh: matrix O(1), list O(degree). Matrix chỉ đáng dùng khi graph dense (số cạnh gần V²) và V nhỏ.

Bài này so sánh 2 representation chính (adjacency list, adjacency matrix), variant edge list, pseudocode cho từng cái, và rule of thumb chọn đúng cho production graph.

1. Analogy — Sổ liên lạc lớp học

Hình dung một lớp 30 học sinh, mỗi học sinh có một số quan hệ bạn bè với nhau (tổng cộng 100 cặp bạn trong lớp).

Adjacency matrix = bảng 30×30, mỗi ô đánh dấu "X có quen Y không". Tốn đúng 900 ô dù chỉ có 100 quan hệ — 800 ô trống hoàn toàn lãng phí.

Adjacency list = mỗi học sinh giữ danh sách bạn riêng. Tổng kích thước tất cả các list = 2 × 100 = 200 entry (mỗi cặp đếm 2 lần vì undirected). Không tốn ô trống.

Edge list = 1 danh sách khổng lồ ghi "X-Y" cho từng cặp bạn. Tra "X có bạn nào?" phải scan toàn bộ danh sách.

2. Định nghĩa graph

Graph G = (V, E): V là tập đỉnh (vertices/nodes), E là tập cạnh (edges).

• Directed graph: cạnh (u, v) khác (v, u) — đường một chiều. Ví dụ: Twitter follow, dependency DAG.
• Undirected graph: cạnh {u, v} = {v, u} — hai chiều. Ví dụ: Facebook friendship, đường hai chiều.
• Weighted graph: mỗi cạnh có trọng số (số thực). Ví dụ: khoảng cách km, travel time, bandwidth.
• Self-loop: cạnh từ đỉnh tới chính nó — (u, u).
• Multi-edge: nhiều cạnh giữa cùng 2 đỉnh.

Real-world mapping:

3. Adjacency Matrix

Ma trận V×V, ô adj[u][v] = 1 (hoặc true) nếu có cạnh từ u đến v.

-- Khởi tạo adjacency matrix cho graph V đỉnh
GraphMatrix(V):
    adj[0..V-1][0..V-1] <- 0      -- toàn bộ ô khởi tạo bằng 0

-- Thêm cạnh (undirected)
addEdge(u, v):
    adj[u][v] <- 1
    adj[v][u] <- 1                 -- bỏ dòng này nếu directed

-- Kiểm tra cạnh
hasEdge(u, v):
    return adj[u][v]               -- O(1)

-- Lấy danh sách hàng xóm
neighbors(u):
    result <- []
    for v <- 0 đến V-1:
        if adj[u][v] = 1:
            result.append(v)
    return result                  -- phải scan toàn hàng — O(V)

Time: O(1) cho hasEdge Space: O(V²)

Ví dụ matrix 5 đỉnh (0–4), 6 cạnh: 0-1, 0-2, 1-3, 2-3, 3-4, 1-4:

     0   1   2   3   4
0  [ .   X   X   .   . ]
1  [ X   .   .   X   X ]
2  [ X   .   .   X   . ]
3  [ .   X   X   .   X ]
4  [ .   X   .   X   . ]

graph LR
    subgraph Ma trận kề — 5 đỉnh
        A0((0)) --- A1((1))
        A0 --- A2((2))
        A1 --- A3((3))
        A1 --- A4((4))
        A2 --- A3
        A3 --- A4
    end

Complexity:

Dùng khi: graph dense (E gần V²), cần edge lookup O(1) liên tục, hoặc V đủ nhỏ để matrix vừa RAM.

4. Adjacency List

Mỗi đỉnh giữ một list các hàng xóm. Chỉ lưu cạnh thực sự tồn tại.

-- Khởi tạo adjacency list cho graph V đỉnh
GraphList(V):
    adj[0..V-1] <- [] cho mọi đỉnh   -- mỗi đỉnh có list rỗng

-- Thêm cạnh (undirected)
addEdge(u, v):
    adj[u].append(v)
    adj[v].append(u)                  -- bỏ dòng này nếu directed

-- Kiểm tra cạnh
hasEdge(u, v):
    return v trong adj[u]             -- O(degree(u))

-- Lấy danh sách hàng xóm
neighbors(u):
    return adj[u]                     -- O(1) trả về, duyệt O(degree)

Time: O(degree) cho hasEdge Space: O(V + E)

Với weighted graph, mỗi entry trong list là cặp (đỉnh đích, trọng số):

-- Thêm cạnh có trọng số (undirected)
addEdge(u, v, weight):
    adj[u].append((v, weight))
    adj[v].append((u, weight))

-- Duyệt cạnh có trọng số
for each (v, w) trong adj[u]:
    -- v là đỉnh đích, w là trọng số cạnh

Time: O(V + E) Space: O(V + E)

graph TD
    subgraph Adjacency List — 5 đỉnh
        V0["Đỉnh 0: [1, 2]"]
        V1["Đỉnh 1: [0, 3, 4]"]
        V2["Đỉnh 2: [0, 3]"]
        V3["Đỉnh 3: [1, 2, 4]"]
        V4["Đỉnh 4: [1, 3]"]
    end

Complexity:

Dùng khi: graph sparse (E gần V), cần duyệt hàng xóm nhanh (BFS, DFS, Dijkstra). Đây là default choice cho hầu hết real-world graph.

5. Edge List

Chỉ một list các cạnh — không phân theo đỉnh nào. Space O(E), tra hàng xóm O(E).

-- Edge list: danh sách tất cả cạnh
edges <- []
edges.append((0, 1, 5))    -- cạnh từ 0 đến 1, trọng số 5
edges.append((0, 2, 3))
edges.append((1, 3, 2))

-- Duyệt tất cả cạnh (dùng trong Bellman-Ford, Kruskal)
for each (u, v, w) trong edges:
    -- xử lý cạnh u->v với trọng số w

Time: O(E) để duyệt toàn bộ Space: O(E)

Complexity:

Dùng khi: algorithm cần iterate qua tất cả cạnh theo thứ tự — Kruskal MST (Module 3 lesson 08), Bellman-Ford shortest path (lesson 06). Những algorithm này không cần tra hàng xóm của một đỉnh cụ thể, chỉ cần process từng cạnh một lần.

6. Bảng so sánh tổng hợp

7. Rule of thumb — chọn representation nào

Adjacency list là default choice cho hầu hết real-world graph:

• Social network: E ≈ 5×V (theo Friendster paper). Facebook 3B user, mỗi user avg 150-300 friends → sparse.
• Road map: mỗi ngã tư có 2-4 outgoing road → sparse, weighted directed.
• Dependency graph: mỗi package có vài chục dependency → sparse DAG.

Adjacency matrix khi:

• Dense graph (E gần V²): complete graph, all-pairs shortest path baseline.
• V đủ nhỏ (vài nghìn đỉnh) và cần edge lookup O(1) liên tục.
• Thuật toán Floyd-Warshall (all-pairs shortest path) — đọc dist[u][v] rất nhiều lần.

Edge list khi algorithm là edge-centric:

• Kruskal MST: sort tất cả cạnh theo trọng số, process từng cạnh một → edge list tự nhiên.
• Bellman-Ford: relaxation qua tất cả cạnh V-1 lần → iterate edge list hiệu quả.

8. Pitfall tổng hợp

Pitfall 1 — Default dùng matrix "vì đơn giản"

-- BUG: matrix cho graph lớn, sparse
adj[1_000_000][1_000_000] <- 0
-- Cấp phát 10^12 ô = 1 TB RAM
-- Crash ngay lập tức với lỗi hết bộ nhớ

Với social network 1 triệu user, matrix cần 10¹² byte (1 TB RAM). Adjacency list với 5 triệu cạnh chỉ cần khoảng 40 MB. Luôn ước lượng density (E/V²) trước khi chọn — nếu density nhỏ hơn 0.01, dùng list.

Pitfall 2 — ArrayList vs HashSet cho neighbor list

-- Mặc định: List — cho phép multi-edge, hasEdge O(degree)
adj[u] = List of neighbors

-- Thay thế: Set — không trùng, hasEdge O(1) amortized
adj[u] = Set of neighbors

Nếu graph không có multi-edge và cần hasEdge thường xuyên (ví dụ cycle detection), dùng Set cho neighbor → hasEdge O(1) amortized thay vì O(degree). Trade-off: thêm overhead hash, không giữ insertion order.

Dùng List khi: multi-edge cần thiết, iterate neighbor theo thứ tự, hoặc BFS/DFS (chỉ iterate, không cần hasEdge).

Pitfall 3 — Quên double-add cho undirected graph

-- BUG: undirected nhưng chỉ thêm một chiều
addEdge(u, v):
    adj[u].append(v)
    -- Quên: adj[v].append(u)
-- Kết quả: graph bị directed — v không thấy u
-- BFS/DFS từ v bỏ sót mọi path đi qua cạnh này từ phía v

-- ĐÚNG: undirected — thêm cả hai chiều
addEdge(u, v):
    adj[u].append(v)
    adj[v].append(u)

Bug này rất khó debug vì graph "trông" đúng khi traverse từ u, nhưng fail khi traverse từ v. Viết test với path check cả 2 chiều.

9. Special graph types — preview

Một số loại graph đặc biệt hay gặp trong Module 3:

• DAG (Directed Acyclic Graph): không có cycle. Dùng cho dependency graph, task scheduling. Topological sort (lesson 04) chỉ work trên DAG.
• Tree: acyclic connected undirected graph với đúng V - 1 cạnh. Spanning tree của graph là subgraph dạng tree gồm tất cả đỉnh.
• Bipartite graph: chia đỉnh thành 2 partition, cạnh chỉ nối giữa 2 partition, không bao giờ trong cùng partition. Dùng cho matching problem (job-candidate assignment).
• Planar graph: có thể vẽ trên mặt phẳng 2D không có 2 cạnh cắt nhau. Road map, circuit board routing.

10. Ứng dụng thực tế

Social network (Facebook/X): adjacency list. Graph 3B user nhưng sparse — avg 150-300 kết nối mỗi user. Với directed graph (Twitter follow), mỗi user giữ 2 list riêng: following và followers.

Google Maps road network: weighted directed adjacency list. Mỗi ngã tư là đỉnh, mỗi đoạn đường là directed edge với trọng số = travel time. Avg 2-4 outgoing edge mỗi ngã tư → rất sparse. Dijkstra (lesson 05) chạy trực tiếp trên adjacency list này.

Maven/Gradle build dependency: DAG dùng adjacency list. Mỗi artifact là đỉnh, mỗi dependency là directed edge. Topological sort trên DAG cho build order — artifact phải build sau tất cả dependency của nó. Gradle detect cycle dependency và throw error vì DAG không được phép có cycle.

Neo4j / TigerGraph (graph databases): native graph storage là pointer-based adjacency list. Mỗi node lưu pointer trực tiếp đến hàng xóm, traverse O(1) per hop thay vì lookup B-tree như relational DB. Đây là lý do graph DB nhanh hơn SQL JOIN nhiều bậc khi query deep relationship (friend of friend of friend).

11. Deep Dive

12. Tóm tắt

• Graph G = (V, E): V đỉnh, E cạnh. Directed/undirected/weighted là 3 thuộc tính cơ bản.
• Adjacency matrix: O(V²) space, edge lookup O(1), iterate neighbors O(V). Dùng cho dense graph hoặc khi cần lookup cực nhanh.
• Adjacency list: O(V + E) space, edge lookup O(degree), iterate neighbors O(degree). Default choice cho sparse graph — hầu hết real-world graph là sparse.
• Edge list: O(E) space, iterate all edges O(E). Dùng cho edge-centric algorithm: Kruskal, Bellman-Ford.
• Sparse vs dense: nếu E ≪ V², chọn adjacency list. Nếu E gần V², matrix có thể hợp lý — nhưng ước lượng RAM trước.
• Undirected graph: luôn add cả 2 chiều trong adjacency list/matrix. Quên một chiều → biến thành directed.
• DAG, tree, bipartite, planar: các loại graph đặc biệt với thuật toán riêng — gặp lại trong các lesson 02-11 của Module 3.

13. Tự kiểm tra

Bài tiếp theo: BFS — unweighted shortest path