Я пытаюсь выяснить, сколько различных деревьев BFS и DFS можно построить из заданного графика, если это невозможно точно определить, тогда я хочу знать, имеет ли DFS больше разнообразия, чем BFS, все они связаны к данному графику!Сколько разных DFS и BFS можно сделать из графика? показать DFS больше разнообразия или BFS?
Спасибо
Возможно, сложность ответа на вопрос
Поиск в глубину
Худшая производительность случай O (| E |) для явного графики проходится без повторения, O (b^{d}) для неявных графов с коэффициентом ветвления b, искаженным до глубины d.
В худшем случае пространство сложность O (| V |), если весь граф пройден без повторения, O (длинная длина пути поисков) для неявных графов без устранения дублирующих узлов
&
поиск в ширину
Наихудший производительность O (| E |) = О (Ь {д})
В худшем случае пространство сложность O (| V |) = О (Ь {д})