Поиск в ширину (BFS)
Вставка
- Опубліковано 25 бер 2023
- Плейлист по кратчайшим путям в графах: • Кратчайшие пути в графах
Это видео записывалось как часть онлайн-курса, которому, увы, уже не суждено увидеть свет. Тем не менее, мы опубликуем его материалы, так как они могут оказаться полезными при изучении соответствующих тем.
Спасибо. Очень качественная подача информации, всё по делу, ничего лишнего. Браво.
Спасибо за все видео, очень доступно объясняете, пожалуйста, не останавливайтесь, если есть такая возможность:)
Спасибо большое за объяснение!Хорошо и понятно!
Спасибо за объяснение, все было понятно :)
Огромное спасибо за видео
Столько раз пытался понять bfs и не получалось, спасибо
большое спасибо
очень выручило
АПО?
@@legenda7830 что?
ну, видимо нет
Отличное видео, спасибо большое! Единственный момент - не очень согласен с тем, что BFS не может обнаруживать циклы, ведь если при анализе вершин, смежных с текущей вершиной мы обнаруживаем, что смежная вершина уже посещена или обработана и, в случае неориентированных графов, не является непосредственным предком, то мы как раз обнаружили цикл
Вы правы, однако всё же чаще встречаются задачи, где требуется найти цикл в графе с ориентированными рёбрами. Здесь поиск в ширину далеко не всегда сможет помочь.
@@op_ulstuа разве порядок обхода в нерекурсивном дфс не полечится, если я буду помечать вершину при pop? А не перед пуш
@@oanovitskij Да, но тогда одни и те же вершины будут складываться в стек несколько раз (эта проблема упомянута на 7:25), так что придётся добавить условие, чтобы не обрабатывать повторы.
@@op_ulstu нашел на стаковерфлоу следующую реализацию на псевдокоде, но с тремя цветами. Она аналогично неверно обходит граф? Нет ли ссылки на верный алгоритм?
Кстати, видео топ и по дфс и по итеративным и по бин поиску. не хватает таких на степике)
Algorithm Non-Recursive-DFS(G)
-----------------------------------------------------------------------------------
1 for each vertex u ∈ G.V
2 u.color ← WHITE
3 u.π ← NIL
4 time = 0
5 for each vertex u ∈ G.V
6 if u.color = WHITE
7 u.color ← GRAY
8 time ← time + 1
9 u.d ← time
7 push(u, S)
8 while stack S not empty
9 u ← pop(S)
10 for each vertex v ∈ G.Adj[u]
11 if v.color = WHITE
12 v.color = GRAY
13 time ← time + 1
14 v.d ← time
15 v.π ← u
16 push(v, S)
17 u.color ← BLACK
18 time ← time + 1
19 u.f ← time
я вообще не понимаю вот эти обходы. Теорию и реализацию. Можете кто нибудь легко обьяснить для меня?
Смотри другие видео, прогоняй код в дебагере, в итоге со временем точно поймешь. И если уж ты взялся за алгоритмы, то приготовься к тому, что просто тут не будет
@@miron5733 iam not Russian, could you recommend similar russian resources like this great one ?
😨😓💩🤡👌🏿🤛🏿💁🏿