6
Hãy xem xét các thuật toán sau đây để loại topo được đưa ra trong sách giáo khoa của tôi:tôpô Sắp xếp
Input: A digraph G with n vertices
Output: A topological ordering v1,v2...vn of G, or the non-existence thereof.
S is an empty stack
for each vertex u in G do
incount(u) = indeg(u)
if incount(u) == 0 then
S.push(u)
i = 1
while S is non-empty do
u = S.pop()
set u as the i-th vertex vi
i ++
for each vertex w forming the directed edge (u,w) do
incount(w) --
if incount(w) == 0 then
S.push(w)
if S is empty then
return "G has a dicycle"
tôi đã cố gắng thực hiện các thuật toán word-cho-word nhưng thấy rằng nó luôn luôn phàn nàn của một dicycle, cho dù đồ thị là acyclic hoặc không phải. Sau đó, tôi phát hiện ra rằng 2 dòng cuối không phù hợp chính xác. Vòng lặp while ngay trước khi nó thoát khi S rỗng. Vì vậy, mỗi lần, nó được đảm bảo rằng nếu điều kiện sẽ giữ đúng sự thật.
Làm cách nào để tôi có thể sửa thuật toán này để kiểm tra xe đạp đúng cách?
Edit:
Hiện nay, tôi chỉ đơn giản là ván vấn đề S, bằng cách kiểm tra giá trị của i ở cuối:
if i != n + 1
return "G has a dicycle"