Нахождение цикла
Напомним, что циклом в графе $G$ называется ненулевой путь, ведущий из вершины $v$ в саму себя. Граф называют ацикличным, если в нем нет циклов.
Для нахождения цикла, рассмотрим такой альтернативные способ делать обход в глубину:
Здесь мы вместо массива used передаем в рекурсию параметр $p$, равный номеру вершины, откуда мы пришли, или $-1$, если мы начали обход в этой вершине.
Этот способ корректен только для деревьев — проверка u != p гарантирует, что мы не пойдем обратно по ребру, однако если в графе есть цикл, то мы в какой то момент вызовем dfs второй раз с одними и теми же параметрами и попадем в бесконечный цикл.
Если мы можем определять, попали ли мы в бесконечный цикл, то это ровно то, что нам нужно. Модифицируем dfs так, чтобы мы могли определять момент, когда мы входим в цикл. Для этого просто вернем массив used обратно, но будем использовать его для проверки, были ли мы когда-то в вершине, которую мы собираемся посетить — это будет означать, что цикл существует.
Если нужно восстанавливать сам цикл, то можно вместо завершения программы возвращаться из рекурсии несколько раз и выписывать вершины, пока не дойдем до той, в которой нашелся цикл.
Как и со всеми обходами, если в графе больше одной компоненты связности, или если граф ориентированный, то dfs нужно запускать несколько раз от вершин разных компонент.
Проверка графа на цикл
Проверка на связность графа
Здравствуйте, помогите пожалуйста. Есть неориентированный граф. Представлен граф список смежности.
Проверка графа на связность
Требуется проверить граф на связность. Помогите найти ошибки. #include <stdio.h> #include.
Алгоритм Дейкстры и цикл for (для заполнения веса рёбер графа)
Здравствуйте, форумчане. Задался я написанием алгоритма Дейкстры, но возникла проблема в одном.
проверка графа на связность
помогитте написать программу проверяющую граф на связность. граф задаётся в текстовом файле в виде.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Поиск элементарных циклов в графе
Рассмотрим алгоритм поиска всех элементарных циклов в неориентированном графе. В этой статье будет приведено описание алгоритма и его реализация на языке программирования C#.
Циклом в графе называется такая конечная цепь, которая начинается и заканчивается в одной вершине. Цикл обозначается последовательностью вершин, которые он содержит, например: (3-5-6-7-3).
Кстати, про цепи, а именно про поиск элементарных цепей в графе мы недавно писали.
Цикл называется элементарным, если все вершины, входящие в него, различны (за исключением начальной и конечной).
Давайте рассмотрим пример. Пусть дан такой граф:
Перечислим все элементарные циклы в нем: 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#:
Результатом выполнения этой процедуры поиска элементарных циклов для графа, рассмотренного выше, будет такая последовательность циклов:
Поделиться в соц. сетях:
14 комментария(ев) к статье “ Поиск элементарных циклов в графе ”
А каким образом мы задаем вершины и ребра ?
Ведь List и List у нас сейчас принимают значение 0
Вершины — в виде списка экземпляров класса Vertex, указывая координаты каждой вершины. Ребра — в виде списка экземпляров класса Edge, указывая для каждого ребра номера вершин, которые оно соединяет.
Подскажите, а как заполнять эти List, желательно примером добавления одной вершины
- admin Автор статьи 29.08.2016 в 23:59
Создаем 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 — номера вершин, которые соединяет ребро графа.
Добрый вечер, подскажите, а как переделать алгоритм поиска циклов с использование поиска в ширину? Буду очень благодарен.
Заранее спасибо.
- admin Автор статьи 25.10.2016 в 12:24
Это довольно сложный вопрос, тема отдельной статьи.
В общем случае:
1) Вам нужно обойти граф с помощью алгоритма поиска в ширину.
2) При обходе записывать маршрут движения по связанным вершинам.
3) Если пришли из вершины в неё же саму, то найден цикл.
Возможны подводные камни в виде нахождения одинаковых маршрутов, соответственно необходим механизм их исключения.
С помощью поиска в ширину никогда обход графа не делал. На мой взгляд для данной задачи (поиска циклов) больше подходит поиск в глубину.
Собрал все куски программы, сделал объявление графа, но когда вызываю функцкию выводит это:
Для нестатического поля, метода или свойства «ConsoleApplication1.Program.cyclesSearch()» требуется ссылка на объект.
Вот кусок кода из мейна..
V.Add(new Vertex(1, 3));
E.Add(new Edge(2, 3));
cyclesSearch();
Пробовал менять статичность/нестатичность но только хуже становилось…
Как это исправить ?
- admin Автор статьи 29.11.2016 в 11:49
Здравствуйте. Если делать программу в одном файле, то, чтобы всё работало, необходимо поля:
сделать статическими. Кроме того, нужно создать эти объекты с помощью оператора new.
Методы cyclesSearch и DFScycle — также объявить статическими.
Вот Вам пример, где всё собрано в один файл и работает:
Конечно, так делать не хорошо. Лучше всего каждый класс помещать в отдельный файл, и сам процесс поиска циклов в графе также выделить в отдельный класс.
Добавил вершины:
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 вне границы массива
- admin Автор статьи 12.12.2016 в 21:16
Дека, нумерация вершин должна начинаться с нуля, а не с единицы.
Не могу понять.. Мы вводим координаты вершины, а не порядок.
Сначала добавляется несколько вершин:
V.Add(new Vertex(10, 40)); //числа — это координаты вершины на плоскости
V.Add(new Vertex(0, 1));
Затем создаются рёбра:
E.Add(new Edge(0, 1)); //тут мы соединили первую вершину со второй
здесь числа — это номера вершин, которые соединяет созданное ребро.
Номера вершин начинаются с нуля. То есть первая вершина в коде является нулевой.
Я бы сказал, что в примере этой статьи не 10, а три цикла. Циклы природно отождествлять, если один из другого получается циклической перестановкой.
Проверить, содержит ли неориентированный graph цикл или нет
Для заданного связного неориентированного Graph проверьте, содержит ли он какой-либо цикл или нет.
Например, следующий graph содержит цикл 2–5–10–6–2 :
Рекомендуем прочитать:
1. Использование БФС
Когда мы делаем Поиск в ширину (BFS) из любой вершины v в неориентированном Graph мы можем встретить крест-накрест который указывает на ранее обнаруженную вершину, которая не является ни предком, ни потомком текущей вершины. Каждое “поперечное ребро” определяет цикл в неориентированном Graph. Если поперечный край x —> y , то так как y уже обнаружен, у нас есть путь от v к y (или из y к v так как graph неориентированный), где v является начальной вершиной BFS. Итак, мы можем сказать, что у нас есть путь v
v что образует цикл. (Здесь,
представляет еще одно ребро в пути, и
представляет собой прямое ребро).
Ниже приведена программа на C++, Java и Python, которая демонстрирует это: