Печатный (не обнаруживающий) цикл с топологической сортировкой

Question

Это вопрос в 3-м издании «Анализ структур данных и алгоритмов», который также задавался на одном из наших экзаменов. Запишите алгоритм для топологической сортировки графа, представленного списком смежности, модифицированный такой, что алгоритм выводит цикл, если он найден. Сначала объясните свою идею в нескольких приговоры. (Не используйте глубинный поиск в первую очередь, мы хотим просто модифицировать базовую топологию сортировки.)

И ответ таков: Если ни одна вершина не имеет степени 0, мы можем найти цикл, проследив назад вершины с помощью положительная степень; так как каждая вершина на трассе имеет положительную степень, мы в конечном итоге достичь вершины дважды, и цикл найден.

Я не понял, что такое обратная трассировка. Что означает «обратная связь», и мне интересно, как будет выглядеть псевдокод этого ответа? Цени любую помощь.

Answer 1

Алгоритм Канса работает, выбирая узел с степенью 0 и удаляя все его исходящие ребра (что может привести к появлению новых узлов с степенью 0).Если больше нет узлов с нулевой степенью 0 (и график сейчас не пуст), он содержит цикл.

Чтобы напечатать цикл, начните с любого места и следуйте за входящими ребрами.Поскольку существует конечное число узлов, в какой-то момент вы должны достичь узла во второй раз.Это ваш цикл, чтобы напечатать его, просто запустите его в другой раз.

Скажем, наш график:

a --> b
b --> c, d
c --> b

инверсия этого графика тогда равна

a <-- 
b <-- a, c
c <-- b
d <-- b

Топологическая сортировка начинается с a, удаляет ее.b сейчас равно b <-- c

Теперь мы начинаем где угодно, скажем, d и ищем в обратном направлении.

d <-- b <-- c <-- b

Поскольку мы видели b ранее, это должно бытьчасть цикла.Для печати мы снова переходим по ссылкам и получаем b <-- c <-- b.

Если бы был какой-либо тупик, такой как a, он был бы удален алгоритмом топологической сортировки уже до обнаружения цикла.