Ứng dụng DFS và BFS

Giới thiệu

Ngoài việc xác định các thành phần liên thông và liên thông mạnh trên đồ thị, các thuật toán duyệt trên đồ thị còn nhiều ứng dụng quan trọng khác. Dù mỗi ứng dụng đó cần dùng một thuật toán với nhiều kỹ thuật đặc biệt khác để xử lý riêng nhưng nền tản cơ bản vẫn dựa trên một trong hai kỹ thuật duyệt trên đồ thị. Trong chủ đề này chúng ta sẽ thảo luận qua một số ứng dụng như:

• Sắp xếp topo

• Định chiều đồ thị

• Kiểm tra vòng

• Xác định khớp, cầu

• Kiểm tra đồ thị hai phía

Tài liệu tham khảo

• Competitive programming 4, Steven Hamlim

• Sách giáo khoa chuyên Tin quyển 1, Hồ sỹ Đàm

• GeeksforGeeks

• CP-Algorithm

• VNOI

Sắp xếp topo (Topological Sort)

Trong một đồ thị có hướng và không có chu trình (Directed Acyclic Graph - DAG), có một thứ tự tuyến tính để sắp xếp các đỉnh theo thứ tự duyết đến u trước v. Ta gọi đó là sắp xếp topo.

Sắp xếp topo có nhiều ứng dụng trong thực tế, ví dụ như thứ tự học các môn của sinh viên đại học. Vì hệ thống tín chỉ có quy định các môn tiên quyết (môn nào phải học trước môn nào), các môn lựa chọn học, ...nên khi sắp xếp lộ trình học tập của sinh viên trong bốn năm ta được một thứ tự topo.

Ví dụ, với đồ thị sau đây:

Có nhiều thuật toán để tìm thứ tự topo của đồ thị có hướng. Cách đơn giản nhất là dùng DFS có chỉnh sửa một chút. Các bạn quan sát đoạn  code sau:

Thủ tục toposort(u) thực hiện việc đẩy u vào vector ts chứa các đỉnh duyệt đến được thực hiện sau khi các con trong nhánh DFS của nó đã được thăm hết. Việc đẩy bằng pushback khiến thứ tự topo bị ngược, khi xuất ra kết quả ta cần đảo ngược lại. Thuật toán này được đề xuất bởi Tarjan.

Độ phức tạp: O(V+E)

Kahn's Algorithm

Một thuật toán khác được đề xuất bởi Kahn. Khác với cách dùng DFS như trên, ông dùng một biến thể của BFS được hỗ trợ bởi một hàng đợi ưu tiên.

Nhiệm vụ 1: LIệt kê thứ tự Topo của đồ thị sau theo hai thuật toán trên

Nhiệm vụ 2. UVa 11060 - Beverages

Nhiệm vụ 3. SPOJ - TopoSorting

Kiểm tra đồ thị hai phía (Bipartite Graph check)

Nhắc lại khái niệm về đồ thị hai phía là một đồ thị mà với tập đỉnh V của nó ta có thể chia thành hai tập V1, V2 sao chi chỉ tồn tại các cạnh nối từ một đỉnh thuộc V1 sang một đỉnh thuộc V2.

Đồ thị hai phía có rất nhiều ứng dụng thực tế, chúng ta sẽ bàn kỹ trong phần sau. Ở phần này, chúng ta chỉ thảo luận việc làm sao kiểm tra một đồ thị vô hướng có phải là hai phía hay không.

Thuật toán đơn giản nhất là dùng BFS, đánh số đỉnh đầu tiên (lớp zero) là 0, các con trực tiếp của nó (lớp 2) là 1, cứ luân phiên như vậy, ta còn gọi cách này là tô màu đồ thị, ở đây chỉ có hai màu trắng đen. Sau đó chúng ta kiểm tra lại nếu có hai đỉnh kề nhau mà trùng màu thì kết luận đồ thị không phải hai phía, ngược lại thì nó là hai phía.

Nhiệm vụ 4. UVa 10004 - Bicoloring

Tìm khớp, cầu trên đồ thị vô hướng

Nhắc lại khái niệm khớp: là đỉnh mà khi bỏ nó cùng các cạnh liên quan khiến cho số thành phần liên thông trong đồ thị tăng lên

Nhắc lại khái niệm cầu: Là cạnh mà khi bỏ nó khỏi đồ thị sẽ làm số thành phần liên thông trong đồ thị tăng lên.

Từ hai khái niệm trên ta dễ dàng đưa ra được một thuật toán vét cạn để tìm khớp (tương tự cho cầu) như sau:

Bước 1. Chạy BFS hay DFS để tìm số thành phần liên thông của đồ thị.

Bước 2. Cứ mỗi đỉnh, ta bỏ nó đi rồi lại chạy lại thuật toán tìm thành phần liên thông, nếu việc bỏ đỉnh nào làm số thành phần liên thông tăng lên thì nó là khớp.

Độ phức tạp: O(V*(V+E))

Sử dụng DFS_NUM và DFS_LOW

Sử dụng lại hai tính chất này của cây DFS mà ta đã xét ở mục tìm thành phần liên thông mạnh của đồ thị. Trong khi thực hiện đánh việc cập nhật DFS_LOW cho các đỉnh, ta sẽ kiểm tra nếu từ u duyệt đến v (u -->v) mà dfs_low(v)>=dfs_num(u) thì u là khớp. Vì như phân tích hôm trước, nếu có điều đó xảy ra, nghĩa là v đã tiếp cận với u qua nhánh dfs con của nó, và u là tổ tiên có dfs_num nhỏ nhất mà v tiếp cận được, đồng nghĩa với việc v muốn đi về lại tổ tiên cao hơn thì phải qua u, nên nếu bỏ u đi thì v không về được nữa --> u là khớp.

Nhiệm vụ 5. Thực hiện contest ngắn - Ứng dụng DFS và BFS 1