Помощь - Поиск - Пользователи - Календарь
Полная версия: поиск циклов в орграфе
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
brrr
как найти циклы в ографе если орграф задается матрицей смежности ?
Altair
Нужно все возможные циклы, всех возможных длинн найти ?

Например так...
Цикл
Берем вершину.
Находим для нее все циклы.
Удаляем вершину из графа.
переходим к следующей вершине
кцикл

нахождение циклов делается рекурсивно...
передается параметры - список вершин пройденных, и каждый проход, мы выбираем новый путь, помечаем его, и идем по исходящему пути.
Если пришли в точку исходную - цикл есть, пришли в тупик - не удалось построить цикл. Далее, делается откат (обратный ход рекурсии - бектрекинг) и идется к вершинам по ребрам нехоженным. Так строятся все циклы для вершины...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.