Graph (Đồ thị) & Thuật toán tìm đường

🎯 Thế giới phẳng là một Đồ thị

Mạng xã hội (Facebook), Bản đồ (Google Maps), Internet... tất cả đều là Graph.

• Đỉnh (Vertex/Node): Đại diện cho đối tượng (Người, Thành phố).
• Cạnh (Edge): Đại diện cho mối quan hệ (Kết bạn, Đường đi). Có thể có Hướng (Directed) hoặc Vô hướng (Undirected), có Trọng số (Weighted - Độ dài đường đi).

1. Duyệt đồ thị: BFS vs DFS (Phải thuộc lòng)

Làm sao để đi hết mọi ngóc ngách của một đồ thị?

Tiêu chí	BFS (Breadth-First Search) - Chiều rộng	DFS (Depth-First Search) - Chiều sâu
Chiến thuật	"Loang dầu". Tham lam thăm hết hàng xóm xung quanh mình trước rồi mới đi xa hơn.	"Đâm lao". Chọn 1 đường đi mãi đến khi cùng đường (ngõ cụt) mới quay lại (Backtrack) đi đường khác.
Cấu trúc dữ liệu	Queue (Hàng đợi). (Vào trước ra trước).	Stack (Ngăn xếp) hoặc Đệ quy.
Ứng dụng	Tìm đường ngắn nhất (trong đồ thị không trọng số), Peer-to-peer network.	Giải mê cung, Các bài toán liệt kê, Topological Sort.

2. Dijkstra - Thuật toán tìm đường ngắn nhất

Google Maps dùng cái này (phiên bản nâng cao A*).

Tư duy "Tham lam" (Greedy):

1. Đứng tại điểm xuất phát (A). Khoảng cách A=0. Các điểm khác = Vô cực.
2. Xét các hàng xóm của A. Chọn hàng xóm nào gần nhất (ví dụ B).
3. Cập nhật khoảng cách đến B.
4. Từ B lại xét các hàng xóm... Luôn chọn điểm chưa thăm có khoảng cách ngắn nhất để đi tiếp.

3. Spanning Tree (Cây khung) & MST

Bài toán: Công ty điện lực muốn kéo cáp nối N thành phố sao cho tổng chiều dài dây cáp là ÍT NHẤT và tất cả thành phố đều có điện.

Đây là bài toán tìm Minimum Spanning Tree (Cây khung nhỏ nhất).

• Thuật toán Kruskal: Sắp xếp các cạnh từ ngắn đến dài. Cứ chọn cạnh ngắn nhất nối vào, miễn là không tạo thành vòng tròn (Cycle).
• Thuật toán Prim: Giống Dijkstra. Bắt đầu từ 1 đỉnh, cứ mọc thêm cạnh ngắn nhất nối ra ngoài.

4. Ứng dụng: Google Maps & Routing

Bản đồ thực tế là một Weighted Graph (Đồ thị có trọng số).

• Đỉnh: Ngã tư, Địa điểm.
• Cạnh: Con đường nối 2 địa điểm.
• Trọng số: Độ dài quãng đường (km) hoặc Thời gian đi (phút) hoặc Độ tắc đường.

Khi bạn chọn "Đường nhanh nhất", Google Maps dùng thuật toán (biến thể Dijkstra/A*) để tìm đường có Tổng trọng số nhỏ nhất.