Ứ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

• CS Academy

• 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.

Trong quá trình DFS, chúng ta chia các đỉnh thành ba nhóm:

1. Những đỉnh đã thăm (VISITED) - là những đỉnh đã được pop ra khỏi STACK

2. Những đỉnh đang thăm - là những đỉnh đang nằm trong STACK

3. Những đỉnh chưa thăm (UNVISITED)

Trong đồ thị có hướng không chu trình (DGA), xét cung A--->B, ta gọi A là đỉnh kề vào của B, còn B được gọi là đỉnh kề ra của A. Rõ ràng khi ta đang thăm đến A thì B chỉ có thể thuộc một trong hai nhóm là 1 hoặc 3, tức là hoặc đã được thăm hoặc là chưa thăm. Vì nếu B cũng đang thăm (đang nằm trong STACK) thì cung A--->B sẽ tạo một chu trình, đều này không tồn tại trong một DGA.

Tính chất này đưa đến một quan sát là một đỉnh được pop ra khỏi STACK khi mà tất cả các đỉnh kề ra của nó đã được pop ra. Điều này gợi ý cho chúng ta một hướng tiếp cận thuật toán này là chúng ta chỉ liệt kê các đỉnh theo thứ tự ngược lại với quá trình DFS thì đó chính là thứ tự TOPO.

Nguồn: CS academy - Topo sorting

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.

Cần nhắc lại hai khái niệm quan trọng trên đồ thị có hướng là bán bậc vào (in_degree) và bán bật ra (out_degree). Bán bậc vào là số cạnh đi vào một đỉnh u, ngược lài bán bậc ra là số cạnh đi ra từ u.

Ta quan sát thấy rằng đỉnh đầu tiên trong thứ tự TOPO phải có bán bậc vào bằng 0. Vì nếu bán bậc vào của nó khác 0, nghĩa là tồn tại một chu trình, điều này không tồn tại trong DAG.

Dựa trên quan sát trên, thuật toán của Kahn đơn giản như sau:

Bước 1. Tìm đỉnh có bán bậc vào bằng 0, đưa nó vào danh sách topo.

Bước 2. Xóa đỉnh đó khỏi đồ thì, đồng thời xóa tất cả các cạnh đi ra từ nó.

Bước 3. Sau bước 2 bạn lại nhận được một DAG, quay lại bước 1.

Thuật toán kết thúc khi số đỉnh trên đồ thị rỗng.

Các bạn quan sát đoạn code sau, lưu ý một số container quan trọng:

• in_degree[] : để lưu bán bậc vào của tất cả các đỉnh đồ thị.

• AL[u] : lưu danh sách đỉnh kề ra của u.

• pq: hàng đời ưu tiên để lưu tạm các đỉnh có bán bậc vào bằng 0 để chờ xử lý.

Nguồn: CS academy - Topo sorting

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

Nhiệm vụ 6. Thực hiện contest - Topo Sorting

Nhiệm vụ 7. Thực hiện contest - Khớp và cầu