Я читал, что есть способы определить все достижимые пары, используя Сильно Связанные Компоненты. Но я хочу вычислить все достижимые узлы на лету - поэтому мне не нужно хранить массивную матрицу достижимости в оперативной памяти. Какая временная сложность была бы возможна для алгоритма для вычисления всех достижимых узлов в ориентированном графе из одного узла?
Вот наивный алгоритм, который я придумал, я не уверен во временной сложности этого. $ O (n!) $?
Кажется, он имеет пространственную сложность $ O (n) $.
Я читал об алгоритме Беллмана-Форда с временной сложностью $ O (EV) $, который по существу является $ O (V ^ 3) $, и алгоритм Флойда-Варшалла, который является $ O (V ^ 3) $. Они требуют пространственной сложности $ O (V) $ и $ O (V ^ 2) $ соответственно.
Проблема в том, что только входные данные могут быть определены в постоянное время. Таким образом, нужно было бы найти (за $ O (n) $ время) все выходные данные для конкретного нейрона. Что я на самом деле сделал в своем решении, так это инвертировал график, используя аналогичную технику, перед запуском DFS. Но я не знаю, является ли это оптимальным ...