Сложность поиска всех простых путей с использованием поиска в глубину?

Спасибо всем, кто отвечает идеями и альтернативными решениями. Всегда приветствуются более эффективные способы решения проблем, а также напоминания о моих предположениях. Тем не менее, я бы хотел, чтобы вы на мгновение проигнорировали проблему, которую я пытаюсь решить с помощью алгоритма, и просто помогли мне проанализировать сложность моего алгоритма, о которой я писал, - все простые пути. на графике с использованием глубинного поиска, как описаноВоти реализованоВот, Спасибо!

Изменить: Это домашнее задание, но я уже отправил это задание, и я просто хотел бы знать, если мой ответ правильный. Я немного запутался из-за сложности Big-O, когда речь идет о рекурсии.

Оригинальный вопрос ниже:

Я пытаюсь найти сложность поиска по всем путям, как указаноэто алгоритм. Учитывая две вершины, я нахожу все простые пути между ними, используя поиск в глубину.

Я знаю, что временная сложность DFS - это O (V + E), а его пространственная сложность - O (V), и моя интуиция заключается в том, что сложность поиска по всем путям будет больше, но я не могу определите что это будет.

Смежные вопросыВот а такжеВот.

Обновление (в ответ на комментарий ниже):

Я пытаюсь решитьшесть градусов Кевина Бэкона проблема. Обычно для этого требуется найти самую низкую степень разделения между парой актеров, но мне нужно найти ВСЕ степени разделения (на данный момент менее 6, но это может измениться).

Ответы на вопрос(4)

Ваш ответ на вопрос