Псевдокод для поиска циклов в графе с использованием поиска в ширину

Question

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

Answer 1

На всякий случай, DFS гораздо больше подходит для этой задачи, особенно в ориентированных графах. Если вы уже знали это, игнорируйте это.

Что касается псевдокода, то в неориентированном графе это традиционная BFS, которая прерывает и сообщает о найденном цикле, когда достигает узла, ранее помеченного как посещенный. Вы можете найти псевдокод для BFS здесь .

В ориентированном графе это становится сложнее, поскольку вы должны помнить, каким путем вы шли, когда достигли узла, а недостаток пространственной сложности по сравнению с DFS становится еще хуже.

Edit: о, я говорил о тестировании графика для циклов, а не на самом деле найти цикл. Поиск циклов в DFS близок к тривиальному, в то время как поиск циклов в BFS намного сложнее как с точки зрения реальной алгоритмической сложности, так и сложности кода. Вот почему вы не можете найти псевдокод.

Answer 2

Вы, вероятно, имели в виду DFS, которая гораздо чаще встречается при обнаружении циклов, поэтому я предполагаю, что вы допустили эту ошибку.Переход на BFS довольно прост, хотя основная идея остается прежней.

func detectCycle()
  for node in graph:
    visited = bool[N]
    set all visited to false
    detectCycle(n, n, visited)

func detectCycle(n, origin, visited)
  for neighbour in graph[n]
    if neighbour == origin
       cycle detected
    if not visited[neighbour]
       visited[neighbour] = true
       detectCycle(neighbour, visited)
       visited[neighbour] = false