Опитвам се да разбера колко различни BFS и DFS дървета мога да конструирам от дадена графика, ако това е невъзможно да се определи точно, тогава искам да знам дали DFS има повече разнообразие от BFS, сигурен съм, че всички те са свързани с дадена графика!
Благодаря ти
Може би сложността отговаря на въпроса ви
Търсене в дълбочина
Ефективност в най-лошия случай O(|E|) за явни графики, преминати без повторение, O(b^{d}) за неявни графики с коефициент на разклоняване b, претърсен до дълбочина d.
Сложност на пространството в най-лошия случай O(|V|), ако целият график е преминат без повторения, O(най-дългата търсена дължина на пътя) за имплицитни графики без елиминиране на дублиращи се възли
и
Търсене в широчината
Ефективност в най-лош случай O(|E|)=O(b^{d})
Сложност на пространството в най-лошия случай O(|V|)=O(b^{d})
