Как проверить есть ли в графе цикл

Поиск всех циклов в графе

При изучении алгоритма на e-maxx Проверка графа на ацикличность и нахождение цикла понял, что алгоритм прекращает работу при нахождении первого цикла. Как найти все циклы в графе? Я переделал исходный алгоритм. При реализации моего алгоритма, некоторые циклы упускаются из вида. Например:

Ребра в неориент. графе: 1 2 1 3 2 3 2 4 3 4 Циклы: 1 2 3 1 2 3 4 2 1 2 4 3 1

Мой алгоритм find_cycles() не находит третий цикл. Как можно это исправить?

Все циклы — это все простые циклы? (Если нет, то их обычно бесконечно много.)

В полном графе из n вершин различных простых циклов — порядка n!. Так что в любом случае решение, работающее для произвольного графа, будет не быстрее перебора. Перебор отличается от поиска в глубину тем, что при выходе из рекурсивной функции следует вообще снимать пометку ( color[v] = 0; ).

При выходе она у меня снимается же? ( color[v] = 2; )

Вообще снимать — это вернуть в исходное состояние. Чтобы if(color[to] == 0) не отличил.

Значит для задач это бысмысленное дело? Т.е. в задачах это не нужно?

Иногда бывает нужно. Gassa выше уже сказал, как можно найти все простые циклы.

Интересно, что можно «быстро» найти базис «простых циклов».

Или формально: сопоставим циклу битовую строку длинной E (число ребер), ясно, что сумма таких битовых строк даст битовую строку, соответствующую циркуляции. То есть можно найти базис в лин. пространстве циркуляций. Таким базисом будет следующий набор циклов: строим остовный лес, далее берем любое ребро не из леса, и получаем, отбросив ненужную часть леса, цикл. Несложно заметить, что это базис. таким образом размеренность пространства: E-(V-C), C-число компонент связности.

Лучше бы дали ссылку, например, сюда или на какую-нибудь книгу. Потому что если человек не сильно хорошо разбирается в линейной алгебре (а таких тут, кажется, большинство), то ему с Вашего объяснения ничего ясно не будет.

Источник

Нахождение отрицательного цикла в графе

Дан ориентированный взвешенный граф с вершинами и рёбрами. Требуется найти в нём любой цикл отрицательного веса, если таковой имеется.

При другой постановке задачи — требуется найти все пары вершин такие, что между ними существует путь сколько угодно малой длины.

Эти два варианта задачи удобно решать разными алгоритмами, поэтому ниже будут рассмотрены оба из них.

Одна из распространённых «жизненных» постановок этой задачи — следующая: известны курсы валют, т.е. курсы перевода из одной валюты в другую. Требуется узнать, можно ли некоторой последовательностью обменов получить выгоду, т.е. стартовав с одной единицы какой-либо валюты, получить в итоге больше чем одну единицу этой же валюты.

Решение с помощью алгоритма Форда-Беллмана

Алгоритм Форда-Беллмана позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов.

Не будем вдаваться здесь в подробности (которые описаны в статье по алгоритму Форда-Беллмана), а приведём лишь итог — то, как работает алгоритм.

Делается итераций алгоритма Форда-Беллмана, и если на последней итерации не произошло никаких изменений — то отрицательного цикла в графе нет. В противном случае возьмём вершину, расстояние до которой изменилось, и будем идти от неё по предкам, пока не войдём в цикл; этот цикл и будет искомым отрицательным циклом.

Решение с помощью алгоритма Флойда-Уоршелла

Алгоритм Флойда-Уоршелла позволяет решать вторую постановку задачи — когда надо найти все пары вершин , между которыми кратчайшего пути не существует (т.е. он имеет бесконечно малую величину).

Опять же, более подробные объяснения содержатся в описании алгоритма Флойда-Уоршелла, а здесь мы приведём только итог.

После того, как алгоритм Флойда-Уоршелла отработает для входного графа, переберём все пары вершин , и для каждой такой пары проверим, бесконечно мал кратчайший путь из в или нет. Для этого переберём третью вершину , и если для неё оказалось (т.е. она лежит в цикле отрицательного веса), а сама она достижима из и из неё достижима — то путь может иметь бесконечно малую длину.

Задачи в online judges

