Отличное видео, спасибо большое! Единственный момент - не очень согласен с тем, что BFS не может обнаруживать циклы, ведь если при анализе вершин, смежных с текущей вершиной мы обнаруживаем, что смежная вершина уже посещена или обработана и, в случае неориентированных графов, не является непосредственным предком, то мы как раз обнаружили цикл
Вы правы, однако всё же чаще встречаются задачи, где требуется найти цикл в графе с ориентированными рёбрами. Здесь поиск в ширину далеко не всегда сможет помочь.
@@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
Смотри другие видео, прогоняй код в дебагере, в итоге со временем точно поймешь. И если уж ты взялся за алгоритмы, то приготовься к тому, что просто тут не будет
Спасибо. Очень качественная подача информации, всё по делу, ничего лишнего. Браво.
Спасибо за все видео, очень доступно объясняете, пожалуйста, не останавливайтесь, если есть такая возможность:)
Спасибо большое за объяснение!Хорошо и понятно!
Спасибо за объяснение, все было понятно :)
Огромное спасибо за видео
Столько раз пытался понять 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 ?
ошибка сегментации
😨😓💩🤡👌🏿🤛🏿💁🏿
Очень плохо