Ứng dụng 1: sắp xếp topo và bài toán xếp lịch¶

Thứ tự topo¶

Thứ tự topo (topological ordering) của một đồ thị có hướng là một thứ tự sắp xếp của các đỉnh sao cho với mọi cung từ \(u\) đến \(v\) trong đồ thị, \(u\) luôn nằm trước \(v\) trong thứ tự.

Đồ thị có hướng \(G = (V, E)\) được gọi là Directed Acyclic Graph (DAG) khi đồ thị đó không có chu trình (có hướng). Khi đó nếu \(G\) là một DAG thì \(G\) có thứ tự topo.

Ví dụ cho đồ thị sau:

../../_images/topo-order.jpg — Hình 17 Ví dụ DAG¶

Một thứ tự topo hợp lệ:

\[0 \to 1 \to 2 \to 3 \to 4 \to 5 \to 7 \to 6.\]

Thuật toán sắp xếp Topo¶

Xét đồ thị \(G = (V, E)\). Ta xây dựng ý tưởng tìm thứ tự topo cho các đỉnh đồ thị.

Với mỗi đỉnh \(u \in V\), ta duyệt \(\mathrm{DFS}(u)\).
Khi duyệt \(\mathrm{DFS}(u)\), với mỗi đỉnh \(v\) kề với \(u\) ta có hai trường hợp:
1. \(v\) chưa được thăm: ta duyệt DFS đỉnh \(v\).
2. \(v\) đã được thăm: ta có hai trường hợp:
  1. Vòng lặp for thăm \(v\) trước \(u\) (thứ tự từ điển): trường hợp này không tạo ra chu trình mà do thứ tự duyệt đỉnh.
  2. \(v\) có đường đi từ \(v\) tới \(u\) trong quá trình duyệt DFS. Vì có cung \((u, v)\) nên ở đây tồn tại chu trình, đồ thị không phải DAG.

Như vậy, nếu đỉnh \(u\) đứng trước tất cả đỉnh \(v\) kề với nó thì ta gán thứ tự topo của \(u\) là \(L_u = c\) và giảm \(c\) đi một đơn vị (khởi tạo \(c = \lvert V \rvert\) là số lượng đỉnh). Vì \(c > 0\) nên ban đầu ta khởi tạo \(L_u = 0\) với mọi \(u \in V\).

Vì ta phải duyệt hết tất cả đỉnh kề của \(u\) thì mới gán \(L_u = c \neq 0\) được, do đó với mỗi đỉnh \(v\) kề \(u\) mà (1) \(v\) đã thăm, và (2) \(v\) chưa có thứ tự topo, thì đồng nghĩa \(v\) nằm trong chu trình chứa \(u\).

Thuật toán 2 (Sắp xếp topo trên đồ thị có hướng)

Input. Đồ thị có hướng \(G = (V, E)\). Giả sử các đỉnh được đánh số từ \(0\)

Output. Thứ tự topo các đỉnh trong \(G\)

Bước khởi tạo

Khởi tạo mảng \(L \gets \emptyset\) chứa thứ tự topo đã sắp xếp.
Khởi tạo mảng \(d_u \gets 0\) với mọi \(u \in V\) đánh dấu đỉnh đã thăm (\(0\) nếu chưa được thăm và \(1\) nếu đã được thăm)
Khởi tạo mảng \(t_u \gets 0\) với mọi \(u \in V\) đánh dấu thứ tự topo của mỗi đỉnh
Khởi tạo \(c \gets \lvert V \rvert\)

Thuật toán tìm thứ tự topo

Với mọi đỉnh \(u\), nếu \(d_u = 0\) (\(u\) chưa được thăm) thì gọi hàm \(\mathrm{DFS}(u)\)
Hàm \(\mathrm{DFS}(u)\) thực hiện:
1. \(d_u \gets 1\) (đánh dấu \(u\) đã được thăm)
2. Xét mọi đỉnh \(v\) kề \(u\) (từ \(u\) đi tới \(v\))
  1. Nếu \(d_v = 1\) (\(v\) đã thăm) và \(t_v = 0\) (\(v\) chưa có thứ tự topo)
    
    \(\Rightarrow\) Phát hiện chu trình, đồ thị không phải DAG, thoát chương trình
  2. Nếu \(d_v = 0\), gọi \(\mathrm{DFS}(v)\).
3. Chèn \(u\) vào phía trước \(L\)
4. \(L_u \gets c\)
5. \(c \gets c - 1\)

Ví dụ với đồ thị không có chu trình¶

Đầu tiên khởi tạo \(c = \lvert V \rvert = 8\), \(d_u \gets 0\) và \(t_u \gets 0\) với \(0 \leqslant u \leqslant 7\). Xét các đỉnh từ \(0\) tới \(7\):

