Поиск в глубину (DFS)

Плейлист по графам и DFS: • Графы. Поиск в глубину...
Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.

[@user-my6zq6tm2r]

"Входим в каждого соседа" спасибо вам я довел до смеха учителя по дискретной математике

[@user-mx9rg9gg7y]

эти 9 видеоуроков наиболее лучше объясняют графы и алгоритмы , чем остальные в русскоязычном сегменте

[@user-et7fq1mw5j]

О Великий Человек, я буду боготворить тебя до конца своей жизни. Вы объяснили мне, то что я искал несколько дней, за пять минут

[@voolfigg3395]

Согласен

[@maksimboiko007]

Гениально. Наконец-то кто-то смог это мне объяснить, наглядно, спасибо!

[@sorrelofsuccess5513]

Спасибо, понятно. Для обычных деревья идея примерно такая же будет?

[@op_ulstu]

В целом - да. Полезно знать, что при обходе деревьев не обязательно использовать массив visited, достаточно хранить номер вершины - предка (parent). Тогда вместо !visited[to] достаточно проверять to != parent.

[@user-nt7lj6eu6b]

Спасибо за видео. Возник вопрос, почему есть утверждение, что при использовании матрицы смежности асимптотика алгоритма равняется O(V**2), - я понимаю вашу логику, что проверок условий действительно будет больше, но ведь самих запусков dfs - столько же, ведь у нас в условии IF фигуририрует visited, который мы обновляем на предыдущуих вызовах рекурсии

[@op_ulstu]

Проверка, существует ли ребро между вершинами a и b, - не бесплатная операция. Представьте себе запуск DFS на пустом графе из 1000 вершин. Если граф был сохранён в виде списков смежности, то после запуска DFS от каждой вершины мы сразу делаем вывод, что у неё нет соседей, так как соответствующий список смежности пуст; в цикл for мы даже не входим. Итого O(1) на обработку каждой вершины и общая сложность O(V) для запусков от всех вершин. Если граф был сохранён в виде матрицы смежности, после запуска от любой вершины алгоритму придётся просмотреть 1000 ячеек соответствующей строки матрицы, чтобы понять, что там всюду нули и соседних вершин нет. Итого O(V) на обработку каждой вершины и общая сложность O(V^2).

[@dctSPOMMY]

только если ты visited хранишь не как глобальную переменную, то из 4ки ты спокойно сможешь пойти в 5ку, т. к. на том этапе рекурсии в visited еще не было 5. тоже самое и с 6кой

[@op_ulstu]

Амперсанд в параметре vector &visited говорит о том, что этот массив передаётся в функцию dfs по ссылке. Следовательно, все изменения, произошедшие на более глубоких этажах рекурсии, останутся видны после возвращения на более высокие этажи. Поэтому массив visited не обязательно было делать глобальным. Вообще, чем меньше в программе глобальных переменных - тем лучше.