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

Khái niệm đồ thị

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

Đồ thị (graph) mô hình hoá quan hệ giữa các vật: bạn bè trên mạng xã hội, đường nối các thành phố, phụ thuộc giữa các công việc. Bạn sẽ nắm thuật ngữ và các loại đồ thị — nền cho hàng loạt thuật toán mạnh ở Trụ 3 (BFS, DFS, đường đi ngắn nhất).

1. Trực quan: đỉnh và cạnh​

Đồ thị gồm đỉnh (vertex/node) và cạnh (edge) nối các đỉnh.

        (A)───────(B)
         │ \       │
         │   \     │
        (C)───(D)──(E)

Ví dụ thực tế:

  • Mạng xã hội: đỉnh = người, cạnh = quan hệ bạn bè.
  • Bản đồ: đỉnh = giao lộ, cạnh = đường.
  • Web: đỉnh = trang, cạnh = liên kết.
  • Phụ thuộc công việc: đỉnh = task, cạnh = "phải làm trước".

Cây mà bạn vừa học chính là một đồ thị đặc biệt (liên thông, không chu trình, có gốc). Đồ thị tổng quát hơn nhiều.

2. Bốn cách phân loại​

Có hướng vs vô hướng:

Vô hướng:  A —— B   (quan hệ hai chiều: bạn bè)
Có hướng:  A —→ B   (một chiều: A theo dõi B, follow)

Có trọng số vs không:

Không trọng số:  A —— B
Có trọng số:     A —5— B   (cạnh mang giá trị: khoảng cách, chi phí, thời gian)

Có chu trình vs không chu trình: chu trình = đi theo cạnh rồi quay về điểm xuất phát. Đồ thị có hướng không chu trình gọi là DAG (rất quan trọng: lịch công việc, sắp xếp tô-pô).

Liên thông vs không: mọi đỉnh có đường tới nhau không.

3. Thuật ngữ cần nhớ​

Thuật ngữNghĩa
Đỉnh (vertex)một nút
Cạnh (edge)nối hai đỉnh
Bậc (degree)số cạnh nối tới một đỉnh
Đường đi (path)dãy đỉnh nối tiếp bằng cạnh
Chu trình (cycle)đường đi quay về điểm đầu
Trọng số (weight)giá trị gắn trên cạnh
🎬 Trực quan hóa tương tác — VisuAlgo
Xây dựng đồ thị có hướng/vô hướng, có/không trọng số. Quan sát ma trận kề và danh sách kề song song.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

4. Vì sao đồ thị quan trọng?​

Cực nhiều bài thực tế quy về đồ thị: tìm đường ngắn nhất (Google Maps), gợi ý bạn bè, phát hiện chu trình (vòng lặp phụ thuộc), lập lịch, mạng lưới, luồng dữ liệu. Trụ 3 sẽ dạy các thuật toán trên đồ thị: BFS, DFS, Dijkstra, cây khung nhỏ nhất, sắp xếp tô-pô. Trước hết, bài 2.6.2 dạy cách lưu đồ thị trong code.

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

  • Bài nói về quan hệ, kết nối, mạng lưới, đường đi, phụ thuộc → mô hình hoá bằng đồ thị.
  • "Một chiều" (follow, link, phải-làm-trước) → đồ thị có hướng.
  • "Khoảng cách, chi phí, thời gian" trên kết nối → đồ thị có trọng số.
  • "Có bị lặp vòng không" (phụ thuộc vòng) → kiểm tra chu trình.

6. 🎮 Trò chơi: Hiểu đồ thị​

🎮 Hiểu đồ thịCâu 1/4· Điểm 0· 🔥 0

Đồ thị = đỉnh + cạnh. Phân loại: hướng/vô hướng, có/không trọng số, có/không chu trình.

Đường đi quay về đúng điểm xuất phát gọi là?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Đồ thị gồm hai thành phần cơ bản là?
2. Cây là?
3. DAG là gì?

8. Hoàn thành​

…

☑️ Tiếp theo: 2.6.2 — Biểu diễn đồ thị (ma trận kề vs danh sách kề).