Xét đỉnh \(0\): vì \(d_0 = 0\) nên gọi \(\mathrm{DFS}(0)\):
1. \(\color{red}d_0 \gets 1\)
2. Xét \(1\) kề với \(0\): vì \(d_1 = 0\) và \(t_1 = 0\) nên gọi \(\mathrm{DFS}(1)\):
  1. \(\color{red}d_1 \gets 1\)
  2. Xét \(2\) kề với \(1\): vì \(d_2 = 0\) và \(t_2 = 0\) nên gọi \(\mathrm{DFS}(2)\):
    1. \(\color{red}d_2 \gets 1\)
    2. Xét \(3\) kề với \(2\): vì \(d_3 = 0\) và \(t_3 = 0\) nên gọi \(\mathrm{DFS}(3)\):
      1. \(\color{red}d_3 \gets 1\)
      2. Xét \(4\) kề với \(3\): vì \(d_4 = 0\) và \(t_4 = 0\) nên gọi \(\mathrm{DFS}(4)\)
        
        \(\color{red}d_4 \gets 1\)
        
        Không còn đỉnh nào kề với \(4\): chèn \(4\) vào trước \(L\) thu được \((4)\); \(\color{blue}t_4 \gets 8\); \(\color{green}c \gets 7\)
      3. Không còn đỉnh nào kề với \(3\): chèn \(3\) vào trước \(L\) thu được \((3, 4)\); \(\color{blue}t_3 \gets 7\); \(\color{green}c \gets 6\)
    3. Xét \(5\) kề với \(2\): vì \(d_5 = 0\) nên gọi \(\mathrm{DFS}(5)\):
      1. \(\color{red}d_5 \gets 1\)
      2. Không còn đỉnh nào kề với \(5\): chèn \(5\) vào trước \(L\) thu được \((5, 3, 4)\); \(\color{blue}t_5 \gets 6\); \(\color{green}c \gets 5\)
    4. Không còn đỉnh nào kề với \(2\): chèn \(2\) vào trước \(L\) thu được \((2, 5, 3, 4)\); \(\color{blue}t_2 \gets 5\); \(\color{green}c \gets 4\)
  3. Xét \(3\) kề với \(1\): vì \(\color{red}d_3 = 1\) và \(\color{blue}t_3 = 7 \neq 0\) nên bỏ qua
  4. Không còn đỉnh nào kề với \(1\), chèn \(1\) vào trước \(L\) thu được \((1, 2, 5, 3, 4)\); \(\color{blue}t_1 \gets 4\); \(\color{green}c \gets 3\)
3. Xét \(2\) kề với \(0\), vì \(\color{red}d_2 = 1\) và \(\color{blue}t_2 = 5 \neq 0\) nên bỏ qua
4. Không còn đỉnh nào kề với \(0\), chèn \(0\) vào trước \(L\) thu được \((0, 1, 2, 5, 3, 4)\); \(\color{blue}t_0 \gets 3\); \(\color{green}c \gets 2\)
Xét các đỉnh \(1\), \(2\), \(3\), \(4\) và \(5\) đều đã được thăm nên ta bỏ qua
Xét đỉnh \(6\), vì \(d_6 = 0\) nên gọi \(\mathrm{DFS}(6)\):
1. \(\color{red}d_6 \gets 1\)
2. Không còn đỉnh nào kề với \(6\), chèn \(6\) vào trước \(L\) thu được \((6, 0, 1, 2, 5, 3, 4)\); \(\color{blue}t_6 \gets 2\); \(\color{green}c \gets 1\)
Xét đỉnh \(7\), vì \(d_7 = 0\) nên gọi \(\mathrm{DFS}(7)\):
1. \(\color{red}d_7 \gets 1\)
2. Xét \(6\) kề với \(7\), vì \(\color{red}d_6 = 1\) và \(\color{blue}t_6 = 2 \neq 0\) nên bỏ qua
3. Không còn đỉnh nào kề với \(7\), chèn \(7\) vào trước \(L\) thu được \((7, 6, 0, 1, 2, 5, 3, 4)\), \(\color{blue}t_7 \gets 1\); \(\color{green}c \gets 0\)

Nhận xét:

Đồ thị trên có hai phần rời nhau, do đó thứ tự giữa mỗi phần tử trong tập \(\{ 0, 1, 2, 3, 4, 5 \}\) không liên quan đến tập \(\{ 6, 7 \}\).
Đỉnh \(6\) được duyệt trước đỉnh \(7\) và nhận được thứ tự topo. Do đó khi duyệt đỉnh \(7\), vì \(6\) kề \(7\) và đã có thứ tự topo nên không phải chu trình.

Tiếp theo ta sẽ xét một ví dụ khác với chu trình.

