Поиск Эйлерова цикла в графе

Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.

Реализовать это можно, например, так, рекурсивно:

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

Для поиска цикла на шаге 1 используем поиск в глубину.

Сложность полученного алгоритма — O(M), то есть линейная относительно количества рёбер М в данном графе.

Построение остовного дерева

Алгоритм Прима.
	Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U. Положить в U любую вершину; // изначально U - пусто. while (V-U не пусто) { Выбрать ребро (u, v) наименьшей стоимости, u из U, v из V-U; Добавить v к U (и убрать из V-U); } Очевидно, данный алгоритм имеет сложность O(V2)
Алгоритм Краскала.
	В отличие от алгоритма Прима, этот алгоритм не требует прохода по всем вершинам для нахождения ребра с минимальным весом. Вместо этого он использует 'жадный' подход. Работаем с вершинами, а не с ребрами G. Это дает нам V связных компонент. Будем увеличивать их размер по ребру за раз. Число ребер, необходимое для остовного дерева: V-1. Граф связен, а значит E содержит как минимум такое их количество. Создаем список вершин L, в неубывающем по весу порядке while (число отмеченных вершин < V-1) { w = L.Remove(); // удалить из головы списка if (w соединяет две несвязных компоненты) отметить w и добавить к MST else // w - внутри компоненты не отмечать w // это приведет к циклу в MST } Сложность алгоритма составляет O(E*lg E).

Выделение связной компоненты графа.

В этом алгоритме три этапа - первоначальная разметка, распространение разметки и формирование результата.

1. Первоначальная разметка

Пометим все вершины первым маркером - нам про них ничего не известно.
Выберем любую вершину (например, первую (или нулевую)), пометим ее вторым маркером, ведь она может быть достигнута сама из себя.

2. Разметка соседних вершин

Если нет вершин, помеченных вторым маркером - переходим к третьему этапу.
Выберем любую вершину, помеченную вторым маркером. Пометим ее третьим маркером. Все вершины, соседние с данной и помеченные первым маркером, пометим вторым маркером.
Повторим этот пункт с начала.

3. Завершение работы

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

32) Формальные языки и грамматики. Определение языка, описание языка. Понятие грамматики.