Рассмотрим следующий алгоритм топологической сортировки, приведенный в моем учебнике:
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"
Я пытался реализовать алгоритм дословно, но обнаружил, что он всегда жаловался на цикл, независимо от того, был ли график ациклическимне.Затем я обнаружил, что последние 2 строки не соответствуют правильно.Цикл while непосредственно перед ним завершается, когда S пусто.Таким образом, каждый раз гарантируется, что условие if будет выполнено.
Как я могу исправить этот алгоритм, чтобы правильно проверить наличие велосипеда?
Редактировать:
В настоящее время я просто обхожу проблему S, проверяя значение i в конце:
if i != n + 1
return "G has a dicycle"