DFS в DFS, DFS с известной строкой

Question

Я ищу вычисления сложности моего кода. Это просто DFS (поиск по глубине в DFS). DFS работает на графике (конечный автомат) от конца до начала (обратный поиск). Всякий раз, когда он достигает начала, он накапливает строку, которая заставляла ее запускаться, и пытается эту строку на другом графике с другой DFS, чтобы проверить, достигает ли она и начало состояния на другом графике с той же строкой.

Внешняя сложность DFS определенно O (Vo + Eo), где Vo: число вершин во внешнем графе и Eo: количество ребер во внешнем графе. Но какова сложность внутри DFS, когда известна строка, которая будет следовать?

И если возможно, можете ли вы также ответить на всю сложность алгоритма?

Я не уверен, является ли это O ((Ео + Vo) + (Ei + Vi)) или O ((Ео + Vo) (Ei + Vi)) или smtg .else

Спасибо advance,

Answer 1

Это зависит от того, что вы делаете в случае неудачи второй DFS. В противном случае я хочу сказать, что второй граф не содержит строку, найденную в первой DFS.

Если второй отказ DFS означает, что вы возвращаетесь назад и выполняете поиск другой строки в первой DFS, а затем повторите попытку второй DFS, тогда ваша сложность O((Eo+Vo)*(Ei+Vi)), потому что вы можете в худшем случае выполнить полную DFS второго графика для каждый путь DFS к стартовому узлу в первой DFS.

Если второй отказ DFS означает, что вы остановились, вы в худшем случае выполните одиночную DFS первого графика и одну DFS второго графика, дающую вам худшую сложность O((Eo+Vo)+(Ei+Vi)).

Тот факт, что вы являетесь DFS, чтобы проверить, содержит ли граф строку, означает, что в некоторых случаях вы можете рано или поздно завершить свою DFS (например, вы достигнете вершины без запуска, не оставив никаких символов для проверки). Однако, сможете ли вы закончить раннее, полностью зависит от структуры графика, поэтому я бы сказал, что вторая DFS находится в худшем случае O(Ei+Vi), потому что с неприятным графиком вы все равно можете пройтись по всем краям и всем вершины.