Tìm Đường Đi Ngắn Nhất Trên Đồ Thị Có Trọng Số 0-1 Với 0-1 BFS

Xin chào anh em, lại là tôi - Jim đây!

Hôm nay, chúng ta sẽ cùng nhau khám phá một kỹ thuật cực kỳ mạnh mẽ và hiệu quả, một vũ khí bí mật giúp anh em giải quyết một lớp bài toán tìm đường đi ngắn nhất đặc biệt: 0-1 BFS.

Đây là một thuật toán không chỉ nhanh, dễ cài đặt mà còn mở ra một tư duy hoàn toàn mới về cách chúng ta biến hình một bài toán tưởng chừng không liên quan thành một bài toán đồ thị quen thuộc. Hãy cùng nhau bắt đầu hành trình này. Chúng ta sẽ không chỉ học cái gì và như thế nào, mà quan trọng hơn, chúng ta sẽ hiểu tại sao thuật toán này lại đúng và khi nào nên sử dụng nó.

1. Khi BFS Thường Không Đủ

Hẳn anh em nào khi bắt đầu với đồ thị cũng đều biết đến Breadth-First Search (BFS), tức thuật toán tìm kiếm theo chiều rộng. Với sự trợ giúp của một hàng đợi (queue) đơn giản, BFS có thể tìm ra đường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong một đồ thị không có trọng số hoặc có trọng số là một hằng số một cách hiệu quả với độ phức tạp $O(V+E)$. Nguyên lý của nó giống như việc chúng ta thả một viên sỏi xuống mặt hồ, các vòng sóng sẽ lan ra đồng đều theo từng lớp.

Nhưng cuộc sống không phải lúc nào cũng đơn giản như vậy. Hãy tưởng tượng anh em đang ở trong một mê cung. Nếu mọi bước đi đều như nhau, BFS sẽ là người bạn đồng hành tuyệt vời. Bây giờ, hãy thêm một chút phép thuật: mê cung này có những tấm thảm bay thần kỳ. Anh em có thể dùng thảm bay để di chuyển đến một căn phòng kế bên mà không tốn chút sức lực nào (chi phí là 0), trong khi việc đi bộ bình thường sẽ tốn 1 đơn vị sức lực (chi phí là 1).

Mục tiêu của bạn vẫn là tìm đường ra khỏi mê cung với tổng sức lực ít nhất. Lúc này, con đường đi qua ít phòng nhất chưa chắc đã là con đường rẻ nhất. Một con đường dài ngoằng nhưng toàn đi bằng thảm bay rõ ràng tốt hơn một lối đi tắt chỉ cần một bước nhưng phải đi bộ.

Đây chính là lúc BFS truyền thống bắt đầu bối rối. Hàng đợi FIFO (First-In-First-Out) của nó chỉ đảm bảo xử lý các đỉnh theo thứ tự được khám phá, chứ không hề quan tâm đến chi phí tích lũy. Nó sẽ luôn cho rằng đường đi 1 bước là tốt hơn đường đi 3 bước, dẫn đến kết quả sai. Chúng ta cần một công cụ mạnh hơn, một công cụ có thể hiểu được sự khác biệt giữa chi phí 0 và 1. Đây chính là sân khấu dành cho 0-1 BFS.

2. Gặp Gỡ 0-1 BFS: Làn Ưu Tiên VIP

Vậy 0-1 BFS giải quyết vấn đề này như thế nào? Bí mật nằm ở việc thay thế cấu trúc dữ liệu. Thay vì dùng một hàng đợi (queue) thông thường, chúng ta sẽ sử dụng một hàng đợi hai đầu (deque - double-ended queue).

Hãy tưởng tượng deque này như một hàng chờ đặc biệt tại một sự kiện lớn, nó có cả cửa vào thông thường và một lối đi VIP.

• Khi chúng ta đi từ đỉnh u đến đỉnh v qua một cạnh có trọng số 1 (một bước đi bộ tốn sức), đỉnh v sẽ được coi như một khách thường. Nó sẽ phải xếp hàng ở cuối như bình thường. Trong lập trình, chúng ta dùng push_back(v).
• Nhưng khi chúng ta đi từ u đến v qua một cạnh có trọng số 0 (một bước đi miễn phí trên thảm bay), đỉnh v sẽ được coi là khách VIP. Nó được ưu tiên, đi thẳng lên đầu hàng chờ. Trong lập trình, chúng ta dùng push_front(v).

Bằng cách này, deque của chúng ta luôn ưu tiên xử lý những đỉnh rẻ hơn trước. Những đỉnh có thể đến được với chi phí 0 sẽ được khám phá ngay lập tức, trước cả những đỉnh đã được đưa vào hàng chờ từ trước nhưng với chi phí cao hơn.

3. Thuật Toán Hoạt Động Như Thế Nào?

Hãy cùng xem một ví dụ cụ thể. Giả sử chúng ta có đồ thị sau và muốn tìm đường đi ngắn nhất từ đỉnh 0.

Đồ thị:

Bước 1: Khởi tạo

• Mảng khoảng cách dist được gán giá trị vô cùng, dist[0] = 0.
• Tạo deque dq và đưa đỉnh nguồn 0 vào.
• dist = [0, INF, INF, INF, INF]
• dq = [0]

Bước 2: Lấy 0 ra khỏi deque

• Xét đỉnh u = 0, dist[u] = 0.
• Kề với 0 có 1 (cạnh 0): Cập nhật dist[1] = 0. Vì trọng số là 0, đưa 1 vào đầu deque.
• Kề với 0 có 2 (cạnh 1): Cập nhật dist[2] = 1. Vì trọng số là 1, đưa 2 vào cuối deque.
• dist = [0, 0, 1, INF, INF]
• dq = [1, 2]

Bước 3: Lấy 1 ra khỏi deque

• Xét đỉnh u = 1, dist[u] = 0.
• Kề với 1 có 3 (cạnh 1): Cập nhật dist[3] = 1. Vì trọng số là 1, đưa 3 vào cuối deque.
• dist = [0, 0, 1, 1, INF]
• dq = [2, 3]

Bước 4: Lấy 2 ra khỏi deque

• Xét đỉnh u = 2, dist[u] = 1.
• Kề với 2 có 4 (cạnh 0): Cập nhật dist[4] = 1. Vì trọng số là 0, đưa 4 vào đầu deque.
• dist = [0, 0, 1, 1, 1]
• dq = [4, 3]

Bước 5: Lấy 4 ra khỏi deque

• Xét đỉnh u = 4, dist[u] = 1.
• Kề với 4 có 3 (cạnh 1): dist[4] + 1 < dist[3] (tức là 1 + 1 < 1) là sai. Không làm gì cả.
• dq = [3]

Bước 6: Lấy 3 ra khỏi deque

• Xét đỉnh u = 3, dist[u] = 1. Không có đỉnh kề mới để đi.
• dq = []

Bước 7: Deque rỗng, thuật toán kết thúc.

• Kết quả cuối cùng: dist = [0, 0, 1, 1, 1]. Đây là chi phí nhỏ nhất để đi từ đỉnh 0 đến các đỉnh khác.

4. Tại Sao 0-1 BFS Luôn Đúng?

Việc sử dụng deque và quy tắc ưu tiên có vẻ trực quan, nhưng tại sao nó lại đảm bảo tìm ra đường đi ngắn nhất một cách chính xác? Câu trả lời nằm ở một tính chất quan trọng, một bất biến mà deque luôn duy trì.

Bất biến Deque: Tại bất kỳ thời điểm nào, các giá trị khoảng cách (dist) của các đỉnh trong deque, nếu đọc từ đầu đến cuối, sẽ luôn được sắp xếp không giảm. Hơn nữa, trong deque chỉ có tối đa hai giá trị khoảng cách khác nhau: d và d+1. Cấu trúc của deque sẽ luôn có dạng: [d, d,..., d, d+1, d+1,..., d+1].

• Khởi tạo: Ban đầu, deque chỉ chứa đỉnh nguồn với khoảng cách 0. Bất biến đúng.
• Bước lặp: Giả sử bất biến đang đúng. Chúng ta lấy ra một đỉnh u từ đầu deque. Đỉnh này chắc chắn có khoảng cách nhỏ nhất trong deque, gọi là d.
  • Nếu cạnh (u, v) có trọng số 0: Khoảng cách mới đến v là d. Chúng ta đẩy v vào đầu deque. Bất biến được duy trì.
  • Nếu cạnh (u, v) có trọng số 1: Khoảng cách mới đến v là d+1. Chúng ta đẩy v vào cuối deque. Bất biến vẫn được duy trì.