Ví dụ với đồ thị có chu trình¶

../../_images/topo-order-2.jpg — Hình 19 Đồ thị có chu trình¶

Đầu tiên khởi tạo \(c = \lvert V \rvert = 3\), \(d_u \gets 0\) và \(t_u \gets 0\) với \(0 \leqslant u \leqslant 2\). Xét các đỉnh từ \(0\) tới \(2\):

Xét đỉnh \(0\): vì \(d_0 = 0\) nên gọi \(\mathrm{DFS}(0)\):
1. \(\color{red}d_0 \gets 1\)
2. Xét \(1\) kề với \(0\): vì \(d_1 = 0\) và \(t_1 = 0\) nên gọi \(\mathrm{DFS}(1)\):
  1. \(\color{red}d_1 \gets 1\)
  2. Xét \(2\) kề với \(1\): vì \(d_2 = 0\) và \(t_2 = 0\) nên gọi \(\mathrm{DFS}(2)\):
    1. \(\color{red}d_2 \gets 1\)
    2. Xét \(0\) kề với \(2\): vì \(\color{red}d_0 = 1\) và \(t_0 = 0\), ta phát hiện chu trình và kết thúc thuật toán.

Ở ví dụ này, thuật toán đã gặp điều kiện \(d_v = 1\) và \(t_v = 0\) (Thuật toán 2), và phát hiện chu trình.

Đánh giá thuật toán¶

Mỗi đỉnh \(u \in V\) ta chỉ duyệt qua một lần nên độ phức tạp là \(O(\lvert V \rvert)\).
Với mỗi đỉnh \(u \in V\), ta duyệt tất cả đỉnh kề một lần, tương ứng duyệt tất cả các cung một lần, nên độ phức tạp là \(O(\lvert E \rvert)\).
Như vậy tổng độ phức tạp của giải thuật trên là \(O(\lvert V \rvert + \lvert E \rvert)\).

Ứng dụng giải bài toán xếp lịch¶

Thuật toán sắp xếp topo được ứng dụng hỗ trợ cho rất nhiều giải thuật quy hoạch động trên mảng trật tự topo.

Mô tả bài toán: ở trường Đại học U nọ có một số học phần được gọi là "học phần tiên quyết" --- là học phần mà sinh viên bắt buộc phải học trước khi học một vài học phần khác. Các sinh viên cần phải sắp xếp lịch học sao cho phù hợp với yêu cầu "học phần tiên quyết". Là một nhân viên xếp lịch học, bạn hãy đưa ra số kì tối thiểu mà sinh viên cần học.

Input: \(N\) môn học, \(M\) quan hệ "tiên quyết" giữa hai môn \(u\) và \(v\).
Output: Số kì tối thiểu cần học.

Đầu tiên ta cần một số nhận xét:

Nếu môn \(u\) là môn tiên quyết của môn \(v\) và được học ở học kì thứ \(i\) (\(i \geqslant 1\)), thì môn \(v\) phải được học ở học kì \(k\) với \(k > i\).
Với một dãy liên tục các môn \(a_i\), \(a_{i+1}\), ..., \(a_k\) mà \(a_i\) là môn tiên quyết của \(a_{i+1}\) thì số kì tối thiểu mà sinh viên cần học chính là độ dài của dãy.
Không có trường hợp một dãy \(a_i\), \(a_{i+1}\), ...., \(a_i\) (không được phép có chu trình).
Đáp án của bài toán chính là độ dài dài nhất của dãy các môn trên.

Dựa vào các nhận xét trên, ta có thể áp dụng thuật toán sắp xếp topo kết hợp ý tưởng quy hoạch động để giải quyết. Trong quá trình duyệt của thuật toán, ta luôn đảm bảo thứ tự topo --- cũng là thứ tự môn học, đồng thời ta có thể dùng một mảng để tính được số kì tối thiểu cần để kết thúc các môn học. Đáp án sẽ là phần tử lớn nhất của mảng này.

Ta sẽ xây dựng một mô hình đồ thị để lưu trữ thông tin trên máy tính. Các thông tin cần lưu trữ:

\(N\) môn học tương ứng \(N\) đỉnh.
\(M\) quan hệ \((u, v)\) tương ứng môn \(u\) là tiên quyết của môn \(v\), khi đó trên đồ thị ta vẽ cung \(u \to v\).
Đồ thị DAG để đảm bảo tính thực tế.
Số môn cần học trước môn \(u\) để \(u\) có thể được học.

Với các thông tin cần lưu trữ, thuật toán dưới đây dưới sẽ lưu trữ đồ thị dưới dạng danh sách kề.

vector<int> vs[maxn] --- mảng vs chứa \(M\) cung; vs[u] chứa các đỉnh kề đỉnh u;
int f[maxn] --- f[u] lưu số kì tối đa cần học sau môn u.

