В чем различия между алгоритмами поиска циклов в ориентированных и неориентированных графах?

Некоторые различия между алгоритмами поиска циклов в ориентированных и неориентированных графах:

Для ориентированных графов при поиске цикла используется серия обходов. neerc.ifmo.ru Из каждой вершины, в которую ещё не приходили, запускается поиск в глубину, который при входе в вершину красит её в серый цвет, а при выходе из неё — в чёрный. neerc.ifmo.ru Если алгоритм пытается пойти в серую вершину, то это означает, что цикл найден. neerc.ifmo.ru

Для неориентированных графов при поиске цикла необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не является тем ребром, по которому пришли в эту вершину. neerc.ifmo.ru По определению, одно ребро не должно встречаться в цикле дважды. neerc.ifmo.ru

Ещё одно различие заключается в том, что в ориентированном графе два разных пути к одной и той же вершине не образуют цикла, поэтому нужен другой алгоритм. stackoverflow.com

Для поиска циклов в графах часто используется алгоритм поиска (или обхода) в глубину (DFS). foxford.ru В случае неориентированного графа результатом алгоритма является маршрут, следуя которому можно обойти последовательно все вершины графа, доступные из начальной вершины. foxford.ru Если граф ориентированный, то поиск в глубину строит дерево путей из начальной вершины во все доступные из неё. foxford.ru