Hình dung bạn muốn lưu "ai quen ai" trong một nhóm 10.000 người. Cách thứ nhất: kẻ một bảng vuông khổng lồ 10.000 × 10.000 ô, đánh dấu X vào ô (i, j) nếu hai người quen nhau. Tra "A với B có quen không" thì nhìn thẳng vào một ô — nhanh tức thì. Nhưng bảng ấy có một trăm triệu ô, mà mỗi người chỉ quen chừng chục người, nên gần như toàn bộ ô là trống. Cách thứ hai: mỗi người giữ một cuốn danh bạ nhỏ, chỉ ghi tên những ai họ thật sự quen. Nhẹ tênh, nhưng muốn biết "A quen B không" thì phải lật cả danh bạ của A. Cách thứ nhất là ma trận kề, cách thứ hai là danh sách 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. Đây là bảng vuông khổng lồ.

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. Đây là cuốn danh bạ nhỏ.

Đ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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, đồ thị thưa V=10k/E=50k. Con số đổi theo mật độ và máy; cái cần nhìn là dáng O(V²) của ma trận đè bẹp O(V+E) khi đồ thị thưa, nhưng đảo chiều ở thao tác kiểm cạnh.)

Hai niềm tin đối nghịch, cùng sai

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ị". Con số bác thẳng 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 tôi suýt rơi vào một đo hớ ngược lại: "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. Không có "cấu trúc thắng tuyệt đối"; có "cấu trúc đúng cho mật độ và thao tác của bài toán này".

Về đến code hằng ngày

Điều đầ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.

Điều 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.

Chỗ này ai đụng tới database đồ thị hay xử lý mạng lớn sẽ thấy rất quen. Các thư viện tính toán khoa học như SciPy có hẳn một họ định dạng "sparse matrix" (CSR, CSC, COO) — bản chất là danh sách kề đóng gói cho ma trận thưa — chính vì lưu đầy đủ V² là bất khả thi ở quy mô thật. Các đồ thị khổng lồ (mạng xã hội, đồ thị web PageRank) gần như luôn lưu dạng danh sách kề nén, và định dạng CSR còn là chuẩn de-facto để chạy thuật toán đồ thị trên GPU. Ngược lại, các engine cần hỏi cạnh liên tục — ví dụ thuật toán trên ma trận kề nhỏ và dày trong bài toán tối ưu — thì ma trận bitset lại đúng chỗ. Cùng một câu hỏi bảng-vuông-hay-danh-bạ, phóng to lên hàng tỷ cạnh.

Muốn tự thấy thì 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). Vài phút đó 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.