Алгоритм линейного времени, который берет прямой граф и возвращает количество вершин - PullRequest
1 голос
/ 17 февраля 2011

как вы могли бы описать алгоритм линейного времени, который принимает ориентированный граф в качестве входных данных и возвращает количество вершин, которые могут быть достигнуты из любой другой вершины.Я знаю, что алгоритм будет занимать линейное время, но почему.а также почему это должно быть (O (V2) в матрице смежности; O (E + V) в списке смежности).

1 Ответ

2 голосов
/ 18 февраля 2011

Проверьте Алгоритм Косараю .Вы должны быть в состоянии определить, почему время выполнения соответствует алгоритму.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...