Назад Края в глубине первого дерева поиска графа
У меня есть домашнее задание, которое я выполнил, и около 3 баллов из 100 относятся к следующему вопросу.
"Предположим, вы строите дерево DFS на ориентированном графе. После этого вы замечаете, что задних граней нет. Что это говорит о графе?"
Я подумал об этом, и все, что я могу рассуждать, это то, что существует подразумеваемая зависимость, так что существует только один конкретный путь для топологического прохождения по графу. К сожалению, я не смог найти никакой информации об этом где-либо в Интернете, поэтому я решил опубликовать здесь свой ответ и посмотреть, сможет ли кто-нибудь оценить его (не) правильность. Пожалуйста, дайте мне знать, если у вас есть какие-либо дополнительные мысли или указатели, которые могут помочь мне с этой проблемой.
Огромное спасибо!
2 ответа
В любом ориентированном графе, если DFS не сообщает обратные ребра, то у графа нет циклов.
Возможно, есть более нюансированный ответ, но я сразу же подумал, что это означает, что на графике нет циклов.