Mọi người cho e hỏi thuật toán topo sort có ứng dụng gì trong đồ thị ạ. Em tra gg mà em cảm thấy mông lung khó hiểu về thuật toán này ạ. Em xin cảm ơn ạ.
Thuật toán topo sort
Topo sort của một đồ thị có hướng là một thứ tự tuyến tính của các đỉnh, sao cho với mỗi cạnh uv đi từ đỉnh u tới đỉnh v, thì u luôn đứng trước v trong thứ tự topo sort.
Ứng dụng đơn giản nhất của nó trong thực tế là khi cậu lập lịch. Sau khi cậu có 1 đồ thị có hướng, với 1 cạnh uv đi từ đỉnh u tới đỉnh v, có nghĩa là task u cần hoàn thành trước task v, thứ tự topo của đồ thị này cho cậu biết thứ tự hoàn thành của công việc, khi các task bị phụ thuộc vào task khác luôn ở sau task mà nó phụ thuộc.
Trong đồ thị, cậu cũng có thể ứng dụng nó trong bài toán tìm đường đi ngắn nhất trên đồ thị có hướng.
See also:
https://en.m.wikipedia.org/wiki/Topological_sorting (tất cả những gì tớ liệt kê ở trên được tham chiếu từ đây).
6 Likes
ví dụ 1 ứng dụng như là build các thư viện trong C++ ấy, hay thứ tự install các thư viện trong Python chẳng hạn. Thư viện A phụ thuộc thư viện B, B phụ thuộc C, D, vậy phải build/install C,D hoặc D,C trước, rồi tới B, rồi tới A. Ví dụ trong vcpkg thì thư viện SFML phụ thuộc thế này: (gõ vcpkg depend-info sfml là ra)
vcpkg-cmake:
vcpkg-cmake-config:
zlib:
brotli:
bzip2:
libogg:
libpng: vcpkg-cmake, vcpkg-cmake-config, zlib
freetype[brotli, bzip2, zlib, png]: brotli, bzip2, libpng, zlib
libflac: libogg
libvorbis: libogg
openal-soft:
stb:
sfml: freetype, libflac, libogg, libvorbis, openal-soft, stb
nghĩa là sfml phụ thuộc freetype, libflac, libogg, libvorbis, openal-soft, stb. freetype lại phụ thuộc tiếp libpng, libpng lại phụ thuộc tiếp zlib v.v…
đồ thị nó thế này:
muốn biết cần build thư viện nào trước thì phải xài topo sort trên đồ thị này :V
hay ví dụ đồ thị lệ thuộc của qt5:
boost thì bự quá ko chèn nổi ảnh 
ngay cả việc vẽ hình đồ thị này nó cũng đã thực hiện topo sort rồi đấy :V
5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?