Cho đồ thị có hướng G = (V, E) trong đó tập đỉnh V = {1,2,3,4,5,6} và tập cung E = {(1,6),(2,1),(2,5),(2,6),(3,1),(3,2),(5,4),(5,6),(6,4)}. Thứ tự các đỉnh trong sắp xếp TOPO trên G là thứ tự nào sau đây?

Sắp xếp topo là một thứ tự tuyến tính của các đỉnh trong đồ thị có hướng không chu trình (DAG) sao cho với mọi cung (u, v) trong đồ thị, đỉnh u đứng trước đỉnh v trong thứ tự đó. Một đồ thị có chu trình thì không có thứ tự topo.

Để tìm thứ tự topo của đồ thị đã cho, ta có thể sử dụng thuật toán duyệt đồ thị theo chiều sâu (DFS) kết hợp với việc đánh dấu các đỉnh đã được thăm và các đỉnh đã hoàn thành.

Trong đồ thị G = (V, E) với V = {1, 2, 3, 4, 5, 6} và E = {(1, 6), (2, 1), (2, 5), (2, 6), (3, 1), (3, 2), (5, 4), (5, 6), (6, 4)}:

- Đỉnh 3 không có cung vào, có thể là đỉnh bắt đầu.

- Từ 3 có các cung đến 1 và 2.

- Từ 2 có các cung đến 1, 5, 6.

- Từ 1 có cung đến 6.

- Từ 5 có các cung đến 4 và 6.

- Từ 6 có cung đến 4.

Duyệt theo DFS:

- Bắt đầu từ đỉnh 3.

- Thăm 3, sau đó thăm 1 (vì 3 -> 1).

- Thăm 1, sau đó thăm 6 (vì 1 -> 6).

- Thăm 6, sau đó thăm 4 (vì 6 -> 4).

- Thăm 4 (đã hoàn thành).

- Quay lại 6 (đã hoàn thành).

- Quay lại 1 (đã hoàn thành).

- Quay lại 3, thăm 2 (vì 3 -> 2).

- Thăm 2, sau đó thăm 5 (vì 2 -> 5).

- Thăm 5, sau đó thăm 4 (đã thăm rồi) và 6 (đã thăm rồi).

- 5 hoàn thành.

- 2 hoàn thành.

- 3 hoàn thành.

Như vậy, một thứ tự topo hợp lệ là: 3, 2, 1, 5, 6, 4.