2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: 2 небольших вопроса, по обходам графов
Сообщение29.04.2013, 10:27 
Аватара пользователя
StopCry в сообщении #716899 писал(а):
Нашел сложность для обхода в глубину $O(n^m)$


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

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group