В 2008 обсуждалась эта тема, но уже закрыта.
Вот последнее сообщение:
"От: Eugene Kilachkoff
Дата: 09.04.08 17:45
Здравствуйте, Beam, Вы писали:
B>
B>Наличие циклов в графе можно определить с помощью эффективного алгоритма. Алгоритм может быть реализован как для матричного, так и для спискового способа представления графа.
B>Принцип выделения циклов следующий. Если вершина имеет только входные или только выходные дуги, то она явно не входит ни в один цикл. Можно удалить все такие вершины из графа вместе со связанными с ними дугами. В результате появятся новые вершины, имеющие только входные или выходные дуги. Они также удаляются. Итерации повторяются до тех пор, пока граф не перестанет изменяться. Отсутствие изменений свидетельствует об отсутствии циклов, если все вершины были удалены. Все оставшиеся вершины обязательно принадлежат циклам.
Чисто практическое замечание: это будет работать, если имеется способ перебора элементов графа, отличный от переходов по дугам. Например, в случае зацикленного двусвязного списка -- облом."
Чисто теоретическое замечание: Утверждение "Все оставшиеся вершины обязательно принадлежат циклам." не верно.
Контр-пример: Два кольца соединённые путём длины 2 и более. Внутренние узлы такого пути не входят в циклы.
Здравствуйте, MaximUN, Вы писали:
MUN>Здравствуйте, ashkotin, Вы писали:
A>>В 2008 обсуждалась эта тема, но уже закрыта.
A>>Вот последнее сообщение:
A>>"От: Eugene Kilachkoff
A>>Дата: 09.04.08 17:45
A>>Здравствуйте, Beam, Вы писали:
B>>>
B>>>Наличие циклов в графе можно определить с помощью эффективного алгоритма. Алгоритм может быть реализован как для матричного, так и для спискового способа представления графа.
B>>>Принцип выделения циклов следующий. Если вершина имеет только входные или только выходные дуги, то она явно не входит ни в один цикл. Можно удалить все такие вершины из графа вместе со связанными с ними дугами. В результате появятся новые вершины, имеющие только входные или выходные дуги. Они также удаляются. Итерации повторяются до тех пор, пока граф не перестанет изменяться. Отсутствие изменений свидетельствует об отсутствии циклов, если все вершины были удалены. Все оставшиеся вершины обязательно принадлежат циклам.
A>>Чисто практическое замечание: это будет работать, если имеется способ перебора элементов графа, отличный от переходов по дугам. Например, в случае зацикленного двусвязного списка -- облом."
A>>Чисто теоретическое замечание: Утверждение "Все оставшиеся вершины обязательно принадлежат циклам." не верно.
A>>Контр-пример: Два кольца соединённые путём длины 2 и более. Внутренние узлы такого пути не входят в циклы.
MUN>А чем обычный DFS не угодил?
Моё замечание собственно только про теорию: "Чисто теоретическое замечание: Утверждение "Все оставшиеся вершины обязательно принадлежат циклам." не верно."
Сам наткнулся на этот курс в и-нете и они меня сбили с толку — тоже думал, что избавишься от источников и стоков, так через любую вершину будет цикл проходить.
Ан нет. Впрочем я напишу авторам. Пусть подправят свои и-лекции