Vì deque luôn giữ được tính chất này, việc chúng ta luôn lấy phần tử ở đầu ra cũng tương đương với việc luôn xử lý đỉnh có khoảng cách nhỏ nhất hiện tại, tương tự như Dijkstra.

5. Mối Liên Hệ Với Dijkstra

Nếu anh em đã quen thuộc với thuật toán Dijkstra, anh em sẽ thấy một sự tương đồng đáng kinh ngạc. Dijkstra giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số không âm tổng quát. Trái tim của Dijkstra là một hàng đợi ưu tiên (priority queue), giúp nó luôn chọn được đỉnh chưa xét có khoảng cách nhỏ nhất.

0-1 BFS chính là một phiên bản tối ưu hóa tuyệt vời của Dijkstra cho trường hợp đặc biệt khi trọng số chỉ là 0 hoặc 1. Nhờ bất biến d và d+1 mà chúng ta đã chứng minh, deque đã thay thế hoàn hảo cho priority queue.

• Thao tác trên priority_queue tốn O(logV).
• Thao tác push_front/push_back trên deque chỉ tốn O(1).

Điều này giúp giảm độ phức tạp tổng thể của thuật toán từ O(ElogV) của Dijkstra xuống còn $O(V+E)$ của 0-1 BFS.

6. Code C++ Hoàn Chỉnh

Lý thuyết là vậy, giờ hãy cùng nhau xây dựng một đoạn code C++ mẫu hoàn chỉnh. Đây sẽ là xương sống để anh em giải quyết các bài toán 0-1 BFS.

#include <bits/stdc++.h>
using namespace std; const int INF = 1e9; // Một giá trị lớn tượng trưng cho vô cùng // Hàm thực hiện 0-1 BFS
// startNode: đỉnh bắt đầu
// numNodes: tổng số đỉnh của đồ thị
// adjList: danh sách kề, adjList[u] chứa các cặp {v, w} là đỉnh kề và trọng số
vector<int> zeroOneBfs(int startNode, int numNodes, const vector<vector<pair<int, int>>>& adjList)
{ // 1. Khởi tạo vector<int> dist(numNodes + 1, INF); dist[startNode] = 0; deque<int> dq; dq.push_front(startNode); // 2. Vòng lặp chính while (!dq.empty()) { int u = dq.front(); dq.pop_front(); // 3. Duyệt các đỉnh kề for (const auto& edge : adjList[u]) { int v = edge.first; int weight = edge.second; // 4. Điều kiện "relax" if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; // 5. Logic cốt lõi của 0-1 BFS if (weight == 0) dq.push_front(v); // Cạnh 0-cost, ưu tiên lên đầu else dq.push_back(v); // Cạnh 1-cost, xếp hàng ở cuối } } } return dist;
} int main()
{ // Ví dụ sử dụng int numVertices = 6, numEdges = 7; // Số đỉnh, số cạnh vector<vector<pair<int, int>>> adjList(numVertices + 1); // Thêm các cạnh vào đồ thị adjList[0].push_back({1, 0}); adjList[0].push_back({2, 1}); adjList[1].push_back({3, 1}); adjList[2].push_back({4, 0}); adjList[4].push_back({3, 1}); // Thêm 2 cạnh ví dụ khác adjList[3].push_back({4, 1}); adjList[4].push_back({5, 0}); int startNode = 0; vector<int> shortestPaths = zeroOneBfs(startNode, numVertices, adjList); cout << "Khoang cach ngan nhat tu dinh " << startNode << " den cac dinh khac:" << endl; for (int i = 0; i < numVertices; ++i) { cout << "Den dinh " << i << ": "; if (shortestPaths[i] == INF) cout << "INF" << '\n'; else cout << shortestPaths[i] << '\n'; } return 0;
}

7. Mô Hình Hóa: Nhận Diện Bài Toán

Đây là phần quan trọng và thú vị nhất. Trong các kỳ thi, rất hiếm có bài toán nào nói thẳng: Cho đồ thị có trọng số 0 và 1, hãy tìm đường đi ngắn nhất. Thay vào đó, đề bài sẽ đưa ra những kịch bản mà anh em phải trở thành một thám tử để tìm ra đồ thị 0-1 ẩn giấu bên trong. Đây chính là nghệ thuật mô hình hóa bài toán.

7.1. Case Study 1: Đảo Chiều Cạnh