Список задач, в которых требуется искать цикл отрицательного веса:

Источник

Как проверить есть ли в графе цикл

Поиск всех циклов в графе

Ребра в неориент. графе: 1 2 1 3 2 3 2 4 3 4 Циклы: 1 2 3 1 2 3 4 2 1 2 4 3 1

Мой алгоритм find_cycles() не находит третий цикл. Как можно это исправить?

Все циклы — это все простые циклы? (Если нет, то их обычно бесконечно много.)

При выходе она у меня снимается же? ( color[v] = 2; )

Вообще снимать — это вернуть в исходное состояние. Чтобы if(color[to] == 0) не отличил.

Значит для задач это бысмысленное дело? Т.е. в задачах это не нужно?

Иногда бывает нужно. Gassa выше уже сказал, как можно найти все простые циклы.

Интересно, что можно «быстро» найти базис «простых циклов».

Источник

Обнаружение цикла в неориентированном графике

,
Учитывая неориентированный граф, как проверить, есть ли цикл в графе? Например, следующий график имеет цикл 1-0-2-1.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

using namespace std;

// Класс для неориентированного графа

int V; // Количество вершин

list int > *adj; // Указатель на массив, содержащий списки смежности

bool isCyclicUtil( int v, bool visited[], int parent);

Graph( int V); // Конструктор

void addEdge( int v, int w); // добавить ребро на график

bool isCyclic(); // возвращает true, если есть цикл

adj = new list int >[V];

void Graph::addEdge( int v, int w)

adj[v].push_back(w); // Добавить w в список v.

adj[w].push_back(v); // Добавить v в список w.

// Рекурсивная функция, которая использует visit [] и parent для обнаружения
// цикл в подграфе, достижимом из вершины v.

bool Graph::isCyclicUtil( int v, bool visited[], int parent)

// Пометить текущий узел как посещенный

// Повторение для всех вершин, смежных с этой вершиной

list int >::iterator i;

// Если соседний не посещен, то повторяем для этого соседнего

if (isCyclicUtil(*i, visited, v))

// Если соседний посещен и не является родителем текущей вершины,

// Возвращает true, если граф содержит цикл, иначе false.

// Пометить все вершины как не посещенные и не являющиеся частью рекурсии

bool *visited = new bool [V];

// Вызываем рекурсивную вспомогательную функцию для определения цикла в разных

if (!visited[u]) // Не повторяться для вас, если он уже посещен

// Программа драйвера для проверки вышеуказанных функций

g1.isCyclic()? cout «Graph contains cycle\n» :

cout «Graph doesn’t contain cycle\n» ;

g2.isCyclic()? cout «Graph contains cycle\n» :

cout «Graph doesn’t contain cycle\n» ;

// Java-программа для обнаружения цикла в неориентированном графе

// Этот класс представляет ориентированный граф, используя список смежности
// представление

private int V; // Количество вершин

private LinkedList adj[]; // Пересмотр списка смежности

adj = new LinkedList[v];

adj[i] = new LinkedList();

// Функция для добавления ребра в график

void addEdge( int v, int w) <

// Рекурсивная функция, которая использует visit [] и parent для обнаружения

// цикл в подграфе, достижимом из вершины v.

Boolean isCyclicUtil( int v, Boolean visited[], int parent)

// Пометить текущий узел как посещенный

// Повторение для всех вершин, смежных с этой вершиной

Iterator it = adj[v].iterator();

// Если соседний не посещен, то повторить для этого

if (isCyclicUtil(i, visited, v))

// Если соседний посещен и не является родителем текущего

// вершина, то есть цикл.

// Возвращает true, если граф содержит цикл, иначе false.

// Пометить все вершины как не посещенные и не являющиеся частью

Boolean visited[] = new Boolean[V];

// Вызываем рекурсивную вспомогательную функцию для обнаружения цикла в

// разные деревья DFS

if (!visited[u]) // Не повторяться, если вы уже посетили

// Метод драйвера для тестирования вышеуказанных методов

public static void main(String args[])

// Создать график, приведенный на диаграмме выше

Graph g1 = new Graph( 5 );

System.out.println( «Graph contains cycle» );

System.out.println( «Graph doesn’t contains cycle» );

Graph g2 = new Graph( 3 );

