Здравствуйте __Avatar__, Вы писали:

A>Здравствуйте AndrewVK, Вы писали:

AVK>>Зависит от характеристик графа. В общем случае — волновой алгоритм по графу с глобальным графом строящимся на основании пройденных вершин.

A>То есть ты предлагаешь брать каждую вершину и проверять достижима ли она через другие вершины?
A>Если так,то это очень долго — а как-нибудь по быстрее.
A>О графе известно: список вершины, и матрица единичной достижимости (граф планарный).

Например, такой вариант волнового алгоритма.
Если граф не содержит циклов, то это — дерево,
значит, можно ввести строгое упорядочивание вершин,
значит, можно будет построить орграф с ребрами, направленными от "меньших" вершин к "большим".
Орграф понадобится для нахождения цикла (для обнаружения — достаточно просто маркировать вершины).

Да простят мне русскоязычный псевдокод.

Переменные:
  непомеченные : Множество Вершин
  необработанные : Множество Вершин
  корни : Множество Вершин // корневые вершины изолированных подграфов
  назад: Таблица (Вершина --> Вершина)
  номер: Таблица (Вершина --> Номер) // для эффективного поиска подграфа
  следующий : Номер
  циклы: Множество Множеств Вершин

Функции:
  есть_непомеченные() = (множество непомеченных не пусто)
  есть_необработанные() = (множество необработаных не пусто)
  не_помечена(вершина) = (вершина принадлежит непомеченным)

Поехали:

  обработано = помечено = 0
  непомеченные = все вершины
  помеченные = пусто

  пока есть_непомеченные() или есть_необработанные()

    вершина : Вершина // которую будем обрабатывать

    если есть_необработанные()
      вершина = любая из необработанных
      необработанные -= вершина
      номер[вершина] = следующий++
    иначе
      вершина = любая из непомеченных
      непомеченные -= вершина
      корни += вершина // эта вершина - корень нового изолированного подграфа
    конец выбора вершины

    для всех соседей вершины
      сосед : Вершина = очередной сосед

      если не_помечен(сосед)
        непомеченные -= сосед
        необработанные += сосед
        назад[сосед] = вершина
        номер[сосед] = следующий++
      иначе
        // Это цикл! остается его извлечь
        // Цикл состоит из 2 ветвей: одна восходит от текущей, другая - от соседа.
        // т.е. вершина, назад[вершина], назад[назад[вершина]]... и сосед, назад[сосед], назад[назад[сосед]]...
        // Поскольку номер[назад[v]] < номер[v], поиск корня этого цикла - простое занятие

        цикл : Множество Вершин

        повторять
          сравнить номер[вершина] и номер[сосед]
          если ==
            цикл += вершина // вершина == сосед
            выйти из цикла
          если <
            цикл += сосед
            сосед = назад[сосед]
          если >
            цикл += вершина
            вершина = назад[вершина]
          конец выбора
        конец

        циклы += цикл

        // при желании, можно удалять вершины цикла из дальнейшего рассмотрения,
        // то есть из множеств "номер", "назад", "необработанные"
        // тогда не будут обнаружены такие циклы:
        //
        // --(*)--(*)--(*)--(*)--
        //    |    |    |    |
        //    |    +----+    |
        //    +--------------+

      конец проверки соседа
    конец перебора по соседям

  конец обработки