2 небольших вопроса, по обходам графов

[StopCry]

Собственно вопросы:
1. Какова сложность обхода графа в глубину?
2. Можно ли реализовать обход в ширину, не используя очередь?

[StopCry]

Нашел сложность для обхода в глубину $O(n^m)$
Где n- кол-во вершин, а m - среднее кол-во ребер выходящих из каждой вершины.
И если я правильно понял, то в худшем случае (не рассматриваю мультиграф), это превратится в $O(n^{n-1})$, я прав или что-то не допонял?

[Pavlovsky]

StopCry в сообщении #716899 писал(а):

Нашел сложность для обхода в глубину $O(n^m)$

Ой где такие глупости пишут?? На самом деле и поиск в глубину и поиск в ширину имеют оценку $O(n^2)$ или $O(E)$, где E количество ребер.

[StopCry]

То что у обхода в ширину и глубину одинаковая сложность, является достаточно очевидным фактом (у них просто порядок просмотра меняется, не более).
Если сложность $O(E)$, то это обход в глубину из 1й вершины, верно? А если мне нужно им пройтись из каждой, то сложность перерастает в $O(n\cdot E)$?