System.out.println( «Graph contains cycle» );

System.out.println( «Graph doesn’t contains cycle» );

>
// Этот код предоставлен Aakash Hasija

# Программа Python для обнаружения цикла в неориентированном графе

from collections import defaultdict

# Этот класс представляет неориентированный граф, используя представление списка смежности

# функция для добавления ребра на график

# Рекурсивная функция, которая использует посещенный [] и родительский для обнаружения

# цикл в подграфе, достижимый из вершины v.

# Отметить текущий узел как посещенный

# Повторить для всех вершин, смежных с этой вершиной

# Если узел не посещен, рекурсировать на нем

if visited[i] = = False :

# Если соседняя вершина посещена и не является родителем текущей вершины,

# Возвращает true, если граф содержит цикл, иначе false.

# Отметить все вершины как не посещенные

# Вызовите рекурсивную вспомогательную функцию, чтобы обнаружить цикл в разных

if visited[i] = = False : # Не повторяться, если он уже посещен

# Создайте график, приведенный на диаграмме выше

print «Graph contains cycle»

print «Graph does not contain cycle «

print «Graph contains cycle»

print «Graph does not contain cycle «

# Этот код предоставлен Ниламом Ядавом

// C # Программа для обнаружения цикла в неориентированном графе

// Этот класс представляет ориентированный граф
// используя представление списка смежности

private int V; // Количество вершин

// Пересмотр списка смежности

private List int > []adj;

adj = new List int >[v];

adj[i] = new List int >();

// Функция для добавления ребра в график

void addEdge( int v, int w)

// Рекурсивная функция, которая использует с посещением []

// и родитель для определения цикла в подграфе

// достижимы из вершины v.

Boolean isCyclicUtil( int v, Boolean []visited,

// Пометить текущий узел как посещенный

// повторить для всех вершин

// рядом с этой вершиной

foreach ( int i in adj[v])

// Если соседний не посещен,

// затем повторяем для этого смежного

if (isCyclicUtil(i, visited, v))

// Если соседний посещен и

// не является родителем текущей вершины,

// Возвращает true, если график содержит

// Пометить все вершины как не посещенные

// а не часть стека рекурсии

Boolean []visited = new Boolean[V];

// Вызов рекурсивной вспомогательной функции

// обнаружение цикла в разных деревьях DFS

// Не повторяться, если вы уже посетили

public static void Main(String []args)

// Создать график, приведенный на диаграмме выше

Graph g1 = new Graph(5);

Console.WriteLine( «Graph contains cycle» );

Console.WriteLine( «Graph doesn’t contains cycle» );

Graph g2 = new Graph(3);

Console.WriteLine( «Graph contains cycle» );

Console.WriteLine( «Graph doesn’t contains cycle» );

// Этот код предоставлен PrinciRaj1992

Выход:

Сложность времени: программа выполняет простой DFS обход графа и граф представлен в списке смежности. Таким образом, сложность времени O (V + E)

Упражнение: Можем ли мы использовать BFS для обнаружения цикла в неориентированном графе за время O (V + E)? Как насчет ориентированных графов?

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Источник

Как проверить есть ли в графе цикл

Как найти циклы в графе

Задан неориентированный граф. Найти количество путей проходящие через k вершин, начинающиеся и заканчивающиеся в одной и той же вершине, но не проходящие два раза через любую другую вершину.

Я пробовал написать поиск в глубину, но у меня находилось больше путей, т.к. у меня получилось что 1-2-3-4-1 и 1-4-3-2-1 — разные пути.

Вероятно, каждый путь получился посчитан одинаковое количество раз (например, два раза или 2k раз). В этом случае можно просто поделить ответ на это число.

Вот здесь задача и моё решение (писалось на PascalABC): http://pastebin.com/9XCpcqW9

1) Если запустить dfs не циклом из всех а один раз из первой то res = 6 (Ответ res/2)

2) Где в условие сказано что нужно искать пути из первой точки?

3) Верное ли решение? Есть ли более оптимальное?

