Тарьян Алгоритм ТПС худший случай анализа

Question

я читал бумаги Donal B .Johnson для нахождения всех элементарных цепей в ориентированном графе, http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

В этой статье он отметил, что наихудший случай для Тарьян алгоритма O (V * Е (c + 1)) Хотя везде, где это показано как O (V + E), бумага Джонсона взяла пару примеров, чтобы доказать эту точку, как показано на рис. 1 и 2 на бумаге.

Пример 2, который довольно схож, после нахождения первого цикла 1 ... k в O (k) времени, теперь, согласно моему пониманию, все остальные вершины просто вернутся, поскольку их индекс уже определен, и он должен принять другое k-время для k вершин, поэтому для подброса оно должно 2k раз вместо k ** 2, я пропустил какой-то момент здесь?

Пожалуйста, предложите с некоторыми, например, Спасибо

Answer 1

«Алгоритм Tarján» является в данном случае не алгоритм для сильно связанных компонентов. Это его алгоритм для перечисления элементарных схем. Однако в the original paper этот метод отмечен как имеющий плотный наихудший случай O ((V + E) * (C + 1)) времени. Интересно отметить, что аргумент, который Тарьян использует для доказательства этой привязки (время O (V + E) между нахождением двух схем), внезапно изменяется в работе Джонсона (время O (V * E) между нахождением двух схем). Я не знаком ни с одним из этих алгоритмов, поэтому не могу сказать, какой из них правильный. Быстрый поиск, по-видимому, считает алгоритм Джонсона асимптотически более быстрым (хотя оба метода претендуют на одинаковые временные сложности), но нигде я не мог найти источник, который опровергает сложность времени в работе Тарьяна.