Bài viết này sẽ giúp bạn tìm hiểu về bài toán sắp xếp Tô-pô(Topological Sort). Sắp xếp Tô-pô là một trong những bài toán có tính ứng dụng cao trong Tin học lẫn Toán học và cả trong đời sống.
Sắp xếp Tô-pô được áp dụng nhiều nhất đối với các bài toán biểu diễn mối quan hệ phụ thuộc giữa các đối tượng.
Ví dụ như nó có thể được áp dụng trong việc lập ra lịch trình công việc. Một tập hợp các công việc phụ thuộc lẫn nhau có thể được sắp xếp theo một thứ tự nhất định để chúng được thực hiện.
Ta có ví dụ thực tế như sau:
Để có được bằng cấp, sinh viên phải hoàn thành một số khóa học bắt buộc. Các khóa học này không nhất thiết phải được hoàn thành theo bất kỳ trình tự nhất định nào, nhưng có một số khóa học là điều kiện tiên quyết cho những khóa học khác.
Ví dụ, khóa học "Giới thiệu về thuật toán trong Tin học" có thể phụ thuộc vào các khóa học “Nhập môn thuật toán”, “Giới thiệu về cấu trúc dữ liệu”, “Nhập môn lập trình”, … Đây là mối quan hệ phụ thuộc; việc tham gia các khóa học sau phụ thuộc vào việc tham gia các khóa học tiên quyết của nó.
Từ đó, ta có thể xây dựng một đồ thị với mỗi đỉnh tương ứng với một khóa học và mỗi cạnh có hướng từ đỉnh đến đỉnh khi và chỉ khi khóa học tương ứng với đỉnh là điều kiện tiên quyết cho khóa học tương ứng với đỉnh . Việc sắp xếp thứ tự các đỉnh của đồ thị này sẽ cung cấp một thứ tự khả thi mà các khóa học có thể được thực hiện.
Tất nhiên, nó không thể được sử dụng để giải quyết vấn đề nghiêm trọng hơn về xung đột lịch trình.
Dễ nhận thấy rằng, một đồ thị tồn tại thứ tự Tô-pô thì đồ thị đó phải là đồ thị có hướng và không có chu trình (Directed Acyclic Graph - DAG). Vì nếu đồ thị có chứa một chu trình, thì phải đứng sau theo thứ tự Tô-pô, phải đứng sau , v.v...; nhưng sau đó phải đứng sau , dẫn đến kết luận vô lý khi phải đứng sau chính nó trong danh sách.
Vậy câu hỏi đặt ra là liệu điều kiện này có đủ hay không? Có đúng là một đồ thị có thể được sắp xếp theo thứ tự Tô-pô khi và chỉ khi đồ thị đó là một ? Câu trả lời là đúng.
Định lý : Một đồ thị tồn tại thứ tự Tô-pô khi và chỉ khi đồ thị đó là DAG. Đồng nghĩa, mọi DAG đều luôn tồn tại ít nhất một thứ tự Tô-pô, và có thuật toán để tìm thứ tự Tô-pô trong thời gian tuyến tính.
Chứng minh :
Rõ ràng, một chỉ gồm đỉnh duy nhất luôn có thể được sắp xếp theo thứ tự Tô-pô. Khi đó, danh sách Tô-pô trong trường hợp này chỉ bao gồm chính đỉnh đó.
Giả sử rằng bất kỳ nào có đỉnh đều có thể được sắp xếp theo thứ tự Tô-pô. Bây giờ hãy xem xét các có đỉnh. Nhớ lại rằng mọi đều có ít nhất một đỉnh nguồn (đỉnh không có cung vào). Hãy để đỉnh nguồn này làm giá trị đầu tiên trong danh sách Tô-pô, rồi loại bỏ đỉnh này cùng cách cạnh kề với nó ra khỏi đồ thị. Khi đó, ta sẽ có được đồ thị mới gồm đỉnh là đồ thị con của đồ thị ban đầu. Rõ ràng, các chu trình không thể được tạo ra bằng cách loại bỏ các cạnh và đỉnh. Bằng giả thiết ban đầu, ta có thể sắp xếp đồ thị con này theo thứ tự Tô-pô. Sau đó, ta nối thứ tự Tô-pô của đồ thị con vào cuối danh sách hiện tại để có được danh sách thứ tự Tô-pô của đồ thị đỉnh với đỉnh nguồn là giá trị đầu tiên trong danh sách.
Ví dụ minh họa: Để xác định thứ tự Tô-pô của gồm đỉnh, ta thêm đỉnh nguồn vào trong danh sách Tô-pô rồi nối thêm thứ tự Tô-pô của đồ thị con đỉnh.
Bây giờ, với hai đỉnh bất kỳ và trong danh sách Tô-pô, giả sử đứng trước :
Nếu là giá trị đầu tiên trong danh sách (đỉnh nguồn), trong trường hợp đó, rõ ràng là không thể tồn tại cạnh nối từ .
Nếu cả hai đỉnh và đều không phải là giá trị đầu tiên trong danh sách, dù trong trường hợp nào thì chúng đều được sắp xếp đúng vì chúng thuộc phần đồ thị con được sắp xếp theo thứ tự Tô-pô.
Do đó, danh sách đỉnh mới này là một thứ tự Tô-pô của gồm đỉnh.
Tính chất
Thứ tự Tô-pô không nhất thiết phải là duy nhất. Có thể có một số thứ tự Tô-pô khác nhau trong một đồ thị.
Tuy nhiên, thứ tự Tô-pô sẽ là duy nhất khi có đường đi .
Cho đồ thị có hướng không chu trình (Directed Acyclic Graph - DAG) . Hãy đánh số lại các đỉnh của sao cho chỉ có cung nối từ đỉnh có chỉ số nhỏ đến đỉnh có chỉ số lớn hơn.
Input
Dòng đầu chứa hai số nguyên và là số đỉnh và số cung của đồ thị ;
dòng tiếp theo, mỗi dòng chứa một cặp số cho biết một cung nối từ tới trong .
Output
Ghi ra số nguyên dương, số thứ là chỉ số của đỉnh thứ sau khi đánh số lại. Hai số trên cùng một dòng được ghi cách nhau một dấu cách.
Từ phần chứng minh của định lý trên (trong mục Điều kiện tồn tại thứ tự Tô-pô), ta có thuật toán để tìm ra một thứ tự Tô-pô như sau:
Bắt đầu với một danh sách Tô-pô trống.
Tìm đỉnh nguồn của . Thêm đỉnh này vào cuối danh sách Tô-pô.
Loại bỏ đỉnh này và tất cả các cạnh kề với nó ra khỏi .
Nếu số đỉnh của lớn hơn , hãy quay lại bước .
Sau khi kết thúc, danh sách sẽ chứa một thứ tự Tô-pô của .
Để thực hiện thuật toán này một cách hiệu quả, ta sẽ không thực sự loại bỏ các đỉnh khỏi đồ thị trong bước , vì đây là một quá trình phức tạp nếu đồ thị được biểu diễn dưới dạng ma trận kề hoặc danh sách kề.
Ta cũng sẽ không duyệt qua toàn bộ đồ thị ở mỗi bước để tìm đỉnh nguồn. Điều này cũng tốn kém về mặt thời gian và tính toán.
Thay vào đó, ta có những nhận xét sau:
Một đỉnh là đỉnh nguồn khi và chỉ khi số lượng cung vào của nó bằng .
Nếu một đỉnh không phải là đỉnh nguồn, nó sẽ trở thành đỉnh nguồn sau khi tất cả các cung vào của nó đã bị xóa. Một cung vào của nó chỉ bị xóa khi đỉnh còn lại của cung đó bị xóa.
Giả sử ta biết vị trí của tất cả các đỉnh nguồn trong và ta thực hiện các bước và một lần. Sau đó, những đỉnh duy nhất có thể trở thành đỉnh nguồn là những đỉnh có cung vào nối với đỉnh vừa bị xóa.
Sau khi xác định được thứ tự Tô-pô của đồ thị, ta sẽ đánh số lại các đỉnh của đồ thị theo thứ tự.
Mảng indegree[] - Lưu số lượng cung vào của mỗi đỉnh.
Vector g[] - Danh sách cạnh kề của mỗi đỉnh.
Vector topo - Danh sách thứ tự Tô-pô.
Queue listSource - Danh sách các đỉnh không có cung vào.
#include <bits/stdc++.h>
using namespace std;
const int maxN = 110;
int n, m;
int indegree[maxN], ans[maxN];
vector <int> g[maxN], topo;
queue <int> listSource;
main() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
indegree[v]++;
}
for (int u = 1; u <= n; ++u)
if (!indegree[u]) listSource.push(u);
while (!listSource.empty()) {
int u = listSource.front();
listSource.pop();
topo.push_back(u);
for (auto v : g[u]) {
indegree[v]--;
if (!indegree[v]) listSource.push(v);
}
}
if (topo.size() < n) {
cout << "Error: graph contains a cycle";
return 0;
}
/* Sau khi xác định được thứ tự Tô-pô của đồ thị, ta sử dụng
mảng ans để đánh số lại các đỉnh */
int cnt = 0;
for (auto x : topo) ans[x] = ++cnt;
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}
Mô tả quá trình
Thứ tự Tô-pô không phải là duy nhất. Quá trình sau chỉ mô tả lại quá trình xác định thứ tự Tô-pô theo như code mẫu.
Sau khi xác định được thứ tự Tô-pô của đồ thị là topo = {1; 6; 7; 2; 4; 5; 3}. Ta đánh số lại các đỉnh. Khi đó ta sẽ có mảng ans = {1; 4; 7; 5; 6; 2; 3}.
Để thực hiện thuật toán này một cách hiệu quả, ta cần phải có khả năng duyệt qua các đỉnh kề của một đỉnh một cách hiệu quả. Điều này được thực hiện tốt nhất bằng cách sử dụng danh sách kề (vector g[]).
Ngoài ra, listSource nên là một ngăn xếp (stack) hoặc một hàng đợi (queue) để việc thêm và loại bỏ các phần tử có thể được thực hiện trong thời gian không đổi.
Thuật toán sẽ luôn tìm ra một thứ tự Tô-pô nếu nó tồn tại. Còn nếu nó không tồn tại (nghĩa là đồ thị ban đầu không phải là ) thì danh sách topo sẽ không được điền đầy đủ và thông báo lỗi sẽ được in ra.
Thứ tự Tô-pô sẽ là duy nhất khi và chỉ khi listSource chứa chính xác một đỉnh ở đầu mỗi lần lặp của vòng lặp while.
Độ phức tạp
Ở vòng lặp while để duyệt các đỉnh trong listSource, ta mất độ phức tạp vì mỗi đỉnh chỉ được thêm vào nhiều nhất lần (ở ban đầu hoặc ngay sau khi cạnh vào cuối cùng của nó bị loại bỏ). Và ta sẽ mất thêm độ phức tạp để duyệt các cạnh vì mỗi cạnh chỉ được kiểm tra nhiều nhất lần trong vòng lặp while (khi đỉnh nối với nó được lấy ra).
Có một thuật toán khác cho sắp xếp Tô-pô dựa trên tìm kiếm theo chiều sâu(Depth-First Search - DFS).
Đối với thuật toán 2, quá trình tìm kiếm theo chiều sâu sẽ trả ra danh sách nghịch đảo thứ tự Tô-pô. Đơn giản hơn, nó chính là danh sách Tô-pô bị đảo ngược lại.
Điều này tương đương với việc nếu tồn tại cung thì có số thứ tự cao hơn trong danh sách nghịch đảo Tô-pô.
Ví dụ minh họa:
Chứng minh: Hãy xem xét cây DFS của đồ thị (tìm hiểu thêm về cây tại đây):
Nếu là tổ tiên của trong cây , thì quá trình duyệt xong cây con gốc sẽ kết thúc sớm hơn quá trình duyệt xong cây con gốc . Do đó, sẽ có số thứ tự cao hơn trong danh sách.
Nếu là tổ tiên của trong cây và tồn tại cung nối từ đỉnh thuộc cây con gốc đến đỉnh thì đồ thị có chu trình (không phải là DAG) nên sẽ không tồn tại thứ tự Tô-pô.
Nếu không phải là tổ tiên của và cũng không phải là tổ tiên của trong cây thì khi đó, đỉnh và sẽ nằm trên nhánh khác nhau của cây . Do đó cung nối từ nhánh chứa đỉnh đến nhánh chứa đỉnh là cung chéo và đỉnh sẽ được duyệt sau nên sẽ có số thứ tự cao hơn trong danh sách.
Ví dụ minh họa: Bắt đầu duyệt từ đỉnh . Các "cạnh nét liền" là cung của cây . Các "cạnh nét đứt" không phải là cung của cây . Với cung chéo , đỉnh chắc chắn sẽ được duyệt trước . Vì nếu được duyệt trước thì đỉnh sẽ là tổ tiên của đỉnh và cung sẽ không còn là cung chéo nữa, khi đó ta xét giống như ở trường hợp đầu tiên.
Từ những nhận xét trên, ta có thuật toán để tìm ra một thứ tự Tô-pô như sau:
Xuất phát từ một điểm chưa được duyệt, ta bắt đầu duyệt trên đồ thị xuất phát từ điểm đó.
Dùng một mảng để lưu trạng thái của mỗi đỉnh. Có trạng thái:
Trạng thái 0 : Đỉnh chưa được duyệt (chưa từng được gọi hàm ).
Trạng thái 1 : Đỉnh vẫn đang duyệt (hàm với đỉnh này chưa kết thúc).
Trạng thái 2 : Đỉnh đã duyệt xong (hàm với đỉnh này đã kết thúc).
Hiển nhiên, khi đang duyệt mà ta gặp phải một đỉnh ở trạng thái 1 thì điều đó chứng tỏ đồ thị đang xét có chứa chu trình, và không thể sắp xếp Tô-pô được.
Sau khi kết thúc duyệt trên đồ thị, thứ tự hoàn tất duyệt của mỗi đỉnh chính là danh sách nghịch đảo thứ tự Tô-pô.
Để có được thứ tự Tô-pô, đơn giản ta chỉ cần đảo ngược lại danh sách nghịch đảo thứ tự Tô-pô.
Sau khi xác định được thứ tự Tô-pô của đồ thị, ta sẽ đánh số lại các đỉnh của đồ thị theo thứ tự.
#include <bits/stdc++.h>
using namespace std;
const int maxN = 110;
int n, m;
int visit[maxN], ans[maxN];
vector <int> g[maxN];
stack <int> topo;
void dfs(int u) {
visit[u] = 1;
for (auto v : g[u]) {
if (visit[v] == 1) {
cout << "Error: graph contains a cycle";
exit(0);
}
if (!visit[v]) dfs(v);
}
topo.push(u);
visit[u] = 2;
}
main() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
for (int i = 1; i <= n; ++i)
if (!visit[i]) dfs(i);
/* Sau khi xác định được thứ tự Tô-pô của đồ thị, ta sử dụng
mảng ans để đánh số lại các đỉnh */
int cnt = 0;
while (!topo.empty()) {
ans[topo.top()] = ++cnt;
topo.pop();
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}
Mô tả quá trình
Thứ tự Tô-pô không phải là duy nhất. Quá trình sau chỉ mô tả lại quá trình xác định thứ tự Tô-pô theo như code mẫu.
Sau khi xác định được thứ tự Tô-pô của đồ thị là topo = {7; 6; 1; 4; 5; 2; 3}. Ta đánh số lại các đỉnh. Khi đó ta sẽ có mảng ans = {3; 6; 7; 4; 5; 2; 1}.
Thuật toán 2 đơn giản và dễ cài đặt so với hơn thuật toán 1.
Ta sử dụng ngăn xếp (stack) để có thể dễ dàng đảo ngược lại thứ tự hoàn tất duyệt của mỗi đỉnh. Nói cách khác là ta đảo ngược lại danh sách nghịch đảo thứ tự Tô-pô để có được thứ tự Tô-pô.
Với phương pháp sắp xếp Tô-pô bằng , nếu đồ thị không phải là thì ta vẫn có thể tìm ra một thứ tự, nhưng ta lại có thế dùng để kiểm tra luôn xem đồ thị có là hay không.
Nếu đồ thị không phải là thì thông báo lỗi sẽ được in ra.
Độ phức tạp
Ở hàm , ta mất độ phức tạp vì mỗi đỉnh chỉ được duyệt nhiều nhất lần và ta sẽ mất thêm độ phức tạp để duyệt tất cả các cạnh của đồ thị.
Cho đồ thị có hướng gồm đỉnh và cạnh. Các đỉnh được đánh số và với mỗi , cạnh có hướng thứ sẽ đi từ đỉnh đến đỉnh . không chứa bất kì chu trình có hướng nào !
Tìm độ dài lớn nhất của đường đi có hướng trong . Ở đây, độ dài của đường đi có hướng chính là số cạnh trong nó.
Input
Dòng thứ nhất chứa số nguyên .
dòng tiếp theo mỗi dòng chứa hai số nguyên (Ở đây các cặp phân biệt nhau và đề đảm bảo rằng, không chứa bất kì chu trình có hướng nào).
Output
In ra số nguyên duy nhất là độ dài lớn nhất của đường đi có hướng trong .
Sắp xếp Tô-pô có rất nhiều ứng dụng quan trọng, đặc biệt là áp dụng quy hoạch động trên mảng thứ tự Tô-pô.
Gọi là độ dài đường đi dài nhất bắt đầu từ đỉnh có chỉ số . Ta có công thức quy hoạch động trên danh sách Tô-pô như sau:
(Với và tồn tại cung từ ).
Theo định nghĩa của thứ tự Tô-pô, chỉ tồn tại các cung từ chỉ số nhỏ đến chỉ số lớn hơn. Nên khi ta tính toán đến thì chắc chắn đều đã được tính trước đó.
Vector revTopo - Danh sách nghịch đảo thứ tự Tô-pô.
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 7;
int n, m;
int visit[maxN], dp[maxN];
vector <int> g[maxN], revTopo;
void dfs(int u) {
visit[u] = 1;
for (auto v : g[u])
if (!visit[v]) dfs(v);
revTopo.push_back(u);
visit[u] = 2;
}
main() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
}
for (int i = 1; i <= n; ++i)
if (!visit[i]) dfs(i);
int ans = 0;
for (auto u : revTopo) {
for (auto v : g[u])
dp[u] = max(dp[u], dp[v] + 1);
ans = max(ans, dp[u]);
}
cout << ans;
}
Khi sắp xếp Tô-pô bằng , thuật toán sẽ trả ra danh sách nghịch đảo thứ tự Tô-pô(định nghĩa đã được viết ở mục Bài toán 1 phần Thuật toán 2). Mà ở công thức quy hoạch động, ta cần duyệt ngược lại danh sách, nên ta sẽ giữ nguyên thứ tự nghịch đảo đó và xử lí luôn trên nó.
Do đó, thay vì sử dụng ngăn xếp (stack) để đảo ngược lại danh sách. Ta sử dụng mảng động (vector)revTopo để lưu trữ lại thứ tự nghịch đảo Tô-pô đó.
Với đồ thị tổng quát, bài này sẽ trở thành bài toán .
Với , quy hoạch động trên thứ tự Tô-pô có thể giải được trong , kể cả với trọng số dương/âm, kể cả tìm đường đi ngắn nhất/dài nhất.
Fox Ciel sẽ xuất bản một bài báo trên FOCS (Foxes Operated Computer Systems - Fox). Cô ấy nghe thấy một tin đồn: danh sách tên các tác giả trên bài báo luôn được sắp xếp theo thứ tự từ điển.
Sau khi kiểm tra, cô phát hiện ra rằng đôi khi điều đó không đúng. Trên một số bài báo, tên của các tác giả không được sắp xếp theo tiêu chuẩn thông thường của thứ tự từ điển. Nhưng sau khi sửa đổi một số thứ tự của các chữ cái trong bảng chữ cái Latin thì thứ tự tên của các tác giả được sắp xếp đúng theo thứ tự từ điển mới.
Cô ấy muốn biết liệu có tồn tại thứ tự các chữ cái trong bảng chữ cái Latin sao cho các tên trên bài báo mà cô ấy định xuất bản được sắp xếp theo thứ tự từ điển hay không. Nếu có, bạn hãy giúp cô ấy tìm ra một thứ tự thỏa mãn bất kỳ.
Thứ tự từ điển được xác định theo cách sau: Khi so sánh xâu kí tự và , đầu tiên ta tìm vị trí ngoài cùng bên trái sao cho các ký tự khác nhau rồi so sánh các ký tự và theo thứ tự của chúng trong bảng chữ cái, nếu thì có thứ tự từ điển nhỏ hơn và ngược lại. Còn nếu không có vị trí như vậy (tức là là tiền tố của hoặc ngược lại) thì chuỗi ngắn hơn sẽ có thứ tự từ điển nhỏ hơn.
Input
Dòng đầu tiên chứa số nguyên dương là số lượng tên các tác giả.
dòng tiếp theo, mỗi dòng chứa một chuỗi kí tự gồm các chữ cái Latin in thường là tên của tác giả thứ . Tất cả tên của các tác giả đều khác nhau.
Output
Nếu tồn tại thứ tự các chữ cái mà các tên đã cho được sắp xếp theo thứ tự từ điển, hãy in ra bất kỳ thứ tự nào thỏa mãn là hoán vị của các ký tự (tức là, đầu tiên in ra chữ cái đầu tiên của bảng chữ cái đã sửa đổi, sau đó in ra chữ cái thứ hai, v.v.. ).
Giả sử, ta có hai xâu kí tự và . Theo định nghĩa của thứ tự từ điển, hãy xem xét xem nếu thì nó cho ta biết những dữ kiện gì.
Ví dụ: và . Để thì phải có thứ tự nhỏ hơn trong bảng chữ cái.
Nói cách khác, nó sẽ cho ta biết được kí tự nào sẽ phải đứng trước kí tự nào trong bảng chữ cái.
Do đó, ta có thể xây dựng một đồ thị với mỗi đỉnh tương ứng với kí tự ( ) và mỗi cạnh có hướng từ đỉnh tương ứng với kí tự phải có thứ tự nhỏ hơn đến đỉnh tương ứng với kí tự phải có thứ tự lớn hơn đỉnh kia.
Từ đó, ta có thể sử dụng thuật toán sắp xếp Tô-pô để tìm ra thứ tự chữ cái thỏa mãn.
Nếu đồ thị không phải là thì không tồn tại thứ tự chữ cái nào thỏa mãn.
Lưu ý trường hợp: Nếu đứng trước trong danh sách tên và là tiền tố của thì luôn luôn có thứ tự từ điển lớn hơn nên sẽ không tồn tại thứ tự chữ cái nào thỏa mãn.
#include <bits/stdc++.h>
using namespace std;
const int maxN = 110;
int n;
string s[maxN];
int visit[maxN];
vector <int> g[maxN];
stack <int> topo;
void printImpossible() {
cout << "Impossible";
exit(0);
}
// Sắp xếp Tô-pô bằng DFS
void dfs(int u) {
visit[u] = 1;
for (auto v : g[u]) {
if (visit[v] == 1) printImpossible();
if (!visit[v]) dfs(v);
}
topo.push(u);
visit[u] = 2;
}
// Xây dựng các cạnh của đồ thị
void solve(string x, string y) {
for (int i = 0; i < min(x.size(), y.size()); ++i)
if (x[i] != y[i]) {
g[x[i] - 'a'].push_back(y[i] - 'a');
return;
}
/* Trường hợp y là tiền tố của x => x luôn lớn hơn y
=> không có cách xếp thỏa mãn */
if (x.size() > y.size()) printImpossible();
}
main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> s[i];
if (i) solve(s[i - 1], s[i]);
}
for (int i = 0; i < 26; ++i)
if (!visit[i]) dfs(i);
while (!topo.empty()) {
cout << char(topo.top() + 'a');
topo.pop();
}
}
Để tối ưu độ phức tạp, với mỗi chuỗi kí tự ta không cần phải so sánh nó với tất cả các chuỗi còn lại. Mà ta chỉ cần so sánh chuỗi kí tự liên tiếp. Vì nó sẽ luôn đúng theo tính chất bắc cầu: Nếu và thì .
Độ phức tạp
Ở vòng for đầu tiên để xây dựng các cạnh của đồ thị, ta mất độ phức tạp .
Ở vòng for thứ hai để xác định thứ tự Tô-pô, ta mất độ phức tạp . Với là số cạnh của đồ thị. Trong trường hợp xấu nhất, với mỗi cặp kí tự liên tiếp đều tạo ra cạnh thì số lượng cạnh lớn nhất có thể tạo ra là cạnh.