Честно говоря, я не верю в это решение, мне кажется, поиск в глубину не найдет все циклы. Хотя могу и ошибаться. Есть 100% решение за O(n(n-1)(n-2)(n-3). (n-k+1)*k)=O(k*n^k): перебрать все возможные множества из k вершин и проверить, являются ли они циклами. Тогда ответ надо будет поделить на 2*k, ибо каждый цикл будет посчитан именно столько раз. Но при n=300 и k=4 это будет очень много итераций, так что, думаю, есть и более простое решение :\

Логика решения такова — идём из вершины(или из всех вершин,что я и делал) по соседям(записав вершину,с которой начали), изменяя длину пути и записывая каждую вершину в сет, чтобы проверить не были ли мы на данной вершине. Как только длина достигает нужного значения — проверяем куда мы пришли.

Этот алгоритм переберёт (должен перебрать, т.к. я впервые написал алгоритм на графах) все пути, начинающиеся в вершине,из которой он был запущен.

p.s. Задача с муниципального этапа РОИ. Поэтому вопрос номер 2 (выше) всё же актуален.

Можно по идее сделать так: перебираем все пары вершин. Пересекаем их списки смежности. Считаем количество вершин в пересечении. К ответу прибавляем x * (x — 1) / 2. Итого: алгоритм за N^3. Будет быстрее если списки смежности хранить как битовую маску, тогда пересечение можно сделать за N / 32, а подсчет битов в числе за 2 операции. В конце ответ надо будет поделить на что-то еще, так как все циклы учтутся одинаковое количество раз.

А разве, если k = n, это не задача о гамильтоновом цикле? 🙂

Не совсем в явном виде, конечно. Но, если мы решим данную, мы узнаем, существует ли в графе гамильтонов цикл.

Запускать DFS нужно, конечно, от всех вершин по очереди. DFS должен перед выходом из рекурсии снимать пометку с вершины.

P.S. Задача коротко формулируется так: кол-во простых циклов длины k в неориентированном графе.

O(n^4), при n=300 кол-во операций более 8,1*10^9 — такое решение должно пройти? Ссылки на задачу у меня самого не было. Условие изменил — хотел узнать решение для более общего случая.

Но у меня видимо проблема ещё и с пониманием задачи. У нас же есть пути (тест из условия): 1-2-3-4-1 1-4-3-2-1 1-4-2-3-1 3-2-1-4-3 и т.д.

А правильный ответ — 3. Что я неправильно понимаю?

Выше был код тс с вбитым условием задачи. В условии K = 4. Я и рассказал решение для K = 4.

Извиняюсь, я как-то не догадался, что автор под ссылкой указал другое условие.

Wackloner, можешь подробнее объяснить, как для данных 4-ёх вершин за O(k) определить, что они образуют цикл?

Я могу ошибаться, но разве нельзя взять алгоритм отсюда и посчитать количество путей длиной k от i-той вершины до нее самой?

Будет очень здорово если этот алгоритм можно переделать не под пути,а под циклы. Есть такое, но я ничего не понял из этой статьи

но не проходящие два раза через любую другую вершину

Т.е. нужно кол-во простых циклов (путей). По ссылке кол-во непростых циклов (путей).

Вроде как непростой цикл длины 4 через вершину v — это содержащий петли(которые можно нафиг выкинуть вначале) или состоящий из двух циклов длины 2, а это что-то около deg(v)^2

и посчитать количество путей длиной k

Насколько я понял, BekzhanKassenov имел в виду случай произвольного k.

Ну да. Только теперь прочитал что k == 4. Но ведь n^4 не проходит?

Думаю, можно по аналогии выкидывать повторения для всех разложений k=mp. Но это уже не полином, кажется.

какой-то хаотичный пост. каждый что-то отвечает но все подразумевают разные задачи, где-то похоже присутсвовал код с условием и ссылкой, но я не обнаружил его.
полагаю речь идет об этой задаче ссылку на которую я скопировал из сообщения выше от Burunduk1. Я думаю можно найти количество циклов(не обязательно простых) длины 4 каким-нибудь тупым способом, например умножением матрицы смежности нужное число раз. затем порисовать всевозможные непростые циклы, какие они вообще бывают. найти для каждой вершины какие и в каком количестве присутствуют. это можно сделать за O(n^3) т.к. в непростых циклах число различных вершин не более 3-х, а количество типов константное (вроде 2, но лень думать). Теперь вычитаем одно из другого, и получаем количество простых циклов.

Источник