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

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

Цепью в графе называется последовательность ребер Цепь в графе - vscode.ru, когда каждое предыдущее ребро Предыдущее ребро - vscode.ru соприкасается одним из своих концов со следующим ребром Ребро Ek - vscode.ru. Цепь обозначается последовательностью вершин, которые она содержит (2-5-3-6).

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

Приведем пример. Пусть дан граф, как на рисунке ниже:

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

Все элементарные цепи в нем: 1-2, 1-3-2, 1-2-3, 1-3, 1-2-3-4, 1-3-4, 2-1-3, 2-3, 2-1-3-4, 2-3-4, 3-4.

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

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

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

Множество вершин и ребер можно хранить в виде списков:

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

Модифицируем алгоритм DFS в DFSchain.

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

Хранить результаты поиска будем в списке строк:

Приведем описание DFSchain. В начальный момент времени все вершины графа окрашены в белый цвет. Требуется выполнить следующее:

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

Процедура DFSchain(int u, int endV, List<Edge> E, int[] color, string s).

  • Если номер вершины u не равен endV, значит мы не достигли конца цепи, поэтому перекрашиваем вершину u в черный цвет. Иначе – конец цепи достигнут: добавляем цепь s в список и выполняем возврат из функции.
  • Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, рекурсивно выполняем процедуру DFSchain(w, endV, E, color, s + “-” + (w + 1).ToString()). Возвращаем вершине w белый цвет (возможно через нее проходят другие цепи, поэтому не будем исключать ее из рассмотрения).

Приведем реализацию процедуры DFSchain на языке C#:

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

Результат поиска цепей - vscode.ru

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

 

Оцените статью

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

Добавить комментарий

Ваш 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="">