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

Проверить, есть ли цикл в ориентированном графе

Дан ориентированный граф на n вершинах и m ребрах. Требуется проверить, есть ли в нем цикл, и вывести его, если он есть.

Входные данные:
В первой строке входного файла заданы числа n и m (1≤n,m≤1000000). Затем в m строках заданы пары чисел ui vi, означающие, что в графе есть ребро из ui в vi (1≤ui,vi≤n).

Выходные данные:
Выведите «-1» (без кавычек), если в графе нет цикла, или сам цикл, если он есть: на первой строке — его длину, на второй — вершины цикла в порядке их следования в графе.

Примеры:
входные данные
3 3
1 2
2 3
3 1
выходные данные
3
1 2 3

входные данные
3 3
1 2
1 3
2 3
выходные данные
-1

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Проверить, есть ли в графе цикл
Дан ориентированный граф на n вершинах и m ребрах. Требуется проверить, есть ли в нем цикл, и.

Найти цикл в ориентированном графе
Добрый день! У меня такая трабла. Дан ориентированный граф, заданный весовой матрицей. Найти цикл в.

Поиск циклов в ориентированном графе
Здравствуйте, есть такая вот задача: граф задан в файле списком смежности и числа — длина цикла и.

Восстановление путей в ориентированном графе с++
Нужно вывести кратчайший путь между двумя заданными вершинами Код для поиска кратчайшего пути.

Поиск корня в ориентированном графе
Граф ввожу из файла в списки смежности terminal – хранит вершины, в которые входят ребра; .

35346 / 19946 / 4179
Регистрация: 12.02.2012
Сообщений: 33,093
Записей в блоге: 13
Намек: если m=n-1, то цикла точно нет. Можно не искать.
4751 / 2643 / 547
Регистрация: 07.11.2019
Сообщений: 4,359

Catstail, не факт, например граф задан такой:
входные данные
4 3
1 2
2 3
3 1
Цикл есть:
выходные данные
3
1 2 3
Еще непонятно, ориентированость графа влияет ли на ответ или нет. Если нет, то зачем задан именно ориентированный граф?

35346 / 19946 / 4179
Регистрация: 12.02.2012
Сообщений: 33,093
Записей в блоге: 13

u235, Я имел в виду связный граф. А Вы задали граф с уединенной вершиной (4). Но, строго говоря, Вы правы.

А ориентированность очень даже влияет. В графе на картинке цикла нет.

Изображения

35346 / 19946 / 4179
Регистрация: 12.02.2012
Сообщений: 33,093
Записей в блоге: 13

u235, вариант:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

def get_graph(): (n,m)=tuple(map(int,input().split())) graph=[] for _ in range(m): (a,b)=tuple(map(int,input().split())) graph.append((a,b)) return graph def dfs_loops(graph): stack=[1] chk=[1] while True: if len(stack)==0: print("OK") return v=stack[-1] for (a,b) in graph: if (a==v) and not (b in chk): stack.append(b) chk.append(b) # Проверка цикла sz=len(stack) print(stack) for i in range(sz-1): if (b,stack[i]) in graph: print("Loop:",end=' ') for j in range(i,sz): print(stack[j],end=' ') print() break else: stack.pop() g=get_graph() dfs_loops(g)

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Поиск цикла в ориентированном графе
Добрый день, уважаемые форумчане! Я писал топологическую сортировку ориентированного графа и понял.

Найти путь в ориентированном графе
Здравствуйте, помогите, пожалуйста, решить задачу: Дан список взвешенных дуг ориентированного.

Поиск в глубину в ориентированном графе
Помогите реализовать поиск в глубину в ориентированном графе. Поиск не работает корректно с.

Удаление цикла в ориентированном графе
Помогите реализовать такой вот алгоритм: Задан ориентированный граф. Необходимо найти и удалить из.

Смежные вершины в ориентированном графе
Какие вершины называются смежными в ориентированном графе?

