Поиск сильно связанных компонентов?

Question

В моей книге определен метод поиска сильно связанных компонент ориентированного графа в линейном времени. Кроме того, несколько других алгоритмов для поиска сильно связанных компонентов (т. Е. Алгоритма Тарьяна) также могут находить компоненты в линейном времени.

Однако все эти алгоритмы требуют, чтобы вершины графа упорядочивались при уменьшении post значения (время, когда вершина оставлена). Общие алгоритмы упорядочения, такие как Mergesort, берут O (n log n).

Поэтому как эти алгоритмы управления для завершения размещения на сильно связные компоненты в линейное время, при заказе списка вершин на посте значения принимает O (N журнал п)?

Answer 1

Поскольку «время» (вид, по которому измеряются значения столбца), монотонно неустранимо как функция времени (количество шагов, выполняемых программой поиска по глубине), достаточно добавить каждый узел к список сразу же после его обхода. В конце обхода список сортируется в порядке сортировки.

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