Есть ли у кого-то исходники (можно просто алгоритм пошаговый) нахождения циклов в графе.
нужно не просто определить их наличие, а выявить вершины всего цикла.
Если циклов много, то тогда нахождение каждого отдельно, удаление его из графа и поиск в оставшемся графе следующего цикла!
A>Есть ли у кого-то исходники (можно просто алгоритм пошаговый) нахождения циклов в графе. A>нужно не просто определить их наличие, а выявить вершины всего цикла. A>Если циклов много, то тогда нахождение каждого отдельно, удаление его из графа и поиск в оставшемся графе следующего цикла!
Зависит от характеристик графа. В общем случае — волновой алгоритм по графу с глобальным графом строящимся на основании пройденных вершин.
Здравствуйте AndrewVK, Вы писали:
AVK>Зависит от характеристик графа. В общем случае — волновой алгоритм по графу с глобальным графом строящимся на основании пройденных вершин.
То есть ты предлагаешь брать каждую вершину и проверять достижима ли она через другие вершины?
Если так,то это очень долго — а как-нибудь по быстрее.
О графе известно: список вершины, и матрица единичной достижимости (граф планарный).
A>Добрый вечер!
A>Есть ли у кого-то исходники (можно просто алгоритм пошаговый) нахождения циклов в графе. A>нужно не просто определить их наличие, а выявить вершины всего цикла. A>Если циклов много, то тогда нахождение каждого отдельно, удаление его из графа и поиск в оставшемся графе следующего цикла!
A>
Правильные слова "топологическая сортировка".
Описание и обсуждение алгоритма можно найти в книге:
Алгоритмы: построение и анализ, Кормен Т., Лейзерсон Ч., Ривест Р.
A>Добрый вечер!
A>Есть ли у кого-то исходники (можно просто алгоритм пошаговый) нахождения циклов в графе. A>нужно не просто определить их наличие, а выявить вершины всего цикла. A>Если циклов много, то тогда нахождение каждого отдельно, удаление его из графа и поиск в оставшемся графе следующего цикла!
A>
Транзитивное замыкание
алгоритм:
замыкаем;
замыкаем;
...
замыкаем;
получили, что вершина замыкается сама на себя — помечаем, как участвующую в цикле (каком — не важно).
определение вершин цикла м-да... получится, что все вершины, которые содержатся в циклах (если их больше одного) образуют один большой цикл... и никак от этого не избавиться...
как их раскидать по циклам что-то сразу и не соображу
Если при компиляции и исполнении вашей программы не происходит ни одной ошибки — это ошибка компилятора :)))
A>Добрый вечер!
A>Есть ли у кого-то исходники (можно просто алгоритм пошаговый) нахождения циклов в графе. A>нужно не просто определить их наличие, а выявить вершины всего цикла. A>Если циклов много, то тогда нахождение каждого отдельно, удаление его из графа и поиск в оставшемся графе следующего цикла!
A>
Небольшое замечание.
Если циклов много, становится важным порядок нахождения и удаления циклов.
От этого порядка зависит конечный результат.
Может для тебя это тоже важно
A>Добрый вечер!
A>Есть ли у кого-то исходники (можно просто алгоритм пошаговый) нахождения циклов в графе. A>нужно не просто определить их наличие, а выявить вершины всего цикла. A>Если циклов много, то тогда нахождение каждого отдельно, удаление его из графа и поиск в оставшемся графе следующего цикла!
Граф связный? Какие циклы нужно находить (гамильтоновы, эйлеровы или любые)? Какой метод удаления? Вот например граф:
Можно последовательно находить и удалять рёбра циклов и получившиеся изолированные вершины: 145, 125, 526, 263, 367.
Можно последовательно находить и удалять рёбра и вершины циклов, тогда: 145, 263, 7 (Заметим, что последняя была изолированная вершина — тоже цикл, только маленький!)
Можно сразу найти цикл 1237654 и удалить эти вершины с инцидентными рёбрами — вообще одна итерация.
Здравствуйте __Avatar__, Вы писали:
A>Здравствуйте AndrewVK, Вы писали:
AVK>>Зависит от характеристик графа. В общем случае — волновой алгоритм по графу с глобальным графом строящимся на основании пройденных вершин.
A>То есть ты предлагаешь брать каждую вершину и проверять достижима ли она через другие вершины? A>Если так,то это очень долго — а как-нибудь по быстрее. A>О графе известно: список вершины, и матрица единичной достижимости (граф планарный).
Например, такой вариант волнового алгоритма.
Если граф не содержит циклов, то это — дерево,
значит, можно ввести строгое упорядочивание вершин,
значит, можно будет построить орграф с ребрами, направленными от "меньших" вершин к "большим".
Орграф понадобится для нахождения цикла (для обнаружения — достаточно просто маркировать вершины).
Да простят мне русскоязычный псевдокод.
Переменные:
непомеченные : Множество Вершин
необработанные : Множество Вершин
корни : Множество Вершин // корневые вершины изолированных подграфов
назад: Таблица (Вершина --> Вершина)
номер: Таблица (Вершина --> Номер) // для эффективного поиска подграфа
следующий : Номер
циклы: Множество Множеств Вершин
Функции:
есть_непомеченные() = (множество непомеченных не пусто)
есть_необработанные() = (множество необработаных не пусто)
не_помечена(вершина) = (вершина принадлежит непомеченным)
Поехали:
обработано = помечено = 0
непомеченные = все вершины
помеченные = пусто
пока есть_непомеченные() или есть_необработанные()
вершина : Вершина // которую будем обрабатывать
если есть_необработанные()
вершина = любая из необработанных
необработанные -= вершина
номер[вершина] = следующий++
иначе
вершина = любая из непомеченных
непомеченные -= вершина
корни += вершина // эта вершина - корень нового изолированного подграфа
конец выбора вершины
для всех соседей вершины
сосед : Вершина = очередной сосед
если не_помечен(сосед)
непомеченные -= сосед
необработанные += сосед
назад[сосед] = вершина
номер[сосед] = следующий++
иначе
// Это цикл! остается его извлечь
// Цикл состоит из 2 ветвей: одна восходит от текущей, другая - от соседа.
// т.е. вершина, назад[вершина], назад[назад[вершина]]... и сосед, назад[сосед], назад[назад[сосед]]...
// Поскольку номер[назад[v]] < номер[v], поиск корня этого цикла - простое занятие
цикл : Множество Вершин
повторять
сравнить номер[вершина] и номер[сосед]
если ==
цикл += вершина // вершина == сосед
выйти из цикла
если <
цикл += сосед
сосед = назад[сосед]
если >
цикл += вершина
вершина = назад[вершина]
конец выбора
конец
циклы += цикл
// при желании, можно удалять вершины цикла из дальнейшего рассмотрения,
// то есть из множеств "номер", "назад", "необработанные"
// тогда не будут обнаружены такие циклы:
//
// --(*)--(*)--(*)--(*)--
// | | | |
// | +----+ |
// +--------------+
конец проверки соседа
конец перебора по соседям
конец обработки
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Перекуём баги на фичи!
