Топологический вид матрицы смежности

Question

Учитывая график, представленный в виде матрицы смежности, как я могу выполнить топологическую сортировку по линейному времени? Даже если я сделаю препроцессор для создания массива значений в градусах, это будет с временной сложностью O (| V | ^ 2). Я знаю, что для топологической сортировки из матрицы можно создать алгоритм линейного времени, так что мне не хватает?

Answer 1

Как отметил в комментариях дюха, «линейное время» - это термин, который зависит от размера ввода. Так, например, метод пробное деление для проверки, является ли число простым прогоном не более n ^ (0,5) итераций, но входной размер равен log (n), поэтому сложность по времени будет 2 ^ (n/2).

В этом случае матрица смежности занимает пространство O (k) = O (| V | ^ 2), вы можете применить алгоритм Кана и получить линейное время, учитывая нахождениевсе вершины без входящих ребер путем итерации матрицы занимают O (k) времени, а обход всех ребер данной вершины занимает O (k ^ 0,5).

Если вы предполагали, существует ли алгоритмНаходя топологическую сортировку в O (| V |), я думаю, что любой алгоритм, по крайней мере, должен пройти по всем ребрам, так что это может быть нижней границей.