Нахождение пути в ориентированном графе
Задать ориентированный граф и определить: 1) все узлы, доступные с заданного за один шаг (привести.

Python-сообщество

• Начало
• » Центр помощи
• » Поиск цикла в графе

#1 Авг. 3, 2015 10:28:16

Andrew22528 Зарегистрирован: 2015-05-17 Сообщения: 44 Репутация: 0 Профиль Отправить e-mail

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

Есть ориентированный граф. На вход подается 2 числа N и M — количества вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин. Надо вывести ‘YES’ и номера вершин в цикле, если цикл есть. Иначе вывести ‘NO’. Заранее спасибо

#2 Авг. 5, 2015 12:08:45

Isem От: Зарегистрирован: 2010-08-27 Сообщения: 447 Репутация: 7 Профиль Отправить e-mail

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

Взято из библиотеки bytenet3

import collections, itertools def get_loops(MN): """ Returns the tuple of closed loops. Loops are represented as ordered lists of nodes """ network = <> for a,b in MN: network[a].add(b) if a in network else network.update(a:b>>) network[b].add(a) if b in network else network.update(b:a>>) chain = collections.OrderedDict() def __loop_iterator(node): if node not in chain: chain[node] = None next = network[node] while next: n = next.pop() network[n].remove(node) yield from __loop_iterator(n) chain.popitem() else: yield tuple(itertools.chain(itertools.takewhile(lambda x: x is not node, reversed(chain)), (node,))) # 'for' is needed for just to run from any first available node as n for n in network: return tuple(__loop_iterator(n)) ch = [(1,4), (4,3), (3,2), (6,3), (4,6), (5,6), (5,4)] >>> print( *get_loops(ch), sep = '\n' ) (6, 3, 4) (5, 6, 3, 4) 

Отредактировано Isem (Авг. 5, 2015 12:11:35)

Проверка графа на наличие циклов

Для заданного графа нужно ответить, содержит ли он хотя бы один цикл. Стоит заметить, что от нас не требуется найти все циклы, нужно всего лишь ответить, существует ли хотя бы один. Задача на поиск всех циклов решается гораздо сложнее.

Алгоритм

Для поиска цикла будем использовать DFS. Для примера разберём такой граф:

Допустим, мы запустили DFS из вершины 1, и он полностью обошёл граф. Представим обход этого графа так же, как представляем деревья, по уровням в зависимости от глубины рекурсии:

(Примечание: это только один из возможных вариантов обхода в глубину.)

Как видите по одному из ребёр, входящих в цикл, DFS не спускался: оно выделено красным цветом. Именно по наличию таких “восходящих” рёбер в графе можно судить о наличии в нём циклов. При реализации DFS такие рёбра распознать достаточно легко: они ведут в уже посещённую (\(used\)) вершину, но не в прямого предка (\(p\)).

Реализация

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
#include  using namespace std; vectorint> graph[100000]; bool used[100000]; void dfs(int v, int p = -1)  //p - прямой предок used[v] = true; for (int u: graph[v])  if (!used[u])  dfs(u, v); > else if (u != p)  cout  <"Graph has cycles."; exit(0); //Полностью выйти из программы. > > > int main()  //Ввод графа. //Проверяем отдельно каждую вершину, так как //граф может быть несвязным, но всё равно иметь циклы for (int i = 0; i  n; i++)  if (!used[i])  dfs(i); > > //Если мы ещё не вышли не вышли из программы, в графе нет циклов. cout  <"Graph has no cycles."; > 
brestprog
Поиск цикла в графе
Нужно определить есть ли цикл в неориентированном графе и вывести все вершины этого цикла. Граф вводится количеством вершин и матрицей смежности. Вот что написал:
n = int(input()) matr = [] for _ in range(n): streng = list(map(int, input().split())) matr.append(streng) lister = [[] for i in range(n)] for i in range(n): for j in range(n): if matr[i][j] == 1: lister[i].append(j) visited = set() def dfs(lister, visited, curr, prev=-1): visited.add(curr) checkers = False for now in lister[curr]: if prev != now: if now in visited: return True if dfs(lister, visited, now, curr): return True visited.remove(curr) return checkers for i in range(n): ret = dfs(lister, visited, i) if ret: break visited.clear() if ret: print("YES") print(len(visited)) visited = map(lambda x: x + 1, visited) print(*visited) else: print("NO") 
Есть/нет цикл оно определяет правильно, но вот вершины в цикле нет. Например, если будет граф с соединенными по кругу вершинами, но при этом будет вершина отдельная, соединяющаяся с одной из вершин круга, то она войдет в этот цикл, хотя не должна. 4 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 Таким вводом, например, вторая вершина в цикл не входит, но выведет 1 2 3 4, т. е. все вершины. Что нужно добавить? Немного подправил. Теперь оно все тупиковые ветки будет удалять, но если начать обход с такой ветки, то она останется.