DFS занимает время, пропорциональное количеству ребер, достижимых из каждого узла, что потенциально равно O (E), поэтому DFS для каждого узла - это O (VE), где V - количество вершин, а E - количество ребер. , Предполагая, что средний граф имеет O (V ^ 2) ребер, это O (V ^ 3) в среднем и худшем случаях. В лучшем случае повторяющаяся DFS требует времени O (V) на графе без ребер.
Один простой способ добиться большего успеха - по крайней мере в теории - это взять матрицу смежности A, запишите 1с по диагонали, чтобы каждый узел был доступен из себя, найдите и / или матричную степень A ^ (V-1), а затем посчитайте число 1с в каждой строке. Временная сложность этого подхода составляет:
- O (V ^ 2) для построения матрицы смежности,
- O (f (V) * log V) для вычисления мощности матрицы используя алгоритм квадрата и умножения для умножения матрицы V на лог, где f (V) - сложность алгоритма умножения матриц,
- O (V ^ 2) для подсчета 1 в каждой строке результата.
временная сложность умножения матриц может быть не более O (n ^ 2.373) в зависимости от используемого вами алгоритма, поэтому Общая сложность приведенного выше алгоритма составляет около O (V ^ 2.373 log V). Это превосходит повторную DFS в среднем и наихудшем случаях, но не в лучшем.
Тем не менее, этот ответ является чисто теоретическим, поскольку алгоритмы умножения матриц, которые достигают низких временных сложностей, обычно имеют довольно большие постоянные коэффициенты , так что они на самом деле не быстрее для матриц разумных размеров. Это также, вероятно, не лучшее, что вы можете сделать; но он отвечает на экзистенциальный вопрос «есть ли что-то более эффективное?».