Поиск элементарных циклов в графе

Рассмотрим алгоритм поиска всех элементарных циклов в неориентированном графе. В этой статье будет приведено описание алгоритма и его реализация на языке программирования C#.

Циклом в графе называется такая конечная цепь, которая начинается и заканчивается в одной вершине. Цикл обозначается последовательностью вершин, которые он содержит, например: (3-5-6-7-3).

Кстати, про цепи, а именно про поиск элементарных цепей в графе мы недавно писали.

Цикл называется элементарным, если все вершины, входящие в него, различны (за исключением начальной и конечной).

Давайте рассмотрим пример. Пусть дан такой граф:

Поиск элементарных циклов в графе. Пример графа - vscode.ru

Перечислим все элементарные циклы в нем: 2-3-4-2, 2-3-5-4-2, 3-2-4-3, 3-2-4-5-3, 3-4-5-3, 4-3-2-4, 4-3-5-4, 4-2-3-5-4, 5-4-3-5, 5-4-2-3-5.

Допустим граф задается, как G = (V, E), где V – множество вершин графа, а E – множество ребер этого графа. Вершины и ребра представим объектами таких классов:

, где x, y – координаты центра вершины на плоскости.

, где v1, v2 – номера вершин, которые соединяет данное ребро.

Важно! Нумерация вершин начинается с нуля!

Множества вершин и ребер графа будем хранить в списках List<>:

Для поиска всех элементарных циклов в неориентированном графе будем использовать модификацию рекурсивного алгоритма “поиск в глубину” (DFS). DFS (Depth-first search) – это один из алгоритмов для обхода графа. Обязательно почитайте про него подробнее здесь.

Модифицируем алгоритм DFS в DFScycle. Прототип функции DFScycle будет таким:

, где u – номер вершины, в которой мы находимся в данный момент, endV – номер конечной вершины цикла, Е – список ребер, color[] – массив, в котором хранятся цвета вершин, unavailableEdge – см. ниже, cycle – список, в который заносится последовательность вершин искомого цикла.

В конечном итоге будем преобразовывать последовательность номеров вершин цикла из списка cycle в строку вида: “2-6-7-2″. Хранить всю совокупность элементарных циклов будем в списке строк:

Рассмотрим работу алгоритма DFScycle. В начальный момент времени все вершины графа окрашены в белый цвет. Необходимо выполнить следующее:

Перебираем все вершины, любая из них может иметь элементарный цикл. На каждой итерации перекрашиваем все вершины в белый цвет (обозначим его 1, а черный цвет будем обозначать 2). Добавляем в список вершин цикла cycle текущую вершину.

Теперь поговорим про параметр unavailableEdge. Вершину, для которой ищем цикл, перекрашивать в черный цвет не будем, иначе программа не сможет в нее вернуться, поскольку эта вершина окажется недоступной. Поэтому введем переменную unavailableEdge, в которую будем передавать номер последнего ребра, по которому осуществлялся переход между вершинами, соответственно это ребро на следующем шаге окажется недоступным для перехода. В действительности это необходимо только на первом уровне рекурсии, чтобы избежать некорректной работы алгоритма и вывода, например, ошибочного результата поиска 1-2-1 при наличии такого графа:

Граф из двух вершин

Вызовем процедуру DFScycle(…).

Процедура DFScycle(int u, int endV, List<Edge> E, int[] color, int unavailableEdge, List<int> cycle).

  • ЕСЛИ номер вершины u не равен endV, то мы не достигли конца элементарного цикла, поэтому перекрашиваем вершину u в черный цвет. ИНАЧЕ ЕСЛИ число вершин в списке cycle больше или равно двум – конец цикла достигнут: добавляем цикл cycle в список catalogCycles и выполняем возврат из функции.
  • Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, рекурсивно выполняем процедуру DFScycle(w, endV, E, color, unavailableE, cycleNEW), предварительно добавив вершину w в список cycleNEW. Возвращаем вершине w белый цвет (возможно через нее проходят другие циклы, поэтому не будем исключать ее из рассмотрения).

Примечание 1. Поскольку алгоритм обходит граф во все стороны, то выходит, что он обходит цикл в обе стороны, в итоге программа находит одинаковые циклы вида: 1-3-4-1, 1-4-3-1. Получаются своеобразные палиндромы. В реализации функции DFScycle присутствует механизм исключения таких палиндромов из списка результатов поиска.

