Сколько различных DFS и BFS мы можем сделать из графа? у DFS больше разнообразия или у BFS?

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

Спасибо


graph breadth-first-search depth-first-search
person Sam Farjamirad    schedule 16.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Возможно, сложности отвечают на ваш вопрос

Поиск в глубину

Производительность в худшем случае O(|E|) для явных графов, пройденных без повторений, O(b^{d}) для неявных графов с коэффициентом ветвления b, просматриваемых до глубины d.

Сложность пространства в наихудшем случае O(|V|), если весь граф проходится без повторений, O(самая длинная длина пути) для неявных графов без исключения повторяющихся узлов

&

Поиск в ширину

Производительность в худшем случае O(|E|)=O(b^{d})

Пространственная сложность в худшем случае O(|V|)=O(b^{d})

person Mavromatos Alexandros    schedule 03.06.2016