Выбор ответа Senior Графы: BFS и DFS обновлено
Цикл в ориентированном графе
Вопрос
Ищем цикл в ориентированном графе DFS-ом. Почему одного множества visited мало?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Повторный заход бывает без цикла; нужны три цвета состояния. В графе A→B, A→C, C→B вершина B встретится дважды, но цикла нет.
Варианты ответа
- Хватает, если граф связный: повторный заход тогда всегда означает цикл
- Нужно ещё множество пройденных рёбер, повтор ребра и есть цикл
- В ориентированных графах циклов не бывает, проверка не нужна
- Повторный заход бывает без цикла; нужны три цвета состоянияправильный ответ
Разбор
В графе A→B, A→C, C→B вершина B встретится дважды, но цикла нет. Цикл есть, только если ребро ведёт в вершину, которая сейчас на стеке DFS (серую). Поэтому храним состояния: белая, серая, чёрная. O(V + E).
- Связность не исправляет ложное срабатывание.
- Множество рёбер не различает «в пути» и «завершена».
- Циклы в ориентированных графах бывают, например A→B→A.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.