Bạn có gặp khó khăn khi giải quyết các bài toán về đồ thị trong hành trình học Cấu trúc dữ liệu và thuật toán (DSA)? Những bài toán liên quan đến đồ thị luôn là một chủ đề được nhiều sinh viên IT thở dài vì tính phức tạp của chúng.Trong bài viết này, mình xin giới thiệu đến bạn Cẩm nang tổng hợp các dạng bài toán đồ thị phổ biến, giúp bạn trang bị đầy đủ công cụ và tư duy để chinh phục bất kỳ bài toán nào liên quan đến đồ thị giúp giải quyết các bài toán đồ thị một cách hiệu quả và dễ dàng hơn.
Lưu ý quan trọng
Các đoạn code trong bài viết này được viết bằng Java, nhưng bạn hoàn toàn có thể chuyển đổi sang bất kỳ ngôn ngữ lập trình nào như Python, C++, JavaScript, v.v. Bản chất thuật toán và tư duy vẫn giữ nguyên, chỉ thay đổi cách triển khai tùy theo ngôn ngữ bạn sử dụng. Hãy thoải mái điều chỉnh cho phù hợp với nhu cầu của mình!
BIỂU DIỄN ĐỒ THỊ
Trước khi đi sâu vào các dạng bài toán, chúng ta cần hiểu hai cách phổ biến nhất để biểu diễn một đồ thị:
1. Ma trận kề (Adjacency Matrix)
Đây là một mảng hai chiều (2D array), trong đómatrix[i][j]thể hiện trọng số của cạnh nối giữa đỉnhi và j. Đối với đồ thị không trọng số, bạn có thể sử dụng một ma trận boolean, trong đómatrix[i][j] = truenếu có cạnh nối giữa hai đỉnh vàmatrix[i][j] = falsenếu không có.Ví dụ về ma trận kề cho đồ thị vô hướng không trọng số:
Ưu điểm:
- Dễ dàng kiểm tra xem hai đỉnh có kết nối với nhau không (O(1)).
- Phù hợp với đồ thị có mật độ cạnh cao (dense graph).
Nhược điểm:
- Tốn bộ nhớ O(V²), đặc biệt khi đồ thị có nhiều đỉnh nhưng ít cạnh.
2. Danh sách kề (Adjacency List)
Đây là một danh sách hoặc mảng, trong đó mỗi đỉnh được liên kết với một danh sách chứa các đỉnh lân cận của nó. Một cách triển khai phổ biến là sử dụng HashMap, trong đó keys là các đỉnh và values là ArrayLists chứa các đỉnh kề.Ví dụ về danh sách kề cho cùng một đồ thị trên:0 -> [1, 2]
1 -> [0, 2, 3]
2 -> [0, 1, 3]
3 -> [1, 2]Ưu điểm:
- Tiết kiệm bộ nhớ, phù hợp với đồ thị thưa (sparse graph).
- Duyệt qua tất cả các đỉnh kề một cách hiệu quả.
Nhược điểm:
- Kiểm tra sự tồn tại của một cạnh có thể chậm hơn so với Adjacency Matrix (O(V) trong trường hợp xấu nhất).
Lựa chọn cách biểu diễn đồ thị nào?
Việc lựa chọn giữa Adjacency Matrix và Adjacency List phụ thuộc vào bài toán cụ thể. Nếu đồ thị có nhiều cạnh, Adjacency Matrix có thể là lựa chọn tốt hơn do tốc độ truy vấn nhanh. Ngược lại, nếu đồ thị có ít cạnh, Adjacency List sẽ giúp tiết kiệm bộ nhớ hơn.Bây giờ, khi đã hiểu rõ cách biểu diễn đồ thị, chúng ta sẽ đi vào các dạng bài toán đồ thị phổ biến và cách giải quyết chúng một cách hiệu quả!