Примечание 2. Поскольку в языке C# списки List передаются по ссылке (а не по значению), то для корректной работы алгоритма необходимо создавать копию списка cycle cycleNEW и передавать ее [копию] в новый вызов функции DFScycle().

Реализация процедуры DFScycle на языке программирования C#:

Результатом выполнения этой процедуры поиска элементарных циклов для графа, рассмотренного выше, будет такая последовательность циклов:

Результат поиска элементарных циклов - vscode.ru

Скачать код процедуры DFScycle

 

Поиск элементарных циклов в графе
5 (100%) 7 votes

Поделиться в соц. сетях:

13 комментария(ев) к статье “Поиск элементарных циклов в графе

    1. admin Автор статьи

      Вершины – в виде списка экземпляров класса Vertex, указывая координаты каждой вершины. Ребра – в виде списка экземпляров класса Edge, указывая для каждого ребра номера вершин, которые оно соединяет.

  1. Mike

    Подскажите, а как заполнять эти List, желательно примером добавления одной вершины

    1. admin Автор статьи

      Создаем List’ы:
      List V = new List();
      List E = new List();
      Добавление в List вершины графа:
      V.Add(new Vertex(X, Y));
      (X, Y) – координаты вершины.
      Добавление в другой List ребра:
      E.Add(new Edge(n1, n2));
      n1, n2 – номера вершин, которые соединяет ребро графа.

  2. Анатолий

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

    1. admin Автор статьи

      Это довольно сложный вопрос, тема отдельной статьи.
      В общем случае:
      1) Вам нужно обойти граф с помощью алгоритма поиска в ширину.
      2) При обходе записывать маршрут движения по связанным вершинам.
      3) Если пришли из вершины в неё же саму, то найден цикл.
      Возможны подводные камни в виде нахождения одинаковых маршрутов, соответственно необходим механизм их исключения.
      С помощью поиска в ширину никогда обход графа не делал. На мой взгляд для данной задачи (поиска циклов) больше подходит поиск в глубину.

  3. Дека

    Собрал все куски программы, сделал объявление графа, но когда вызываю функцкию выводит это:
    Для нестатического поля, метода или свойства “ConsoleApplication1.Program.cyclesSearch()” требуется ссылка на объект.
    Вот кусок кода из мейна..
    V.Add(new Vertex(1, 3));
    E.Add(new Edge(2, 3));
    cyclesSearch();
    Пробовал менять статичность/нестатичность но только хуже становилось…
    Как это исправить ?

    1. admin Автор статьи

      Здравствуйте. Если делать программу в одном файле, то, чтобы всё работало, необходимо поля:

      List< string > catalogCycles;

      List< Vertex > V;
      List< Edge > E;

      сделать статическими. Кроме того, нужно создать эти объекты с помощью оператора new.

      Методы cyclesSearch и DFScycle – также объявить статическими.

      Вот Вам пример, где всё собрано в один файл и работает:

      https://yadi.sk/i/8EpLNQLWzjLYv

      Конечно, так делать не хорошо. Лучше всего каждый класс помещать в отдельный файл, и сам процесс поиска циклов в графе также выделить в отдельный класс.

      1. Дека

        Добавил вершины:
        V.Add(new Vertex(1, 1));
        E.Add(new Edge(1, 2));

        V.Add(new Vertex(2, 1));
        E.Add(new Edge(3, 4));

        V.Add(new Vertex(2, 3));
        E.Add(new Edge(4, 5));

        V.Add(new Vertex(1, 4));
        E.Add(new Edge(3, 4));

        V.Add(new Vertex(1, 3));
        E.Add(new Edge(2, 3));
        После запуска в строке:
        if (color[E[w].v2] == 1 && E[w].v1 == u)
        (она находиться в DFScycle) вылетает ошибка что u вне границы массива

          1. Дека

            Не могу понять.. Мы вводим координаты вершины, а не порядок.

          2. admin Автор статьи

            Сначала добавляется несколько вершин:

            V.Add(new Vertex(10, 40)); //числа – это координаты вершины на плоскости
            V.Add(new Vertex(0, 1));

            Затем создаются рёбра:

            E.Add(new Edge(0, 1)); //тут мы соединили первую вершину со второй
            здесь числа – это номера вершин, которые соединяет созданное ребро.

            Номера вершин начинаются с нуля. То есть первая вершина в коде является нулевой.

Добавить комментарий для Анатолий Отменить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">