[Hướng dẫn] Tìm đường đi trong đồ thị: Phần 2 - Thuật toán BFS

doreamonhihi

Ở bài trước, mình đã giới thiệu một trong các thuật toán cơ bản dùng để tìm đường đi trong đồ thị, DFS.
Tuy nhiên, nếu muốn tìm đường đi ngắn nhất từ 1 điểm này đến 1 điểm khác, ví dụ như tìm đường đi ngắn nhất từ 1 ô này đến 1 ô khác trong 1 mê cung, thì theo bạn sẽ dùng cách nào?  Tất nhiên, ta vẫn có thể sử dụng DFS kết hợp với cả thuật toán tìm kiếm nhị phân (binary search). Tuy nhiên, việc đó sẽ làm tăng thời gian chạy của chương trình một cách không cần thiết. Đối với đồ thị không trọng số (hoặc là độ dài tất cả các cạnh đều bằng nhau), ta có thể áp dụng một cách hiệu quả hơn, đó là thuật toán tìm kiếm theo chiều rộng (Breadth-First Search).

Kiến thức cần chuẩn bị:
- Nắm vững kiến thức cơ bản về C/ C++, STL trong C++.
- Kiến thức cơ bản về đồ thị và cách biểu diễn đồ thị trong C/ C++.

- Khái niệm về hàng đợi (queue).
I - Tư tưởng thuật toán:

Cơ sở của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần S hơn sẽđược duyệt trước). Ví dụ: Bắt đầu ta thăm đỉnh S. Việc thăm đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh (x1,x2, ..., xp) kề với S (những đỉnh gần S nhất). Khi thăm đỉnh x1 sẽ lại phát sinh yêu cầu duyệt nhữngđỉnh (u1, u2 ..., uq) kề với x1. Nhưng rõ ràng các đỉnh u này "xa" S hơn những đỉnh x nên chúng chỉđược duyệt khi tất cả những đỉnh x đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã thăm x1 sẽ là:(x2, x3..., xp, u1, u2, ..., uq). Giả sử ta có một danh sách chứa những đỉnh đang "chờ" thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách và cho những đỉnh chưa "xếp hàng" kề với nó xếp hàng thêm vào cuối danh sách. Chính vì nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới dạng hàng đợi(Queue)

Theo Lý thuyết đồ thị - Lê Minh Hoàng

II - Cài đặt:

Chú ý:
- Cần khởi tạo mảng visited ban đầu là false hết (chưa thăm bất kì đỉnh nào).
- Mảng pre khởi tạo ban đầu là 0 hết, sẽ dùng cho việc sau này in ra đường đi từ 1 đỉnh đến đỉnh còn lại.
- Mặc định bên dưới mình không truyền vector hay mảng nào vào hàm vì mình mặc định chúng sẽ là biến toàn cục.

- Kết quả khi in ra đường đi của thuật toán khi dùng ma trận kề và danh sách kề sẽ khác nhau (dù kết quả kiểm tra có tồn tại đường đi từ đỉnh này đến đỉnh khác không đổi, nhưng đường đi in ra có thể sẽ khác nhau do thứ tự duyệt đỉnh khác nhau). Tuy nhiên, độ dài đường đi phải luôn đảm bảo là đường đi ngắn nhất trong đồ thị (đi qua ít đỉnh nhất, vì đồ thị ta đang xét là đồ thị không trọng số hoặc các cạnh trong đồ thị có đồ dài tương đương nhau nên mới có thể áp dụng BFS để tìm đường đi ngắn nhất). Còn đối với đồ thị có trọng số thì sẽ áp dụng các thuật toán khác.

1. Đối với ma trận kề:

void BFS(int s, int m)
{
    queue<int> Q;
    Q.push(s);
    visited[s]=true;
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for (int v=0; v<m; v++)
        {
            if (!visited[v] && G[u][v])
            {
                Q.push(v);
                visited[v]=true;
                pre[v]=u;
            }
        }
    }
}

2. Đối với danh sách kề:

void BFS(int s)
{
    queue<int> Q;
    Q.push(s);
    visited[s]=true;
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for (int v: G[u])
        {
            if (!visited[v] && G[u][v])
            {
                Q.push(v);
                visited[v]=true;
                pre[v]=u;
            }
        }
    }
}

Giải thích:
- Mảng visited: đánh dấu những đỉnh đã được thăm kể từ đỉnh khởi đầu.
- Mảng pre: lưu lại đỉnh liền trước đó là đỉnh thăm đỉnh hiện tại, vì vậy nếu muốn truy tìm đường đi đến 1 đỉnh nào đó sau khi kiểm tra đỉnh v đấy có thể thăm được từ đinh xuất phát (kiểm tra giá trị visited[v]) thì cần phải truy ngược từ cuối về đầu, trong trường hợp muốn in theo thứ tự xuôi từ đầu đến cuối có thể lưu tạm lại vào 1 mảng nào đó rồi đảo ngược mảng (vector cũng được, khuyến khích dùng vector hơn nếu dùng C++)

- Như cách hoạt động của cả 2 code trên thì từ 1 đỉnh nó sẽ đánh dấu tất cả những đỉnh mà nó có thể thăm được trên đồ thị.

- queue là cấu trúc hàng đợi. hoạt động theo cơ chế First In First Out (FIFO), nghĩa là vào trước ra trước. Cụ thể trong bài này, hàng đợi sẽ dùng để chứa danh sách những đỉnh sẽ được "thăm". Sau khi thăm xong, các đỉnh đó sẽ được đánh dấu lại rồi được loại bỏ ra khỏi hàng đợi.

3. Ứng dụng:
- Kiểm tra xem có thể di chuyển từ điểm này đến điểm khác không.

- Tìm ra đường đi ngắn nhất từ điểm này đến 1 điểm khác (ví dụ như trong một mê cung có các ô được nối với nhau, một số ô không đi qua được (do có vật cản) thì có thể sử dụng thuật toán BFS để tìm ra đường đi ngắn nhất từ 1 ô này đến 1 ô khác.
BFS tuy giúp ta có thể tìm được đường đi ngắn nhất trong trong đồ thị không trọng số so với DFS với cùng độ phức tạp về mặt thời gian, tuy nhiên lại có nhược điểm là tốn bộ nhớ hơn trong trường hợp xấu nhất. Vì vậy, nếu chỉ kiểm tra xem có tồn tại đường đi giữa 1 điểm đến 1 hoặc nhiều điểm khác không thì không cần thiết phải sử dụng BFS (và thực tế thì BFS cũng chỉ áp dụng được trong đồ thị không trọng số). Trong trường hợp có trọng số ta sẽ phải áp dụng các thuật toán khác mình sẽ giới thiệu trong các bài viết sau

Dang_Khoa

Cái này vì không có trọng số nên giống chọn tuyến xe bus mà phải đi ít chuyến nhất có thể