DFS - сравнение времени и сложности двух связанных графов
Представьте себе следующий граф (это не настоящий граф), верхний уровень которого представляет собой ациклический ориентированный граф с узлами n, а нижний уровень представляет собой ациклический ориентированный граф с узлами m. Каждый узел верхнего уровня связан с несколькими узлами нижнего уровня (скажем, каждый узел верхнего уровня покрывает несколько узлов нижнего уровня). Итак, n меньше, чем m (каждый узел верхнего уровня покрывает как минимум 2 узла нижнего уровня).
Мои вопросы:
1- Каковы временные и пространственные сложности при использовании алгоритма depth-first search для поиска всех последовательностей из определенного узла на верхнем и нижнем уровнях? и как можно сравнить эту пространственно-временную сложность двух уровней (как они связаны)?
Мой ответ относительно сложности времени и пространства, к которому я подозреваю, следующий:
- Верхний уровень: временная сложность: o (n), пространственная сложность: o (n + e) (e: количество ребер).
- Нижний уровень: временная сложность: o (m), пространственная сложность: o (m + e) (e: количество ребер).
Но я не могу найти отношения между этими двумя.
2- Если мы хотим найти все возможные последовательности из одного узла на нижнем уровне графа, если к этому графу будет добавлен дополнительный узел, как увеличится количество последовательностей (для наихудшего сценария)?
Любая идея приветствуется!
Начиная с нижнего уровня, верхний уровень никогда не может быть достигнут, поэтому достижимый размер графа составляет m вершин и e_lower ребер. Тогда сложность обхода DFS равна стандартной сложности DFS для графа такого размера (т.е. временная сложность O (m + e_lower) и пространственная сложность O (m). Что касается вопроса 2), мне не ясно, что вы имеете в виду. "всеми возможными последовательностями" и каково точное значение "добавления узла" (т.е. будет ли узел изолирован, или он будет присоединен к существующему графу ребрами? Если да, сколько ребер и т. д.).
Мне не совсем понятно, о чем вы просите. Вы спрашиваете о временной / пространственной сложности выполнения полного обхода DFS, начиная с вершины на верхнем уровне, а не начиная с вершины на нижнем уровне? При запуске в верхнем слое размер графа получается сложением числа вершин и ребер в верхнем и нижнем слое. Тогда временная / пространственная сложность равна стандартная сложность DFS для графа такого размера (то есть временная сложность O (n + m + e_upper + e_lower) и пространственная сложность O (n + m)).