Находить сильно связанные компоненты?
Моя книга определяет метод нахождения сильно связанных компонент ориентированного графа за линейное время. Кроме того, несколько других алгоритмов для поиска сильно связанных компонентов (например, алгоритм Тарьяна) также могут находить компоненты за линейное время.
Однако все эти алгоритмы требуют, чтобы вершины графа были упорядочены по убыванию пост- значений (время, когда вершина остается). Обычные алгоритмы упорядочения, такие как Mergesort, занимают O(n log n) времени.
Следовательно, как этим алгоритмам удается завершить поиск сильно связанных компонентов за линейное время, если упорядочение списка вершин по почтовым значениям занимает O(n log n) времени?
1 ответ
Поскольку "время" (вид, по которому измеряются пост-значения) монотонно не уменьшается как функция времени (количество шагов, выполненных программой поиска в глубину), достаточно добавить каждый узел в список сразу после обход оставляет это. В конце обхода список упорядочен.
В качестве альтернативы, поскольку почтовые значения представляют собой целые числа, ограниченные сверху полиномиально, на некоторых моделях машин их можно отсортировать за линейное время, используя, например, сортировку по основанию.