Поиск одного из фундаментальных множеств циклов данного связного неориентированного графа

1.  Условие задачи

Найти одно из фундаментальных множеств циклов данного связного неориентированного графа.

2.  Анализ задачи

Дано: граф G, а именно количество его вершин nver, количество рёбер nreb и список рёбер.

Результат: фундаментальное множество циклов, если такое существует, или сообщение о том, что граф ацикличен в противном случае. Фундаментальное множество циклов представляется в виде матрицы циклов.

Структура данных: для внутреннего представления графа используем список рёбер, а именно трёхмерный динамический целочисленный массив rebra, состоящий из nreb строк и 3х столбцов. Третий столбец будет содержать метку о том, использовано ли данное ребро. Такое представление удобно тем, что занимает меньше всего памяти по сравнению с другими способами представления. Неудобством является то, что для поиска вершин, смежных с данной, приходится проходить весь список от начала до конца. Улучшение возможно путём упорядочения рёбер по номерам вершин, входящих в них.

Для представления матрицы циклов, содержащей в себе фундаментальные циклы,  воспользуемся двумерным динамическим целочисленным массивом result, который содержит nreb строк и nreb – nver + 1 столбцов, где nreb – nver + 1 – количество циклов, входящих в фундаментальное множество. Элемент result[i][j] равен 1, если ребро rebra[i] входит в j-ый цикл, и равен нулю в противном случае.

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

Метод решения: прежде всего ещё при вводе рёбер будем упорядочивать вершины в ребре по возрастанию, что позволит уменьшить количество сравнений при поиске нужного ребра. Условимся, что вершины нумеруются по порядку, начиная с 1. После ввода рёбер посчитает количество фундаментальных циклов, и если это число положительное то инициализируем  массивы result и versh, который будет содержать метки вершин. Для порождения фундаментального множества циклов используем метод поиска в глубину. Он строит остовное дерево, и каждое обратное ребро порождает цикл относительно этого дерева. Чтобы следить за рёбрами дерева, используется стек, в котором хранятся все текущие вершины пройденного пути в данный момент. При попадании на обратное ребро, обнаруженный цикл будет состоять из этого ребра и рёбер, соединяющих вершины из верха стека до той вершины, в которую мы вернулись. Построение остовного дерева будем начинать с вершины под номером 1.

Этот алгоритм можно представить следующим образом:

верш. стека = 1;

в_стек(1);

CYCLE (1);

void CYCLE (int x)

{  versh[x] = 1; // вершина x исследована

   for (все рёбра)

   { v = 0;

      if (rebra[k] не использовано)

      if (x инцидентна rebra[k]) v = вторая вершина, инцидентная rebra[k];

      if (v 0)

      { rebra[k][2] = 1; // ребро k исследовано

         в_стек(v);

         if (v не исследована) СYCLE (v);

         elseвывести_цикл_из_стека;

         из_стека;

      }

    }

  }

Функция вывести_цикл_из_стека выполняет вывод в файл последовательности вершин графа, входящих в найденный цикл, а также заполняет один столбец матрицы циклов путём поиска ребра, входящего в цикл, в массиве rebra и записи в соответствующую ячейку матрицы циклов значения 1.

3.  Пример работы алгоритма

Исходный файл:

4 4

1 2

1 4

4 2

3 2