Thuật toán:

B1: Nhập dữ liệu, lưu trữ dưới dạng danh sách kề.
B2: Duyệt các đỉnh, nếu đỉnh u chưa duyệt ta sẽ gọi hàm DFS(u).
1. Với mỗi đỉnh u, duyệt các đỉnh v kề với u.
2. Nếu v chưa được duyệt thì ta gọi hàm DFS(v).
3. Ngược lại ta cập nhật f[u] = max(f[u], f[v]+1);
4. Lặp lại B2 cho đến khi mọi đỉnh được duyệt.
B3: Cập nhật đáp án từ các f[u].

Ví dụ demo ở đoạn code sau.

#include <vector>
#include <iostream>

using namespace std;

int n, m;                   // số lượng đỉnh, số lượng cạnh
vector<vector<int>> vs;     // danh sách kề
vector<int> f;              // lưu thứ tự topo + đánh dấu đỉnh đã thăm

void DFS(int u);

int main()
{
   cin >> n >> m;

   f.resize(n);
   vs.resize(n);

   for (int i = 0; i < n; i++) f[i] = 0;

   for (int i = 0; i < m; i++)
   {
      int u, v;
      cin >> u >> v;
      vs[u].push_back(v); // cung (u, v)
   }

   int ans = 0;
   for (int u = 0; u < n; u++)
      if (f[u] == 0 )
      {
            DFS(u);
            ans = max(ans , f[u]);
      }
   cout << "So ki toi thieu: " << ans << endl;
   return 0;
}

void DFS(int u)
{
   f[u] = 1;
   for (int i = 0; i < vs[u].size(); i++)
   {
      int v = vs[u][i];
      if (f[v] == 0) // v chưa được thăm
            DFS(v);
      f[u] = max(f[v] + 1, f[u]); // cập nhật giá trị f[u]
   }
}

Chúng ta thử chạy bộ dữ liệu ở hình 18. Đầu vào như sau:

Kết quả số kì tối thiểu là \(5\). Điều này hợp lý vì khi in mảng f các bạn sẽ thấy thứ tự topo như sau:

Môn học	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)
Thứ tự topo	\(5\)	\(4\)	\(3\)	\(2\)	\(1\)	\(1\)	\(1\)	\(2\)

ở học kì 1 (thứ tự topo là \(5\)) sinh viên học môn \(0\) (không có môn tiên quyết);
ở học kì 2 (thứ tự topo là \(4\)) sinh viên học môn \(1\) (môn tiên quyết là \(0\));
ở học kì 3 (thứ tự topo là \(3\)) sinh viên học môn \(2\) (môn tiên quyết là \(0\) và \(1\));
ở học kì 4 (thứ tự topo là \(2\)) sinh viên học môn \(3\) (môn tiên quyết là \(1\) và \(2\)) và môn \(7\) (không có môn tiên quyết);
ở học kì 5 (thứ tự topo là \(1\)) sinh viên học môn \(4\) (môn tiên quyết là \(3\)), môn \(5\) (môn tiên quyết là \(2\)) và môn \(6\) (môn tiên quyết là \(7\)).

../../_images/topo_schedule-1.jpg — Hình 20 Thứ tự môn học từ thuật toán¶

Nhận xét thuật toán

Từ đỉnh u gọi hàm DFS(v), ta chắc chắn có f[u] <= f[v]. Do đó ta chỉ cần lấy f[u] lớn nhất được gọi từ hàm main.
Vì bài toán không yêu cầu đưa ra một thứ tự topo cụ thể, nên ta có thể lược bỏ một số thao tác không cần thiết trong giải thuật sắp xếp topo.
Thuật toán dựa trên vòng duyệt DFS của thuật toán topo do đó có độ phức tạp \(O(\lvert V \rvert + \lvert E \rvert)\).
Đây chỉ là một ứng dụng rất cơ bản của thuật toán sắp xếp topo. Từ bài toán này, ta có thể phát triển theo nhiều hướng khác, ứng dụng cho nhiều trường hợp hơn.
Trên thực tế có thể có nhiều thứ tự topo và thuật toán trên chỉ đưa ra một thứ tự đơn giản. Chúng ta có thể thấy ở bộ dữ liệu trên:
- môn \(7\) không có môn tiên quyết nên hoàn toàn có thể được học ở học kì 1 thay vì ở học kì 4, theo đó môn \(6\) có thể học ở học kì 2, 3, 4, hoặc 5;
- môn \(3\) và \(5\) đều có môn tiên quyết là \(2\) nên có thể được học ở cùng học kì 4, thay vì phải để môn \(5\) tới học kì \(5\).
Hình 21 Một thứ tự môn học khác¶