• Bài toán: Cho một đồ thị có hướng, tìm số lượng cạnh ít nhất cần phải đảo chiều để có đường đi từ đỉnh A đến đỉnh B.
• Mô hình hóa: Chi phí chúng ta muốn tối thiểu hóa là số lần đảo cạnh.
  • Với mỗi cạnh có sẵn u -> v, ta thêm một cạnh mới u -> v với trọng số 0 (đi theo chiều có sẵn là miễn phí).
  • Đồng thời, ta thêm một cạnh ngược lại v -> u với trọng số 1 (đi ngược chiều tốn một lần đảo).
• Lời giải: Bài toán trở thành tìm đường đi có tổng trọng số nhỏ nhất từ A đến B trên đồ thị mới. Chạy 0-1 BFS là xong.

7.2. Case Study 2: Mê Cung

• Bài toán: Bạn ở trong mê cung dạng lưới. Di chuyển sang ô đường đi kề cạnh chi phí là 0. Phá một bức tường để đi qua chi phí là 1. Tìm chi phí nhỏ nhất để đi từ ô bắt đầu đến ô kết thúc.
• Mô hình hóa:
  • Đỉnh: Mỗi ô (r, c) là một đỉnh.
  • Cạnh: Từ mỗi ô, có cạnh nối đến 4 ô kề.
  • Trọng số: Nếu ô kề là đường đi, trọng số là 0. Nếu là tường, trọng số là 1.
• Lời giải: Chạy 0-1 BFS từ ô bắt đầu.

7.3. Case Study 3: Bài Toán Kinh Điển SPOJ ONEZERO

• Bài toán: Cho một số nguyên N, tìm bội số dương nhỏ nhất của N mà chỉ chứa các chữ số 0 và 1.
• Phân tích: Bài toán này trông không giống đồ thị chút nào. Đỉnh ở đâu? Cạnh ở đâu?
• Mô hình hóa không gian trạng thái:
  • Chúng ta đang tìm một số M sao cho M % N == 0. Từ khóa ở đây là phép toán modulo.
  • Đỉnh: Các trạng thái là các số dư có thể có khi chia cho N, tức là các đỉnh 0, 1, 2, ..., N-1. Đích đến là đỉnh 0.
  • Cạnh: Giả sử ta đang có số dư rem. Ta có thể thêm chữ số 0 hoặc 1 vào cuối:
    • Thêm '0': Trạng thái mới là (rem * 10) % N.
    • Thêm '1': Trạng thái mới là (rem * 10 + 1) % N.
• Dùng BFS nào? Đây là điểm tinh tế. Ta muốn tìm bội số nhỏ nhất. BFS truyền thống tìm đường đi ngắn nhất về số cạnh. Trong bài này, mỗi lần thêm một chữ số (tức là đi qua một cạnh) đều tương đương nhau. Do đó, thuật toán phù hợp nhất là BFS truyền thống, không phải 0-1 BFS.
• Bài học: Bài toán này thường được xếp vào nhóm 0-1 BFS vì nó đòi hỏi kỹ năng mô hình hóa trừu tượng tương tự. Tuy nhiên, việc nhận ra nó thực chất được giải bằng BFS thường giúp chúng ta hiểu sâu hơn bản chất của từng thuật toán.

8. Luyện tập

Cách duy nhất để thực sự làm chủ một thuật toán là thông qua luyện tập. Dưới đây là một danh sách các bài tập được chọn lọc để anh em rèn luyện.

9. Tổng Kết

Qua bài viết này, hy vọng anh em đã có một cái nhìn sâu sắc và toàn diện về 0-1 BFS. Hãy nhớ những điểm chính sau:

• 0-1 BFS là sự tối ưu hóa của Dijkstra cho đồ thị có trọng số cạnh chỉ là 0 hoặc 1.
• deque là cấu trúc dữ liệu cốt lõi, cho phép xử lý các cạnh 0-cost với độ phức tạp O(1).
• Kỹ năng thực sự nằm ở nghệ thuật mô hình hóa – biến một bài toán phức tạp thành một đồ thị 0-1 đơn giản.

Việc nắm vững 0-1 BFS sẽ là một bước tiến lớn trên con đường chinh phục các thuật toán đồ thị của anh em. Đừng ngần ngại thử sức với các bài tập và khám phá thêm những ứng dụng sáng tạo của nó.

Chúc anh em học tốt và code vui, see ya~