Khi cài một đồ thị, có hai cách lưu kinh điển: ma trận kề (một bảng V×V, ô [i][j]=1 nếu có cạnh) và danh sách kề (mỗi đỉnh giữ một danh sách các đỉnh kề). Sách thường dạy ma trận trước vì nó trực quan và code ngắn, khiến nhiều người mặc định dùng nó. Nhưng khi tôi đo với một đồ thị thưa — loại chiếm đa số trong thực tế — ma trận kề tốn RAM và duyệt chậm đến mức khủng khiếp. Tôi đo cả hai trong container gcc:13, và con số cho thấy lựa chọn "đơn giản" có thể là lựa chọn tệ nhất, tùy hình dạng đồ thị.
O(V²) so với O(V+E), và vì sao mật độ quyết định
Ma trận kề: một mảng V×V. Kiểm "có cạnh giữa i và j không" là đọc một ô — O(1), rất nhanh. Nhưng: bộ nhớ là O(V²) bất kể đồ thị có bao nhiêu cạnh — với V=10.000, đó là 100 triệu ô, dù đồ thị chỉ có vài chục nghìn cạnh. Và duyệt hàng xóm của một đỉnh phải quét cả hàng V ô, phần lớn là 0.
Danh sách kề: mỗi đỉnh giữ một danh sách các đỉnh kề. Bộ nhớ O(V+E) — chỉ lưu cạnh thật. Duyệt hàng xóm là O(bậc), duyệt toàn đồ thị là O(V+E) — chỉ chạm những cạnh có thật. Nhưng kiểm cạnh (i,j) phải duyệt danh sách hàng xóm của i — O(bậc), chậm hơn ma trận.
Điểm mấu chốt: mật độ đồ thị quyết định. Đa số đồ thị thực tế — mạng xã hội, bản đồ đường đi, đồ thị web — là thưa: mỗi đỉnh chỉ nối với vài đỉnh khác, nên E ~ vài lần V, không phải V². Với chúng, O(V²) của ma trận là lãng phí khổng lồ. Tôi đo trên đồ thị thưa V=10.000, E=50.000.
Đo: nhỏ hơn 127 lần, duyệt nhanh 302 lần
Đồ thị THƯA: V=10.000 đỉnh, E=50.000 cạnh (bậc TB ~10), g++ -O2:
A. BỘ NHỚ:
ma trận kề (V×V char) : 100 MB (V² = 100 triệu ô, dù đồ thị thưa)
danh sách kề (V+E) : ~0,8 MB (chỉ lưu cạnh thật)
-> danh sách nhỏ hơn ~127 lần
B. DUYỆT toàn đồ thị (BFS, chạm mọi cạnh):
ma trận kề : 0,0302 s (mỗi đỉnh quét cả hàng V -> tổng V² = 100 triệu ô)
danh sách kề : 0,0001 s (chỉ chạm E = 50.000 cạnh, O(V+E))
-> danh sách nhanh hơn ~302 lần
C. KIỂM CẠNH (i,j) có tồn tại (1 triệu lần):
ma trận kề : 4,2 ns/kiểm (O(1), truy cập trực tiếp một ô)
danh sách kề : 11,2 ns/kiểm (O(bậc), duyệt danh sách hàng xóm)
Nhìn A: cùng đồ thị 50 nghìn cạnh, ma trận tốn 100 MB còn danh sách chỉ 0,8 MB — nhỏ hơn 127 lần. Vì ma trận phải cấp cả bảng V² dù 99,95% ô là 0. B còn ấn tượng hơn: duyệt toàn đồ thị bằng BFS, ma trận mất 0,0302 giây (mỗi đỉnh quét cả hàng 10.000 ô để tìm hàng xóm — tổng 100 triệu ô), còn danh sách chỉ 0,0001 giây (chỉ chạm 50 nghìn cạnh có thật) — nhanh hơn 302 lần. Với đồ thị thưa, ma trận biến một thuật toán O(V+E) đẹp đẽ thành O(V²) chậm chạp.
Nhưng C cho thấy ma trận không vô dụng: kiểm "có cạnh (i,j) không" trên ma trận chỉ 4,2 ns (đọc một ô, O(1)), còn danh sách mất 11,2 ns (duyệt danh sách hàng xóm, O(bậc)) — ma trận nhanh hơn 2,7 lần. Nếu thuật toán của bạn liên tục hỏi "hai đỉnh này có nối không", ma trận thắng. Và với đồ thị dày (E ~ V²), O(V²) của ma trận không còn lãng phí — bạn cần chừng đó ô dù sao đi nữa.
Một lần tôi đo hớ: "ma trận đơn giản nên luôn dùng" và "danh sách luôn tốt hơn"
Tôi vào đo với niềm tin của người mới học: "ma trận kề trực quan, code ngắn, cứ dùng nó cho mọi đồ thị". Đo phá tan với đồ thị thưa: ma trận tốn RAM gấp 127 lần và duyệt chậm 302 lần, vì nó cấp và quét cả bảng V² trong khi chỉ có 50 nghìn cạnh. Với đa số đồ thị thực tế (đều thưa), ma trận là lựa chọn tệ. Nhưng rồi tôi suýt rơi vào đo hớ ngược: "vậy danh sách kề luôn tốt hơn, cứ dùng nó". Cũng sai — kiểm cạnh (i,j) ma trận nhanh 2,7 lần (O(1) vs O(bậc)), và với đồ thị dày hoặc thuật toán cần kiểm cạnh liên tục, ma trận hợp hơn.
Bài học đo lường: cách biểu diễn đồ thị phụ thuộc MẬT ĐỘ và thao tác chính — với đồ thị THƯA (đa số thực tế, E ~ vài lần V), danh sách kề O(V+E) thắng: RAM nhỏ hơn (0,8 MB vs 100 MB = 127x) và duyệt toàn đồ thị nhanh hơn (0,0001s vs 0,0302s = 302x, chỉ chạm cạnh thật thay vì quét V² ô); nhưng ma trận kề thắng KIỂM CẠNH (i,j) O(1) (4,2 vs 11,2 ns) và hợp cho đồ thị DÀY (E~V²). Nếu tôi tin "ma trận luôn dùng được", tôi phí hàng trăm MB và làm chậm mọi thuật toán duyệt trên đồ thị lớn; nếu tôi tin "danh sách luôn tốt", tôi chọn sai cho bài toán cần kiểm cạnh nhanh hoặc đồ thị dày.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: mặc định danh sách kề, trừ khi đồ thị dày hoặc cần kiểm cạnh O(1) liên tục. Hầu hết đồ thị thực tế thưa, và hầu hết thuật toán đồ thị (BFS, DFS, Dijkstra, tìm thành phần liên thông) là duyệt — chúng đi qua các cạnh. Danh sách kề cho O(V+E) tự nhiên; ma trận biến chúng thành O(V²). Với đồ thị hàng triệu đỉnh, ma trận thậm chí không đủ RAM (V² = 10¹² ô cho 1 triệu đỉnh). Danh sách kề là lựa chọn mặc định đúng.
Hệ quả thứ hai: nếu chọn ma trận, cân nhắc bitset để giảm RAM. Ma trận kề dùng một bit mỗi ô (thay vì một byte hay một int) qua bitset của phần 15 giảm bộ nhớ 8–32 lần, và phép giao/hợp hàng xóm thành phép bit nhanh. Đây là cách các thuật toán trên đồ thị dày (như một số thuật toán tô màu, clique) dùng ma trận hiệu quả. Nhưng nó vẫn O(V²) — chỉ hằng số nhỏ hơn.
Hệ quả thứ ba là tinh thần đo lường: "đơn giản" và "tối ưu" là hai chuyện khác nhau — hình dạng dữ liệu quyết định cấu trúc, không phải độ ngắn của code. Con số mang theo: ma trận kề (V×V) vs danh sách kề (V+E) cho đồ thị: đồ thị THƯA (V=10k, E=50k) thì danh sách kề nhỏ hơn 127x RAM (0,8 vs 100 MB) và duyệt toàn đồ thị nhanh 302x (0,0001 vs 0,0302s, O(V+E) chỉ chạm cạnh thật vs O(V²) quét cả bảng); nhưng ma trận kề kiểm cạnh (i,j) O(1) nhanh 2,7x (4,2 vs 11,2 ns) và hợp cho đồ thị DÀY. Đa số đồ thị thực tế thưa -> mặc định danh sách kề. Chọn theo mật độ đồ thị và thao tác chính, không theo cái nào code ngắn hơn.
Thử ba mươi giây
Tạo một đồ thị thưa vài nghìn đỉnh với mỗi đỉnh nối vài cạnh, và cài nó hai cách: một ma trận V×V và một danh sách kề (vector<vector<int>>). So bộ nhớ — ma trận tốn V² ô (hàng trăm MB nếu V vài chục nghìn), danh sách chỉ tốn theo số cạnh. Rồi chạy BFS trên cả hai và bấm giờ: danh sách nhanh hơn nhiều, vì ma trận phải quét cả hàng để tìm hàng xóm của mỗi đỉnh. Cuối cùng, thử kiểm "có cạnh (i,j) không" một triệu lần: ma trận nhanh hơn (đọc một ô), danh sách chậm hơn (duyệt hàng xóm). Ba mươi giây đó cho bạn thấy điều mà "ma trận kề đơn giản" giấu đi: đơn giản để viết không có nghĩa là hiệu quả để chạy — với đồ thị thưa (gần như mọi đồ thị thực tế), lựa chọn đúng là danh sách kề, và ma trận chỉ hợp khi đồ thị dày hoặc bạn cần hỏi "có cạnh không" liên tục.
