Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Собственно вопросы: 1. Какова сложность обхода графа в глубину? 2. Можно ли реализовать обход в ширину, не используя очередь?
StopCry
Re: 2 небольших вопроса, по обходам графов
28.04.2013, 18:42
Нашел сложность для обхода в глубину Где n- кол-во вершин, а m - среднее кол-во ребер выходящих из каждой вершины. И если я правильно понял, то в худшем случае (не рассматриваю мультиграф), это превратится в , я прав или что-то не допонял?
Ой где такие глупости пишут?? На самом деле и поиск в глубину и поиск в ширину имеют оценку или , где E количество ребер.
StopCry
Re: 2 небольших вопроса, по обходам графов
29.04.2013, 12:18
То что у обхода в ширину и глубину одинаковая сложность, является достаточно очевидным фактом (у них просто порядок просмотра меняется, не более). Если сложность , то это обход в глубину из 1й вершины, верно? А если мне нужно им пройтись из каждой, то сложность перерастает в ?