Помощь - Поиск - Пользователи - Календарь
Полная версия: циклы в графе
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Bard
У меня тут одна задачка в которой нужно найти есть ли цикл в графе? Никакие поисковики не помогли. Может вы знаете алгоритм? Заранее большое спасибо. smile.gif
volvo
Что, Гугл вот про эту страничку не знает: http://guap.ru/dept04/caf46/textbooks/str_alg/index4.htm ?

Цитата
Принцип выделения циклов следующий. Если вершина имеет только входные или только выходные дуги, то она явно не входит ни в один цикл. Можно удалить все такие вершины из графа вместе со связанными с ними дугами. В результате появятся новые вершины, имеющие только входные или выходные дуги. Они также удаляются. Итерации повторяются до тех пор, пока граф не перестанет изменяться. Отсутствие изменений свидетельствует об отсутствии циклов, если все вершины были удалены. Все оставшиеся вершины обязательно принадлежат циклам.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.