giúp mô hình hóa các đối tượng cùng quan hệ giữa chúng, chẳng hạn mạng xã hội Facebook (người dùng là đỉnh, quan hệ bạn bè là cạnh), bản đồ Google Maps (ngã tư là đỉnh, đường phố là cạnh có trọng số độ dài), hay mạng Internet.

---

Minh họa tương tác

Thuật toánBFS · hàng đợi FIFODFS · ngăn xếp LIFO

Viền nét đứt: đang chờViền liền: đã thămTô đậm: nút hiện tại

Bước 0 / 6 Tốc độ 0.5×1×2×

Bước 0: Bắt đầu tại A.

Đã thăm: Chưa có

Hàng đợi (lấy bên trái): A

Xem code minh họa

const frontier = ['A'];
while (frontier.length) {
  const node = mode === 'bfs' ? frontier.shift() : frontier.pop();
  visit(node);
  // DFS: thêm láng giềng theo thứ tự đảo để thăm nhánh trái trước.
  frontier.push(...neighbors(node, mode));
}

Thay đổi đầu vào hoặc chạy từng bước để kiểm tra điều vừa đọc.

1. Biểu diễn Đồ thị: Ma trận kề vs Danh sách kề

Cho có $V$ đỉnh và $E$ cạnh:

Phương pháp	Bộ nhớ	Kiểm tra 2 đỉnh $(u,v)$ có kề nhau?	Duyệt mọi đỉnh kề của $u$	Thích hợp khi
Ma trận kề (Adjacency Matrix)	$\mathcal{O}(V^2)$	$\mathcal{O}(1)$ (truy cập matrix[u][v])	$\mathcal{O}(V)$	dày (nhiều cạnh, $E\approx V^2$)
Danh sách kề (Adjacency List)	$\mathcal{O}(V+E)$	$\mathcal{O}(\text{deg}(u))$	$\mathcal{O}(\text{deg}(u))$	thưa (ít cạnh, $E\ll V^2$)

---

2. So sánh Trực quan: BFS vs DFS

Ẩn dụ Dễ nhớ:

• BFS (Breadth-First Search): Giống như hòn đá ném xuống mặt hồ phẳng lặng, sóng lan tròn đều theo từng vòng ra xa dần. Đỉnh nào gần điểm xuất phát sẽ được ghé thăm trước.
• DFS (Depth-First Search): Giống như bạn đi khám phá một mê cung. Cứ gặp ngã rẽ là bạn đi sâu mãi vào một nhánh cho đến khi đâm vào ngõ cụt thì mới quay lui lại ngã ba trước đó để thử nhánh khác.

---

3. Thuật toán Dijkstra: Tìm Đường đi Ngắn nhất

Dijkstra tìm đường đi ngắn nhất từ một đỉnh nguồn $S$ đến tất cả các đỉnh còn lại trên có trọng số không âm ($w\ge 0$).

Nguyên lý Tham lam (Greedy Strategy):

1. Khởi tạo mảng khoảng cách dist[i] = +\infty, riêng dist[S] = 0.
2. Dùng ưu tiên (Min-Priority Queue / std::priority_queue trong C++) để luôn chọn ra đỉnh $u$ chưa xét có khoảng cách nhỏ nhất.
3. Thử "thư giãn" (Relaxation) tất cả các cạnh kề $(u,v)$ với trọng số $w$: Nếu điều kiện sau thỏa mãn:
   $$dist[u]+w<dist[v]⟹dist[v]=dist[u]+w$$
4. Lặp lại cho đến khi xét hết mọi đỉnh.

Cảnh báo Đi thi

Thuật toán Dijkstra KHÔNG chạy đúng trên có cạnh mang trọng số âm! Khi gặp trọng số âm, bạn phải dùng thuật toán Bellman-Ford.

---

Hệ thống bài tập tự luyện

Toàn bộ hệ thống bài tập thực hành chuyên sâu của bài học này đã được tích hợp đầy đủ tại tab Bài tập ở đầu trang. Sau khi đọc xong phần lý thuyết, bạn hãy bấm chuyển sang tab Bài tập để bắt đầu luyện tập.

Chuyển sang Tab Bài tập

Bấm vào tab Bài tập trên thanh điều hướng bài giảng ở đầu trang để mở các bài tập thực chiến có hướng dẫn chi tiết và kiểm chứng tự động.

Nguồn Tham khảo & Trực quan Đồ thị

• VisuAlgo - Graph Traversal & Dijkstra - Chạy mô phỏng từng bước thuật toán Dijkstra trực tiếp.
• CP-Algorithms - Graph Theory - Tài liệu trình bày thuật toán kèm giải thích và code C++ để đối chiếu.