Chuyển tới nội dung chính

Biểu diễn đồ thị

Bạn sẽ học được gì

Trước khi chạy thuật toán trên đồ thị, ta phải lưu nó trong code. Hai cách chính: ma trận kề và danh sách kề — đánh đổi bộ nhớ và tốc độ ngược nhau. Chọn đúng cách ảnh hưởng lớn tới hiệu năng.

1. Đồ thị ví dụ​

   (0)───(1)
    │    /
    │   /
   (2)─(3)

Cạnh: 0-1, 0-2, 1-3, 2-3 (vô hướng). Ta sẽ lưu đồ thị này theo hai cách.

2. Cách 1: Ma trận kề (adjacency matrix)​

Một lưới V × V: ô [i][j] = 1 nếu có cạnh i–j, ngược lại 0.

      0  1  2  3
   0 [0, 1, 1, 0]
   1 [1, 0, 0, 1]
   2 [1, 0, 0, 1]
   3 [0, 1, 1, 0]
  • Kiểm tra "có cạnh i–j không?": mt[i][j] → O(1) ✅
  • Bộ nhớ: luôn V² dù ít cạnh → tốn khi đồ thị thưa.
  • Duyệt hàng xóm của i: quét cả hàng → O(V).

3. Cách 2: Danh sách kề (adjacency list)​

Mỗi đỉnh giữ một danh sách các hàng xóm. Phổ biến nhất trong thực tế.

   0 → [1, 2]
   1 → [0, 3]
   2 → [0, 3]
   3 → [1, 2]
  • Bộ nhớ: O(V + E) → tiết kiệm khi đồ thị thưa (ít cạnh). ✅
  • Duyệt hàng xóm của i: đi đúng danh sách của i → nhanh, đúng số hàng xóm.
  • Kiểm tra "có cạnh i–j?": duyệt danh sách của i → O(bậc của i).

4. Chạy debug: dựng danh sách kề​

Bước qua việc thêm các cạnh vào danh sách kề (đồ thị vô hướng → thêm cả hai chiều):

🐞 Dựng danh sách kề từ các cạnhBước 1/5
1ke = {0: [], 1: [], 2: [], 3: []}
2canh = [(0,1), (0,2), (1,3), (2,3)]
3for u, v in canh:
4  ke[u].append(v)
5  ke[v].append(u)   # vo huong -> hai chieu
Biến tại bước này
ke{0:[], 1:[], 2:[], 3:[]}
👉 Mỗi đỉnh một list rỗng.

5. So sánh & chọn cách​

Tiêu chíMa trận kềDanh sách kề
Bộ nhớO(V²)O(V + E)
Kiểm tra cạnh i–jO(1)O(bậc i)
Duyệt hàng xóm của iO(V)O(bậc i)
Tốt chođồ thị dày (nhiều cạnh)đồ thị thưa (ít cạnh)

Quy tắc: đa số đồ thị thực tế thưa (mỗi đỉnh chỉ nối vài đỉnh) → danh sách kề là mặc định. Dùng ma trận kề khi đồ thị dày hoặc cần kiểm tra cạnh i–j liên tục trong O(1).

🎬 Trực quan hóa tương tác — VisuAlgo
Quan sát ma trận kề và danh sách kề cập nhật song song khi thêm/xóa cạnh. Thử chuyển giữa đồ thị có hướng và vô hướng.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

6. Code mẫu (chạy thật)​

Đang tải trình chạy code…

7. Mẫu nhận diện​

  • Đồ thị thưa (E nhỏ hơn nhiều V²) hoặc cần duyệt hàng xóm (BFS/DFS) → danh sách kề.
  • Cần kiểm tra "có cạnh i–j?" rất nhiều, hoặc đồ thị dày → ma trận kề.
  • BFS/DFS (Trụ 3) hầu hết dùng danh sách kề.

8. 🎮 Trò chơi: Chọn cách biểu diễn​

🎮 Ma trận hay danh sách kề?Câu 1/4· Điểm 0· 🔥 0

Thưa / duyệt hàng xóm → danh sách kề. Dày / kiểm tra cạnh O(1) → ma trận kề.

BFS/DFS trên đồ thị thường dùng cách nào?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Ma trận kề tốn bộ nhớ?
2. Ưu điểm chính của danh sách kề?
3. Với đồ thị thưa, nên mặc định dùng?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập
📖 Sách/tài liệu

10. Hoàn thành — XONG TRỤ 2! 🎉​

…

🎉 Bạn đã hoàn thành Trụ 2 — Cấu trúc dữ liệu: mảng, chuỗi, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm, cây và đồ thị. Tiếp theo: Trụ 3 — Thuật toán (sắp xếp, tìm kiếm, đồ thị, DP...).