Структуры данных


Элементарные алгоритмы для работы с графами
    Основные определения (ориентированный/неориентированный граф, входящая/исходящая степень вершины, инцидентность ребра вершине, петли, кратные ребра и т.п.)
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами.
неориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого не присвоено направление.
Степень вершины (англ. degree, также валентность, англ. valency) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды.[1] Степень вершины обозначается как 
Входящая степень вершины v это количество ребер вида (i, v), то есть количество ребер которые «входят» в v.Исходящая степень вершины v это количество ребер вида (v , i), то есть количество ребер которые «выходят» из v
Кратные рёбра — несколько рёбер, инцидентных одной и той же паре вершин. Встречаются в  HYPERLINK "https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2" \l ".D0.BC.D1.83.D0.BB.D1.8C.D1.82.D0.B8.D0.B3.D1.80.D0.B0.D1.84" мультиграфах.
Петля — ребро, начало и конец которого находятся в одной и той же вершине.
    Списки смежности (структура, объем памяти, время доступа к ребру, для каких графов эффективнее)
Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| << |V|2).В данном представлении используется массив Adj содержащий |V| списков. В каждом списке Adj[v] содержатся все вершины u, так что между v и u есть ребро. Память требуемая для представления равна O (|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.Главный недостаток этого способа представления в том, что нет быстрого способа проверить существует ли ребро (u, v). 

    Матрица смежности (структура, объем памяти, время доступа к ребру, для каких графов эффективнее)
Матрица смежности — один из способов представления графа в виде матрицы.
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.
Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно  бит памяти, что может быть на порядок лучше списков смежности.
Время доступа O(n)

    Поиск в ширину (алгоритм, время работы, поиск кратчайшего пути в невзвешенном графе)
Работа алгоритма[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=1" \o "Редактировать раздел \«Работа алгоритма\»" править | править вики-текст]
Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника .Рассмотрим все рёбра , выходящие из узла . Если очередной узел  является целевым узлом, то поиск завершается; в противном случае узел  добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла , из очереди извлекается следующий узел , и процесс повторяется.
Неформальное описание[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=2" \o "Редактировать раздел \«Неформальное описание\»" править | править вики-текст]
Поместить узел, с которого начинается поиск, в изначально пустую очередь.
Извлечь из начала очереди узел  и пометить его как развёрнутый.
Если узел  является целевым узлом, то завершить поиск с результатом «успех».
В противном случае, в конец очереди добавляются все преемники узла , которые ещё не развёрнуты и не находятся в очереди.
Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
Вернуться к п. 2.
Формальное описание[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=3" \o "Редактировать раздел \«Формальное описание\»" править | править вики-текст]
Ниже приведён псевдокод алгоритма для случая, когда необходимо лишь найти целевой узел. В зависимости от конкретного применения алгоритма, может потребоваться дополнительный код, обеспечивающий сохранение нужной информации (расстояние от начального узла, узел-родитель и т. п.)
Рекурсивная формулировка:
BFS(start_node, goal_node) {
return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
if(fringe == ∅) {
// Целевой узел не найден
return false;
}
if (goal_node ∈ fringe) {
return true;
}
return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}
Итеративная формулировка:
BFS(start_node, goal_node) {
for(all nodes i) visited[i] = false; // изначально список посещённых узлов пуст
queue.push(start_node); // начиная с узла-источника
visited[start_node] = true;
while(! queue.empty() ) { // пока очередь не пуста
node = queue.pop(); // извлечь первый элемент в очереди
if(node == goal_node) {
return true; // проверить, не является ли текущий узел целевым
}
foreach(child in expand(node)) { // все преемники текущего узла, ...
if(visited[child] == false) { // ... которые ещё не были посещены ...
queue.push(child); // ... добавить в конец очереди...
visited[child] = true; // ... и пометить как посещённые
}
}
}
return false; // Целевой узел недостижим
}
Свойства[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=4" \o "Редактировать раздел \«Свойства\»" править | править вики-текст]
Обозначим число вершин и рёбер в графе как  и  соответственно.
Пространственная сложность[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=5" \o "Редактировать раздел \«Пространственная сложность\»" править | править вики-текст]
Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет [1].
Алгоритм поиска с итеративным углублением похож на поиск в ширину тем, что при каждой итерации перед переходом на следующий уровень исследуется полный уровень новых узлов, но требует значительно меньше памяти.
Временная сложность[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=6" \o "Редактировать раздел \«Временная сложность\»" править | править вики-текст]
Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет [1][2].
Полнота[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=7" \o "Редактировать раздел \«Полнота\»" править | править вики-текст]
Если у каждого узла имеется конечное число преемников, алгоритм является полным: если решение существует, алгоритм поиска в ширину его находит, независимо от того, является ли граф конечным. Однако если решения не существует, на бесконечном графе поиск не завершается.
Оптимальность[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&veaction=edit&vesection=8" \o "Редактировать раздел \«Оптимальность\»" править | править вики-текст]
Если длины рёбер графа равны между собой, поиск в ширину является оптимальным, то есть всегда находит кратчайший путь. В случае взвешенного графа поиск в ширину находит путь, содержащий минимальное количество рёбер, но не обязательно кратчайший.
Поиск по критерию стоимости является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует очередь с приоритетами.
    Поиск в глубину (алгоритм, классификация ребер, поиск циклов, время работы)
Алгоритм поиска в глубину[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83&veaction=edit&vesection=1" \o "Редактировать раздел \«Алгоритм поиска в глубину\»" править | править вики-текст]
Пусть задан граф , где  — множество вершин графа,  — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
Пройдём по всем вершинам .Если вершина  белая, выполним для неё DFS(v).
Процедура DFS (параметр — вершина )Перекрашиваем вершину  в серый цвет.
Для всякой вершины , смежной с вершиной  и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)[2].
Перекрашиваем вершину  в чёрный цвет.
Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.
Нерекурсивные варианты[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83&veaction=edit&vesection=2" \o "Редактировать раздел \«Нерекурсивные варианты\»" править | править вики-текст]
На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.
Первый вариант: можно сэмулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер  и номер текущей смежной вершины .
Процедура DFS (параметр — вершина )Кладём на стек пару . Перекрашиваем вершину  в серый цвет.
Пока стек не пуст…
Берём верхнюю пару , не извлекая её из стека.
Находим вершину , смежную с  и следующую за .
Если таковой нет, извлекаем  из стека, перекрашиваем вершину  в чёрный цвет.
В противном случае присваиваем , прямо в стеке.
Если к тому же вершина  белая, кладём на стек пару , перекрашиваем  в серый цвет.
Второй вариант: можно в каждой из «серых» вершин держать текущее  и указатель на предыдущую (ту, из которой пришли).
Третий вариант работает, если хватает двухцветных меток.
Процедура DFS (параметр — вершина )Кладём на стек вершину .Пока стек не пуст…
Берём верхнюю вершину .Если она белая…
Перекрашиваем её в чёрный цвет.
Кладём в стек все смежные с  белые вершины.
Общая идея
Общая идея алгоритма состоит в следующем: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
[править]Пошаговое представление
Выбираем любую вершину из еще не пройденных, обозначим ее как .Запускаем процедуру 
Помечаем вершину  как пройденную
Для каждой не пройденной смежной с  вершиной (назовем ее ) запускаем 
Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными.
[править]Реализация
vector<bool> visited; //вектор для хранения информации о пройденных и не пройденных вершинах
void dfs(int u)
{
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}
int main()
{
... //задание графа G с количеством вершин n.
visited.assign(n, false); //в начале все вершины в графе не пройденные
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}
[править]Время работы
Оценим время работы обхода в глубину. Процедура  вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра . Всего таких ребер для всех вершин в графе , следовательно, время работы алгоритма оценивается как .
[править]Цвета вершин
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.Поэтому в процессе алгоритма вершинам задают некоторые цвета:
если вершина белая, значит, мы в ней еще не были, вершина не пройдена;
серая — вершина проходится в текущей процедуре ;черная — вершина пройдена, все итерации  от нее завершены.
Такие "метки" в основном используются при поиске цикла.
Топологическая сортировка и сильно связные компоненты
    Определение топологической сортировки
Упорядочивание вершин  HYPERLINK "https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84" \o "Направленный ациклический граф" бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети. 
↑ Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка
Из рисунка видно, что граф не отсортирован, так как ребро из вершины с номером 4 ведет в вершину с меньшим номером (2).Существует несколько способов топологической сортировки — из наиболее известных:
Алгоритм ДемукронаМетод сортировки для представления графа в виде нескольких уровнейМетод топологической сортировки с помощью обхода в глубину
Я остановлюсь на рассмотрении последнего, поскольку он наиболее популярен, нагляден и прост в реализации. 
    Алгоритм построения топологической сортировки
Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную.
Пусть дан бесконтурный ориентированный простой граф . Через  обозначим множество вершин таких, что . То есть,  — множество всех вершин, из которых есть дуга в вершину . Пусть  — искомая последовательность вершин.
пока
выбрать любую вершину такую, что и

удалить из всех
Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .Пример работы алгоритма[править | править вики-текст]

Пусть задан граф . В таком случае алгоритм выполнится следующим образом:
шаг
0
1
2
3
4
5
На втором шаге вместо  может быть выбрана вершина , поскольку порядок между  и  не задан.
    Доказательство корректности работы алгоритма топологической сортировки
    На каких графах можно построить топологическую сортировку
    Определение сильно связных компонентов
Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связны. Две вершины s и t любого графа сильно связны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы.
    Алгоритм построения сильно связных компонентов
Орграф, не принадлежащий к классу сильно связных графов, содержит некоторый набор сильно связных компонент, и некоторый набор ориентированных ребер, идущих от одной компоненты к другой.
Любая вершина орграфа сильно связна сама с собой.
Алгоритмы[править | править вики-текст]
Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:
При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.
Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.
Поиск компонент связности такого неориентированного графа даст нам компоненты сильной связности нашего орграфа.
Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.
Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмыКосарайю,  HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D0%B0%D0%B1%D0%BE%D0%B2%D0%B0&action=edit&redlink=1" \o "Алгоритм Габова (страница отсутствует)" Габова и  HYPERLINK "https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0" \o "Алгоритм Тарьяна" Тарьяна.
    Граф компонентов (конденсация графа)
Конденсацией орграфа  называют орграф , вершинами которого служат сильные компоненты , а дуга в  показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
Минимальные остовные деревья (МST)
    Определение
    Общая схема построения
    Безопасные ребра 
Введение
В статье рассматривается задача о построении минимального остовного дерева (minimum-spanning-tree problem). В начале статьи дано общее описание проблемы и история подходов к ее решению. Далее описан базовый алгоритм и некоторые теоретические сведения о минимальных остовных деревьях. В конце статьи представлены основные алгоритмы (Крускал, Прим, Борувка).
Постановка задачи
Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?
В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (контактов), аE — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). w() называется весовой функцией. Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.
Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер w(T) = ∑(u,v)∈T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

Рис. 1. Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.
Так как рассматриваются только деревья, можно считать все ребра положительными (достаточно добавить к весу всех ребер некоторую относительно большую положительную константу). В противном случае, если стоимость соединения между двумя вершинами равна отрицательному числу, можно несколько раз параллельно соединить их для уменьшения суммарного веса остовного подграфа.

Рис.2-а. Минимальное остовное дерево.Суммарный вес равен 3. Рис.2-б. Минимальный покрывающий подграф.Суммарный вес равен 0.
Также считаем, что для любой пары ребер их весовые характеристики будут различны. Это гарантирует уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным (с суммарным весом v-1, где v – количество вершин в графе).


Рис.3. Все возможные минимальные остовные деревья для данного графа.
В данном случае, любой алгоритм построит одно из минимальных остовных деревьев. Один из вариантов разрешения неопределенности заключается в модификации алгоритма сравнения ребер по весу, например, так:
SHORTER-EDGE(i;j;k;l)1: if w(i,j) < w(k,l) then return (i,j)2: if w(i,j) > w(k,l) then return (k,l)3: if min(i,j) < min(k,l) then return (i,j)4: if min(i,j) > min(k,l) then return (k,l)5: if max(i,j) < max(k,l) then return (i,j)6: return (k,l)    Теорема о легком ребре, пересекающем разрез, согласованный по ребрам с текущим подмножеством MST 
    Алгоритм Прима (время работы с кучей и с массивом, для каких графов что эффективнее)
При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет наращиваться минимальный остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Ω. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на ноду дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько).
Тогда алгоритм Прима выглядит следующим образом:
MST-PRIM(G,w, r)1: Ω ← V[G]2: foreach (для каждой) вершины u ∈ Ω3:     do key[u] ← ∞4: key[r] ← 05: p[r] = NIL6: while (пока) Ω ≠ 07:     do u ← EXTRACT-MIN(Ω)8:        foreach (для каждой) вершины v ∈ Adj(u)9:            do if v ∈ Ω и w(u,v) < key[v] then10:               p[v] ← u11:               key[v] ← w(u,v)
На рисунках П1-П8 показана схема работы алгоритма Прима с корнем r.
Рис. П1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер. Рис. П2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.
Рис. П3. Следующее безопасное ребро с весом 11. Добавляем его. Рис. П4.
Рис. П5. Рис. П6.
Рис. П7. Рис. П8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Время работы алгоритма Прима зависит от того, как реализована очередь с приоритетами Ω. Если использовать двоичную кучу, инициализацию в строках 1-4 можно выполнить за время O(V). Далее цикл выполняется |V| раз, и каждая операция EXTRACT-MIN занимает время O(VlogV). Цикл for в строках 8-11 выполняется в общей сложности O(E), поскольку сумма степеней вершин графа равна 2|E|. Проверку принадлежности в строке 9 можно выполнить за время O(1), если хранить состояние очереди еще и как битовый вектор размера |V|. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (DECREASE-KEY), которая для двоичной кучи может быть выполнена за время O(logV). Таким образом всего получаем O(VlogV+ElogV)=O(ElogV).
Лучшую оценку можно получить, если использовать фибоначчиевы кучи. С помощью фибоначчиевых куч можно выполнить операцию EXTRACT-MIN за учетное время O(logV), а операцию DECREASE-KEY – за учетное время O(1). В этом случае суммарное время работы алгоритма Прима составит O(E+VlogV).
   
Кратчайшие пути 
    Определение кратчайшего пути
В задаче о кратчайшем пути (shortest-paths problem) задается взвешенный ориентированный граф G = (V, Е) с весовой функцией w : Е → R, отображающей ребра на их веса, значения которых выражаются действительными числами.
Вес (weight) пути р = (vo, vi,..., vk) равен суммарному весу входящих в него ребер:

Вес кратчайшего пути (shortest-path weight) из вершины u в вершину v определяется соотношением

Если пути из u в v не существует, то кратчайший путь равен ∞ Тогда по определению кратчайший путь (shortest path) из вершины и в вершину v — это любой путь, вес которого удовлетворяет соотношению w(u,v)=δ(u,v) Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику. Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму.
    Лемма о частичных путях (подпутях) кратчайшего пути
Лемма (Частичные пути кратчайшего пути являются кратчайшими путями.) Пусть р = (v1, v2..., vk) - кратчайший путь из вершины v1 к вершине vk в заданном взвешенном ориентированном графе G = (V, Е) с весовой функцией w : Е → R, a pij = (vi, vi+i,..., vj) — частичный путь пути р, который проходит из вершины vi к вершине vj для произвольных i и j, удовлетворяющих неравенству 1≤ i ≤ j ≤ k. Тогда pij — кратчайший путь из вершины vi к вершине vj.
Доказательство. Если разложить путь р на составные части
то будет выполняться соотношение w(p) = w(p1i) + w(pij) + w(pik).
Теперь предположим, что существует путь рij 1 из вершины Vi к вершине Vj, вес которого удовлетворяет неравенству w (рij 1 )< w(рij )
Тогда — путь из вершины v1 к вершине vk, вес которого w(p1i) + w(pij 1 ) + w(pik) меньше веса w (р). Это противоречит предположению о том, что р — кратчайший путь из вершины v1 к вершине vk    Циклы с отрицательным весом
Без потери общности можно предположить, что если ведется поиск кратчайших путей, они не содержат циклов. Поскольку в любой ациклический путь в графе G = (V,E) входит не более |V| различных вершин, в нем также содержится не более |V| — 1 ребер. Таким образом, можно ограничиться рассмотрением кратчайших путей, состоящих не более чем из |V| — 1 ребер.
Пусть G = (V, Е) — взвешенный ориентированный граф с весовой функцией w : Е → R. Предположим, что в нем не содержится циклов с отрицательным весом, достижимых из истока s ∈ V а следовательно, кратчайшие пути вполне определены. Тогда дерево кратчайших путей (shortest-paths tree) с корнем в вершине s — это ориентированный подграф G1 = (V1, Е1'),
в котором множества V1 ⊆ V и Е1⊆ Е определяются такими условиями:
1. V — множество вершин, достижимых из истока s графа G;
2. граф G1 образует корневое дерево с корнем в вершине s;
3. для всех v∈V однозначно определенный простой путь из вершины s в вер- вершину v в графе G1 совпадает с кратчайшим путем из вершины s в вершину v в графе G.
Кратчайшие пути, как и деревья кратчайших путей, не обязательно единственны. Например, на рисунке изображен взвешенный ориентированный граф, на котором обозначен вес каждого из кратчайших путей из истока s а также два дерева кратчайших путей с корнем s

    Ослабление ребра
В описанных в этой главе алгоритмах используется метод релаксации, или ослабления (relaxation). Для каждой вершины v∈V поддерживается атрибут d[v], представляющий собой верхнюю границу веса, которым обладает кратчайший путь из истока s в вершину v. Назовем атрибут d[v] оценкой кратчайшего пути (shortest-path estimate). Инициализация оценок кратчайших путей и предшественников производится в приведенной ниже процедуре, время работы которой равно Θ(V):
Initialize_Single_Source(G, s)
1 for (Для) каждой вершины v ∈ V[G]
2 do d[v]←∞
3 π[v] ← NIL 4 d[s]← 0
После инициализации для всех v ∈ V π [v] = NIL, d [s] = 0
и для всех v ∈ V — {s} d [v] = ∞
Процесс релаксации (relaxation) или ослабления ребра (π[v]) заключается в проверке, нельзя ли улучшить найденный до сих пор кратчайший путь к вершине v, проведя его через вершину u, а также в обновлении атрибутов d[v] и π[v] при наличии такой возможности улучшения. Ослабление может уменьшить оценку кратчайшего пути d[v] и обновить поле π[v] вершины v. Приведенный ниже код выполняет ослабление ребра (u,v):
Relax(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u) + w(u, v)
3 π[v] ← u
Ниже приведены два примера ослабления ребра; в одном из этих примеров оценка кратчайшего пути понижается, а в другом — не происходит никаких изменений, связанных с оценками. В каждой вершине на рисунке приводится оценка кратчайшего пути к этой вершине. В примере, приведенном в части а) рисунка, перед ослаблением выполняется неравенство d[v] > d[u] + w{u,v), поэтому в результате ослабления значение d[v] уменьшается. В части б) рисунка перед ослаблением выполняется неравенство d[v] ≤ d[u] + w(u,v), поэтому значение d[v] остается неизменным.
В каждом из рассмотренных ниже алгоритмов сначала вызывается процедура Initialize_Single__Source, а затем производится ослабление ребер. Более того, ослабление — единственная операция, изменяющая оценки кратчайших путей и предшественников. Описанные ниже алгоритмы различаются тем, сколько раз в них производится ослабление ребер, а также порядком ребер, над которыми выполняется ослабление. В алгоритме Дейкстры и алгоритме поиска кратчайших путей в ориентированных ациклических графах каждое ребро ослабляется ровно по одному разу. В алгоритме Беллмана-Форда (Bellman-Ford) каждое ребро ослабляется по несколько раз. Алгоритм Беллман

    Свойства кратчайших путей и ослаблений (стр. 671), особенно свойство ослабления пути
    Алгоритм Беллмана-Форда
За время O(|V| × |E|)
Давайте придумаем что-нибудь простое
Рассмотрим какое-нибудь ребро (v, w). Что мы можем сказать про расстояния до его концов? Очевидно, dist[u, w] ≤ dist[u, v] + weight[v, w].
Доказательство
Давайте будем действовать итерационно. Изначально известно расстояние только до начальной вершины — оно равно 0. В каждый момент времени мы можем проверить выполнение свойства для какого-нибудь ребра и, если оно нарушено, улучшить существующую оценку расстояния до конечной вершины ребра. Это процедура называется релаксацией.

А если я педант?
Давайте докажем, что после k итераций алгоритм найдет все кратчайшие пути, состоящие из k ребер или менее. Тогда получится, что в конце работы он найдет все кратчайшие пути из не более, чем V ребер — то есть, все существующие кратчайшие пути.Для удобства обозначим начальную вершину u.
База: k = 0 очевидно, путь из начальной вершины в нее же найден верно
Предположение: после k итераций для всех вершин v, до которых существует кратчайший путь, состоящий из не более, чем k ребер, dist[v] равно расстоянию от начальной вершины до v
Шаг: рассмотрим некоторую вершину w, до которой существует кратчайший путь, состоящий из k + 1 ребра.
Обозначим предпоследнюю вершину в пути от u до w, как v.
Для v существует кратчайший путь из k вершин (например, начало кратчайшего пути до w).
Значит, кратчайший путь до v был найден на предыдущей итерации. Проведя релаксацию ребра (v, w) на k + 1-ой итерации, мы получим верное значение расстояния до вершины w.
Заметим, что при релаксации какого-либо другого ребра мы не могли получить значения, меньшего, чем верное расстояние, поскольку каждой релаксации ребра (x, w) можно поставить в соответствие путь из начальной вершины в w соответствующей длины.
    Алгоритм поиска кратчайших путей с помощью топологической сортировки
полное время работы алгоритма равно Θ(V + Е)
Ослабляя ребра взвешенного ориентированного ациклического графа G= (V, Е) в порядке, определенном топологической сортировкой его вершин, кратчайшие пути из одной вершины можно найти в течение времени Θ(V + Е). В ориентированном ациклическом графе кратчайшие пути всегда вполне определены, поскольку даже если у некоторых ребер вес отрицателен, циклов с отрицательными весами не существует.
Работа алгоритма начинается с топологической сортировки ориентированного ациклического графа, чтобы установить линейное упорядочение вершин. Если путь из вершины u к вершине v существует, то в топологической сортировке вершина u предшествует вершине v. По вершинам, расположенным в топологическом порядке, проход выполняется только один раз. При обработке каждой вершины производится ослабление всех ребер, исходящих из этой вершины.
Dag_Shortest_Paths(G, w, s)
1 Топологическая сортировка вершин графа G
2 Initialize_Single_Source(G, s)
3 for (для) каждой вершины u в порядке топологической сортировки
4 do for (Для) каждой вершины v∈Adj[u]
5 do Relax(u, v, w)

    Алгоритм Дейкстры (с кучей и с массивом)
О(V2 ) массив
Θ(VlogV + ЕlogE)куча
Алгоритм Дейкстры решает задачу о кратчайшем пути из одной вершины во взвешенном ориентированном графе G = (V, Е) в том случае, когда веса ребер неотрицательны. Поэтому в настоящем разделе предполагается, что для всех ребер (u, v) ∈ Е выполняется неравенство w (u, v) ≥ 0. При хорошей реализации алгоритм Дейкстры производительнее, чем алгоритм Беллмана-Форда.
В алгоритме Дейкстры поддерживается множество вершин S, для которых уже вычислены окончательные веса кратчайших путей к ним из истока s. В этом алгоритме поочередно выбирается вершина u∈ V — S, которой на данном этапе соответствует минимальная оценка кратчайшего пути. После добавления этой вершины u в множество S производится ослабление всех исходящих из нее ребер. В приведенной ниже реализации используется неубывающая очередь с приоритетами Q, состоящая из вершин, в роли ключей для которых выступают значения d.
Dijkstra(G, w ,s)
1. Initialize _Single_ Source(G,s)
2. S←0
3. Q ← V[G]
4. while Q ≠ ∅ 5. do u ← Extract Min(Q)
6. S←-S∪ {u}
7. for (для) каждой вершины v∈Adj[u]
8. do Relax(u, v, w)
9.
Процесс ослабления ребер в алгоритме Дейкстры проиллюстрирован на Рисунке. Исток s расположен на рисунке слева от остальных вершин. В каждой вершине приведена оценка кратчайшего пути к ней, а выделенные ребра указывают предшественников. Черным цветом обозначены вершины, добавленные в множество S, а белым — содержащиеся в неубывающей очереди с приоритетами Q = V — S. В части а рисунка проиллюстрирована ситуация, сложившаяся непосредственно перед выполнением первой итерации цикла while в строках 4-8. Выделенная серым цветом вершина имеет минимальное значение d и выбирается в строкt 5 в качестве вершины u для следующей итерации. В частях б-е изображены ситуации после выполнения очередной итерации цикла while. В каждой из этих частей выделенная серым цветом вершина выбирается в качестве вершины u в строке 5. В части е приведены конечные значения величин d и π.

    Кратчайшие пути между всеми парами вершин:
Рассматривается задача о поиске кратчайших путей между всеми парами вершин графа. Эта задача может возникнуть, например, при составлении таблицы расстояний между всеми парами городов, нанесенных на атлас дорог.
В этой задаче задается взвешенный ориентированный граф G = (V,E) с весовой функцией w : Е → R, отображающей ребра на их веса, выраженные действительными числами. Для каждой пары вершин u, v ∈V требуется найти кратчайший (обладающий наименьшим весом) путь из вершины u в вершину v, вес которого определяется как сумма весов входящих в него ребер. Обычно выходные данные представляются в табличной форме: на пересечении строки с индексом u и столбца с индексом v расположен вес кратчайшего пути из вершины u в вершину v.
алгоритм ФлойдаРассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны:
кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;
кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;
кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин.
Алгоритм
Перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j  которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента di,iравным 0.
Для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1элементы DmАлгоритм заканчивается получением матрицы всех кратчайших путей DN, N – число вершин графа.
 Напомним, для определения по известным элементам матрицы Dm-1 элементов матрицы  Dm в алгоритме Флойда применяется рекурсивное соотношение:
di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}
di,jm – элемент матрицы Dm, di,jm-1 – элементы матрицы Dm-1 найденой на предыдущем шаге алгоритма.



Задача о максимальном потоке
    Транспортная сеть
Определение:
Сеть (англ. flow network)  представляет собой ориентированный граф, в котором каждое ребро  имеет неотрицательную пропускную способность(англ. capacity) . Если , предполагается что .
В транспортной сети выделяются две вершины: исток  и сток .
[править]Определение потока
Определение:
Потоком (англ. flow)  в  является действительная функция , удоволетворяющая условиям:
1)  (антисимметричность);
2)  (ограничение пропускной способности), если ребра нет, то ;
3)  для всех вершин , кроме  и  (закон сохранения потока).
Величина потока  определяется как .
Также существует альтернативное определение (по Асанову), не вводящее антисимметричность (зачастую, из-за этого с ним труднее работать):
Определение:
Потоком  в сети  называется функция , удоволетворяющая условиям:
1)  для всех ;2)  для всех , где .
Здесь  — источник, а  — сток сети  ( имеет нулевую степень захода, а  имеет нулевую степень исхода); через  обозначено множество вершин, к которым идутдуги из вершины ; через  обозначено множество вершин, из которых идут дуги в вершину ;  называется пропускной способностью дуги  и неотрицательно.
Число  можно интерпретировать, например, как количество жидкости, поступающей из  в  по дуге . С этой точки зрения значение  может быть интерпретировано как поток, втекающий в вершину , а  — вытекающий из . Условие 1) называется условием ограничения по пропускной способности, а условие 2) — условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину , отличную от  или , равен вытекающему из неё потоку.
[править]Пример
Пример сети с источником  и стоком .

Первое число означает величину потока, второе — пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности: ). Сумма входящих ребер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем . Кроме того, величина потока на ребре никогда не превышает пропускную способность этого ребра.
Величина потока в этом примере равна  (считаем от вершины ).
Поток через любой разрез равен сумме потоков из источника.Доказательство: пускай есть разрез (A,B). Рассмотрим сумму всех потоков из всех вершин, принадлежащих А. Она равна

В первой из сумм для любой пары вершин (u, v) есть два слагаемых f(u, v) и f(v, u), равных по модулю и противоположных по знаку. Следовательно, эта сумма равна нулю. Вторая сумма есть поток через разрез (A,B). Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна потоку через разрез. С другой стороны, сумма потоков из любой вершины, кроме s и t, равна нулю, а . Следовательно, сумма всех потоков из всех вершин, принадлежащих А, равна сумме потоков из s. Следовательно, поток через разрез (A,B) равен сумме потоков из s, что и требовалось доказать.
Сумма потоков из источника равна сумме потоков в сток.Доказательство: рассмотрим разрез . Поток через этот разрез равен сумме потоков в сток. С другой стороны, по только что доказанному, поток через этот (как и любой другой) разрез равен сумме потоков из источника. Теорема доказана.
Максимальный поток положителен тогда и только тогда, когда существует путь из источника в сток, проходящий по рёбрам с положительной пропускной способностью.Доказательство: Пускай такой путь P существует. Пусть c — минимальная из пропускных способностей рёбер, принадлежащих P. Пускай поток равен c на всех рёбрах из P, и нулю на всех остальных рёбрах. Тогда суммарный поток из источника равен c, то есть положителен. Теперь допустим, что такого пути нет, то есть t недостижимо из s по рёбрам с положительной пропускной способностью. Пусть A — множество вершин, достижимых из s по таким рёбрам, B — недостижимых. Тогда, поскольку , , то (A,B) является разрезом. Кроме того, не существует ребра (a, b) с положительной пропускной способностью, такого что , , иначе b было бы достижимо из s. Следовательно, пропускная способность разреза (A,B) равна нулю, а значит и поток через него всегда равен нулю. Следовательно, сумма потоков из источника всегда равна нулю.
Поток максимален тогда и только тогда, когда нет увеличивающего пути в остаточной сети. Доказательство: пускай такой путь P есть. Пусть c — минимальная из остаточных пропускных способностей рёбер, принадлежащих P, в остаточной сети. Для всех пар  увеличим f(u, v) на c и уменьшим f(v, u) на c. Мы увеличили суммарный поток из источника на c, следовательно, он был не максимален. Теперь, наоборот, допустим, что такого пути нет. Докажем от противного, что поток f в исходной сети обеспечивает максимальный суммарный поток из s. Пусть это не так, тогда есть поток f', обеспечивающий больший суммарный поток из s. Легко убедиться, что f'-f — поток в остаточной сети, обеспечивающий в ней положительный суммарный поток из s. Следовательно, в остаточной сети есть путь из источника в сток, то есть увеличивающий путь. Мы получили противоречие.
Теорема Форда-Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.Доказательство: сумма потоков из s равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть A — множество вершин, достижимых из источника в остаточной сети, B — недостижимых. Тогда, поскольку , , то (A,B) является разрезом. Кроме того, в остаточной сети не существует ребра (a, b) с положительной пропускной способностью, такого что , , иначе бы b было достижимо из s. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез (A,B) равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. Значит, максимальный поток равен пропускной способности разреза (A,B), которая не меньше пропускной способности минимального разреза. Теорема доказана.
    Формальное определение потока
Определение:
Потоком (англ. flow)  в  является действительная функция , удоволетворяющая условиям:
1)  (антисимметричность);
2)  (ограничение пропускной способности), если ребра нет, то ;
3)  для всех вершин , кроме  и  (закон сохранения потока).
Величина потока  определяется как .
    Сеть с несколькими источниками и стоками (сведение к сети с одним источником и одним стоком)
Пусть в сети в общем случае имеется несколько истоков и стоков. Стоки и истоки занимают в сети крайние положения. Все остальные вершины могут быть дальше или ближе к ним. Расположение вершины в сети определяется ее уровнем. Определим это понятие. Вершины уровня 0 — это истоки; они образуют множество N0. Если Ni — множество вершин уровня i 6 k, то Nk+1 — множество вершин уровня k +1 состоящее из тех и только тех вершин, предшественники которых принадлежат любому из множеств N0,...,Nk, причем среди этих множеств нет пустых [3].
Порядковой функцией сети называют отображение, сопоставляющее каждой вершине сети ее уровень.
Задача. Найти порядковую функцию сети (рис. 4.8).


Ответы
№ Порядковая функция
а 4, 3, 7, 9, 6, 5, 1, 8, 2
б 8, 7, 5, 4, 6, 9, 2, 1, 3
в (2, 6), 3, 5, 7, 8, 4, 9, 1
г (4, 8), 2, 6, 1, 7, 5, 3, 9
д 9, 3, (1, 7, 4, 5), 6, 8, 2
е 1, 2, (7, 3, 4, 5), 6, 8, 9
ж (5, 6, 2, 9), (4, 7, 8), 3, 1
з (2, 5, 4), (8, 6, 7, 9), (3, 1)
и (4, 8), (5, 9), (6, 2), (1, 3), 7
Пример. Отсортировать топологически сеть на рис. 4.9.

Решение. Находим вершины (4 и 9), полустепень захода которых равна 0. Удаляем эти вершины и дуги, выходящие из них [3]. Удаленные вершины образуют первый уровень упорядоченной сети. Получаем новую сеть (рис. 4.10). В новой сети в вершины 1, 5 и 8 не входят дуги. Удаляем1264992429772
1
3
4
5
6
7
8
9
2
1
3
4
5
6
7
8
9
эти вершины (они образуют второй уровень) и получаем сеть, изображенную на рис. 4.11. Очевидно, третий уровень состоит из вершин 2, 3 и 6, а последний (сток сети) — из единственной вершины 7. Изображаем ту же сеть по уровням (рис. 4.12).
Рис. 4.12
    Остаточные сети 
Остаточная сеть (residual network) — граф , где  — множество рёбер с положительной остаточной пропускной способностью. В остаточной сети может быть ребро из  в , даже если его нет в исходной сети. Это выполняется, когда в исходной сети есть обратное ребро  и поток по нему положителен.
    Увеличивающие пути
Дан неориентированный невзвешенный граф  с  вершинами. Требуется найти в нём наибольшее паросочетание, т.е. такое наибольшее (по мощности) множество  его рёбер, что никакие два ребра из выбранных не инцидентны друг другу (т.е. не имеют общих вершин).
В отличие от случая двудольного графа (см. Алгоритм Куна), в графе  могут присутствовать циклы нечётной длины, что значительно усложняет поиск увеличивающих путей.
Приведём сначала теорему Бержа, из которой следует, что, как и в случае двудольных графов, наибольшее паросочетание можно находить при помощи увеличивающих путей.
Увеличивающие пути. Теорема Бержа
Пусть зафиксировано некоторое паросочетание . Тогда простая цепь  называется чередующейся цепью, если в ней рёбра по очереди принадлежат - не принадлежат паросочетанию . Чередующаяся цепь называется увеличивающей, если её первая и последняя вершины не принадлежат паросочетанию. Иными словами, простая цепь  является увеличивающей тогда и только тогда, когда вершина , ребро , ребро , ..., ребро , и вершина .

Теорема Бержа (Claude Berge, 1957 г.). Паросочетание  является наибольшим тогда и только тогда, когда для него не существует увеличивающей цепи.
Доказательство необходимости. Пусть для паросочетания  существует увеличивающая цепь . Покажем, как перейти к паросочетанию большей мощности. Выполним чередование паросочетания  вдоль этой цепи , т.е. включим в паросочетание рёбра , , ..., , и удалим из паросочетания рёбра , , ..., . В результате, очевидно, будет получено корректное паросочетание, мощность которого будет на единицу выше, чем у паросочетания  (т.к. мы добавили  рёбер, а удалили  ребро).
Доказательство достаточности. Пусть для паросочетания  не существует увеличивающей цепи, докажем, что оно является наибольшим. Пусть — наибольшее паросочетание. Рассмотрим симметрическую разность  (т.е. множество рёбер, принадлежащих либо , либо , но не обоим одновременно). Покажем, что  содержит одинаковое число рёбер из  и  (т.к. мы исключили из  только общие для них рёбра, то отсюда будет следовать и ). Заметим, что  состоит только из простых цепей и циклов (т.к. иначе одной вершине были бы инцидентны сразу два ребра какого-либо паросочетания, что невозможно). Далее, циклы не могут иметь нечётную длину (по той же самой причине). Цепь в  также не может иметь нечётную длину (иначе бы она являлась увеличивающей цепью для , что противоречит условию, или для , что противоречит его максимальности). Наконец, в чётных циклах и цепях чётной длины в  рёбра поочерёдно входят в  и , что и означает, что в  входит одинаковое количество рёбер от  и . Как уже упоминалось выше, отсюда следует, что , т.е.  является наибольшим паросочетанием.
Теорема Бержа даёт основу для алгоритма Эдмондса — поиск увеличивающих цепей и чередование вдоль них, пока увеличивающие цепи находятся.
Алгоритм Эдмондса. Сжатие цветков
Основная проблема заключается в том, как находить увеличивающий путь. Если в графе имеются циклы нечётной длины, то просто запускать обход в глубину/ширину нельзя.
Можно привести простой контрпример, когда при запуске из одной из вершин алгоритм, не обрабатывающий особо циклы нечётной длины (фактически, Алгоритм Куна) не найдёт увеличивающий путь, хотя должен. Это цикл длины 3 с висящим на нём ребром, т.е. граф 1-2, 2-3, 3-1, 2-4, и ребро 2-3 взято в паросочетание. Тогда при запуске из вершины 1, если обход пойдёт сначала в вершину 2, то он "упрётся" в вершину 3, вместо того чтобы найти увеличивающую цепь 1-3-2-4. Правда, на этом примере при запуске из вершины 4 алгоритм Куна всё же найдёт эту увеличивающую цепь.

Тем не менее, можно построить граф, на котором при определённом порядке в списках смежности алгоритм Куна зайдёт в тупик. В качестве примера можно привести такой граф с 6 вершинами и 7 рёбрами: 1-2, 1-6, 2-6, 2-4, 4-3, 1-5, 4-5. Если применить здесь алгоритм Куна, то он найдёт паросочетание 1-6, 2-4, после чего он должен будет обнаружить увеличивающую цепь 5-1-6-2-4-3, однако может так и не обнаружить её (если из вершины 5 он пойдёт сначала в 4, и только потом в 1, а при запуске из вершины 3 он из вершины 2 пойдёт сначала в 1, и только затем в 6).

Как мы увидели на этом примере, вся проблема в том, что при попадании в цикл нечётной длины обход может пойти по циклу в неправильном направлении. На самом деле, нас интересуют только "насыщенные" циклы, т.е. в которых имеется  насыщенных рёбер, где длина цикла равна . В таком цикле есть ровно одна вершина, не насыщенная рёбрами этого цикла, назовём её базой (base). К базовой вершине подходит чередующийся путь чётной (возможно, нулевой) длины, начинающийся в свободной (т.е. не принадлежащей паросочетанию) вершине, и этот путь называется стеблем (stem). Наконец, подграф, образованный "насыщенным" нечётным циклом, называется цветком (blossom).

Идея алгоритма Эдмондса (Jack Edmonds, 1965 г.) - в сжатии цветков (blossom shrinking). Сжатие цветка — это сжатие всего нечётного цикла в одну псевдо-вершину (соответственно, все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине). Алгоритм Эдмондса ищет в графе все цветки, сжимает их, после чего в графе не остаётся "плохих" циклов нечётной длины, и на таком графе (называемом "поверхностным" (surface) графом) уже можно искать увеличивающую цепь простым обходом в глубину/ширину. После нахождения увеличивающей цепи в поверхностном графе необходимо "развернуть" цветки, восстановив тем самым увеличивающую цепь в исходном графе.
Однако неочевидно, что после сжатия цветка не нарушится структура графа, а именно, что если в графе  существовала увеличивающая цепь, то она существует и в графе , полученном после сжатия цветка, и наоборот.
Теорема Эдмондса. В графе  существует увеличивающая цепь тогда и только тогда, когда существует увеличивающая цепь в .
Доказательство. Итак, пусть граф  был получен из графа  сжатием одного цветка (обозначим через  цикл цветка, и через соответствующую сжатую вершину), докажем утверждение теоремы. Вначале заметим, что достаточно рассматривать случай, когда база цветка является свободной вершиной (не принадлежащей паросочетанию). Действительно, в противном случае в базе цветка оканчивается чередующийся путь чётной длины, начинающийся в свободной вершине. Прочередовав паросочетание вдоль этого пути, мощность паросочетания не изменится, а база цветка станет свободной вершиной. Итак, при доказательстве можно считать, что база цветка является свободной вершиной.
Доказательство необходимости. Пусть путь  является увеличивающим в графе . Если он не проходит через , то тогда, очевидно, он будет увеличивающим и в графе . Пусть  проходит через . Тогда можно не теряя общности считать, что путь  представляет собой некоторый путь , не проходящий по вершинам , плюс некоторый путь , проходящий по вершинам  и, возможно, другим вершинам. Но тогда путь будет являться увеличивающим путём в графе , что и требовалось доказать.
Доказательство достаточности. Пусть путь  является увеличивающим путём в графе . Снова, если путь  не проходит через , то путь без изменений является увеличивающим путём в , поэтому этот случай мы рассматривать не будем.
Рассмотрим отдельно случай, когда  начинается со сжатого цветка , т.е. имеет вид . Тогда в цветке  найдётся соответствующая вершина , которая связана (ненасыщенным) ребром с . Осталось только заметить, что из базы цветка всегда найдётся чередующийся путь чётной длины до вершины . Учитывая всё вышесказанное, получаем, что путь  является увеличивающим путём в графе .
Пусть теперь путь  проходит через псевдо-вершину , но не начинается и не заканчивается в ней. Тогда в  есть два ребра, проходящих через , пусть это  и . Одно из них обязательно должно принадлежать паросочетанию , однако, т.к. база цветка не насыщена, а все остальные вершины цикла цветка  насыщены рёбрами цикла, то мы приходим к противоречию. Таким образом, этот случай просто невозможен.
Итак, мы рассмотрели все случаи и в каждом из них показали справедливость теоремы Эдмондса.
Общая схема алгоритма Эдмондса принимает следующий вид:
void edmonds() {
for (int i=0; i<n; ++i)
if (вершина i не в паросочетании) {
int last_v = find_augment_path (i);
if (last_v != -1)
выполнить чередование вдоль пути из i в last_v;
}
}
 
int find_augment_path (int root) {
обход в ширину:
int v = текущая_вершина;
перебрать все рёбра из v
если обнаружили цикл нечётной длины, сжать его
если пришли в свободную вершину, returnесли пришли в несвободную вершину, то добавить
в очередь смежную ей в паросочетанииreturn -1;
}
Эффективная реализация
Сразу оценим асимптотику. Всего имеется  итераций, на каждой из которых выполняется обход в ширину за , кроме того, могут происходить операции сжатия цветков — их может быть . Таким образом, если мы научимся сжимать цветок за , то общая асимптотика алгоритма составит .
Основную сложность представляют операции сжатия цветков. Если выполнять их, непосредственно объединяя списки смежности в один и удаляя из графа лишние вершины, то асимптотика сжатия одного цветка будет , кроме того, возникнут сложности при "разворачивании" цветков.
Вместо этого будем для каждой вершины графа  поддерживать указатель на базу цветка, которому она принадлежит (или на себя, если вершина не принадлежит никакому цветку). Нам надо решить две задачи: сжатие цветка за  при его обнаружении, а также удобное сохранение всей информации для последующего чередования вдоль увеличивающего пути.
Итак, одна итерация алгоритма Эдмондса представляет собой обход в ширину, выполняемый из заданной свободной вершины . Постепенно будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся со свободной вершины . Для удобства программирования будем класть в очередь только те вершины, расстояние до которых в дереве путей чётно (будем называть такие вершины чётными — т.е. это корень дерева, и вторые концы рёбер в паросочетании). Само дерево будем хранить в виде массива предков , в котором для каждой нечётной вершины (т.е. до которой расстояние в дереве путей нечётно, т.е. это первые концы рёбер в паросочетании) будем хранить предка - чётную вершину. Таким образом, для восстановления пути из дерева нам надо поочерёдно пользоваться массивами  и , где  — для каждой вершины содержит смежную ей в паросочетании, или , если таковой нет.
Теперь становится понятно, как обнаруживать циклы нечётной длины. Если мы из текущей вершины  в процессе обхода в ширину приходим в такую вершину , являющуюся корнем  или принадлежащую паросочетанию и дереву путей (т.е.  от которой не равно -1), то мы обнаружили цветок. Действительно, при выполнении этих условий и вершина , и вершина  являются чётными вершинами. Расстояние от них до их наименьшего общего предка имеет одну чётность, поэтому найденный нами цикл имеет нечётную длину.
Научимся сжимать цикл. Итак, мы обнаружили нечётный цикл при рассмотрении ребра , где  и  — чётные вершины. Найдём их наименьшего общего предка , он и будет базой цветка. Нетрудно заметить, что база тоже является чётной вершиной (поскольку у нечётных вершин в дереве путей есть только один сын). Однако надо заметить, что  — это, возможно, псевдовершина, поэтому мы фактически найдём базу цветка, являющегося наименьшим общим предком вершин  и . Реализуем сразу нахождение наименьшего общего предка (нас вполне устраивает асимптотика ):
int lca (int a, int b) {
bool used[MAXN] = { 0 };
// поднимаемся от вершины a до корня, помечая все чётные вершины
for (;;) {
a = base[a];
used[a] = true;
if (match[a] == -1) break; // дошли до корня
a = p[match[a]];
}
// поднимаемся от вершины b, пока не найдём помеченную вершину
for (;;) {
b = base[b];
if (used[b]) return b;
b = p[match[b]];
}
}
Теперь нам надо выявить сам цикл — пройтись от вершин  и  до базы  цветка. Будет более удобно, если мы пока просто пометим в каком-то специальном массиве (назовём его ) вершины, принадлежащие текущему цветку. После этого нам надо будет симитировать обход в ширину из псевдо-вершины — для этого достаточно положить в очередь обхода в ширину все вершины, лежащие на цикле цветка. Тем самым мы избежим явного объединения списков смежности.
Однако остаётся ещё одна проблема: корректное восстановление путей по окончании обхода в ширину. Для него мы сохраняли массив предков . Но после сжатия цветков возникает единственная проблема: обход в ширину продолжился сразу из всех вершин цикла, в том числе и нечётных, а массив предков у нас предназначался для восстановления путей по чётным вершинам. Более того, когда в сжатом графе найдётся увеличивающая цепь, проходящая через цветок, она вообще будет проходить по этому циклу в таком направлении, что в дереве путей это будет представляться движением вниз. Однако все эти проблемы изящно решаются таким манёвром: при сжатии цикла, проставим предков для всех его чётных вершин (кроме базы), чтобы эти "предки" указывали на соседнюю вершину в цикле. Для вершин  и , если они также не базы, направим указатели предков друг на друга. В результате, если при восстановлении увеличивающего пути мы придём в цикл цветка в нечётную вершину, путь по предкам будет восстановлен корректно, и приведёт в базу цветка (из которой он уже дальше будет восстанавливаться нормально).

Итак, мы готовы реализовать сжатие цветка:
int v, u; // ребро (v,u), при рассмотрении которого был обнаружен цветок
int b = lca (v, u);
memset (blossom, 0, sizeof blossom);
mark_path (v, b, u);
mark_path (u, b, v);
где функция  проходит по пути от вершины до базы цветка, проставляет в специальном массиве  для них  и проставляет предков для чётных вершин. Параметр  — сын для самой вершины  (с помощью этого параметра мы замкнём цикл в предках).
void mark_path (int v, int b, int children) {
while (base[v] != b) {
blossom[base[v]] = blossom[base[match[v]]] = true;
p[v] = children;
children = match[v];
v = p[match[v]];
}
}
Наконец, реализуем основную функцию — , которая будет искать увеличивающий путь из свободной вершины  и возвращать последнюю вершину этого пути, либо , если увеличивающий путь не найден.
Вначале произведём инициализацию:
int find_path (int root) {
memset (used, 0, sizeof used);
memset (p, -1, sizeof p);
for (int i=0; i<n; ++i)
base[i] = i;
Далее идёт обход в ширину. Рассматривая очередное ребро , у нас есть несколько вариантов:
Ребро несуществующее. Под этим мы подразумеваем, что  и  принадлежат одной сжатой псевдо-вершине (), поэтому в текущем поверхностном графе этого ребра нет. Кроме этого случая, есть ещё один случай: когда ребро  уже принадлежит текущему паросочетанию; т.к. мы считаем, что вершина  является чётной вершиной, то проход по этому ребру означает в дереве путей подъём к предку вершины , что недопустимо.
if (base[v] == base[to] || match[v] == to) continue;
Ребро замыкает цикл нечётной длины, т.е. обнаруживается цветок. Как уже упоминалось выше, цикл нечётной длины обнаруживается при выполнении условия:
if (to == root || match[to] != -1 && p[match[to]] != -1)
В этом случае нужно выполнить сжатие цветка. Выше уже подробно разбирался этот процесс, здесь приведём его реализацию:
int curbase = lca (v, to);
memset (blossom, 0, sizeof blossom);
mark_path (v, curbase, to);
mark_path (to, curbase, v);
for (int i=0; i<n; ++i)
if (blossom[base[i]]) {
base[i] = curbase;
if (!used[i]) {
used[i] = true;
q[qt++] = i;
}
}
Иначе — это "обычное" ребро, поступаем как и в обычном поиске в ширину. Единственная тонкость — при проверке, что эту вершину мы ещё не посещали, надо смотреть не в массив , а в массив  — именно он заполняется для посещённых нечётных вершин. Если мы в вершину ещё не заходили, и она оказалась ненасыщенной, то мы нашли увеличивающую цепь, заканчивающуюся на вершине , возвращаем её.
if (p[to] == -1) {
p[to] = v;
if (match[to] == -1)
return to;
to = match[to];
used[to] = true;
q[qt++] = to;
}
Итак, полная реализация функции :int find_path (int root) {
memset (used, 0, sizeof used);
memset (p, -1, sizeof p);
for (int i=0; i<n; ++i)
base[i] = i;
 
used[root] = true;
int qh=0, qt=0;
q[qt++] = root;
while (qh < qt) {
int v = q[qh++];
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (base[v] == base[to] || match[v] == to) continue;
if (to == root || match[to] != -1 && p[match[to]] != -1) {
int curbase = lca (v, to);
memset (blossom, 0, sizeof blossom);
mark_path (v, curbase, to);
mark_path (to, curbase, v);
for (int i=0; i<n; ++i)
if (blossom[base[i]]) {
base[i] = curbase;
if (!used[i]) {
used[i] = true;
q[qt++] = i;
}
}
}
else if (p[to] == -1) {
p[to] = v;
if (match[to] == -1)
return to;
to = match[to];
used[to] = true;
q[qt++] = to;
}
}
}
return -1;
}
Наконец, приведём определения всех глобальных массивов, и реализацию основной программы нахождения наибольшего паросочетания:
const int MAXN = ...; // максимально возможное число вершин во входном графе
 
int n;
vector<int> g[MAXN];
int match[MAXN], p[MAXN], base[MAXN], q[MAXN];
bool used[MAXN], blossom[MAXN];
 
...
 
int main() {
... чтение графа ...
 
memset (match, -1, sizeof match);
for (int i=0; i<n; ++i)
if (match[i] == -1) {
int v = find_path (i);
while (v != -1) {
int pv = p[v], ppv = match[pv];
match[v] = pv, match[pv] = v;
v = ppv;
}
}
}
Оптимизация: предварительное построение паросочетанияКак и в случае Алгоритма Куна, перед выполнением алгоритма Эдмондса можно каким-нибудь простым алгоритмом построить предварительное паросочетание. Например, таким жадным алгоритмом:
for (int i=0; i<n; ++i)
if (match[i] == -1)
for (size_t j=0; j<g[i].size(); ++j)
if (match[g[i][j]] == -1) {
match[g[i][j]] = i;
match[i] = g[i][j];
break;
}
Такая оптимизация значительно (до нескольких раз) ускорит работу алгоритма на случайных графах.
Случай двудольного графа
В двудольных графах отсутствуют циклы нечётной длины, и, следовательно, код, выполняющий сжатие цветков, никогда не выполнится. Удалив мысленно все части кода, обрабатывающие сжатие цветков, мы получим Алгоритм Куна практически в чистом виде. Таким образом, на двудольных графах алгоритм Эдмондса вырождается в алгоритм Куна и работает за .Дальнейшая оптимизация
Во всех вышеописанных операциях с цветками легко угадываются операции с непересекающимися множествами, которые можно выполнять намного эффективнее (см. Система непересекающихся множеств). Если переписать алгоритм с использованием этой структуры, то асимптотика алгоритма понизится до . Таким образом, для произвольных графов мы получили ту же асимптотическую оценку, что и в случае двудольных графов (алгоритм Куна), но заметно более сложным алгоритмом.
    Метод Форда-Фалкерсона (верхняя оценка на время работы; пример, на котором она достигается)
Теорема:
Если  — некоторый поток в сети  с источником  и стоком , то следующие утверждения эквивалентны:
Поток  максималенВ  не существует пути 
 для некоторого разреза  сети 
Доказательство:


Докажем от противного. Предположим, что в  существует какой-нибудь путь . Тогда рассмотрим . По лемме о сумме потоков  тоже является потоком в сети , и причем , что приводит нас к противоречию, что  максимальный поток.

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

Идея
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0:  для всех  из . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
[править]Реализация
dfs(u, Cmin) {
if (u = t)
return Cmin u.vis <- true
for (uv in E)
if (!v.vis) && (uv.f < uv.c)
дельта <- dfs(v, min(Cmin, uv.c - uv.f))
if (дельта > 0) {
uv.f += дельта
uv.backEdge.f -= дельта
return дельта
}
return 0
}
[править]Оценка производительности
Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено , где  — число рёбер в графе,  — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за  и увеличивает поток как минимум на 1.
[править]Пример несходящегося алгоритма


рис. 1
Рассмотрим приведённую справа сеть, с источником , стоком , пропускными способностями рёбер ,  и  соответственно ,  и  и пропускной способностью всех остальных рёбер, равной целому числу . Константа  выбрана так, что . Мы используем пути из остаточного графа, приведённые в таблице, причём ,  и .
Шаг Найденный путь Добавленный поток Остаточные пропускные способности

0
1
2
3
4
5
Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер ,  и  имеют форму ,  и , соответственно, для какого-то натурального . Это значит, что мы можем использовать увеличивающие пути , ,  и  бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага 5 равен . За бесконечное время полный поток сойдётся к , тогда как максимальный поток равен . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.
[править]Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину
При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага. Дана сеть (рис. 2).


рис. 2
Благодаря двум итерациям (рис. 3 и рис. 4)


рис. 3


рис. 4
рёбра  насытились лишь на 1. Конечная сеть будет получена ещё через 1998 итераций (рис. 5).


рис. 5
    Алгоритм Эдмондса-Карпа
Алгоритм
Для заданной сети  алгоритм Эдмондса-Карпа находит поток максимальной величины из заданного истока  в заданный сток  за .
[править]Псевдокод
Edmonds_Karp (G, s, t)
for (для) каждого ребра
do

while существует кратчайший путь из в в остаточной сети
do
for (для) каждого ребра
do

[править]Корректность алгоритма Эдмондса-Карпа
Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона. На каждой итерации цикла while поток в графе  увеличивается вдоль одного из кратчайших путей в  из истока  в сток . Этот процесс повторяется до тех пор пока существует кратчайший  путь в . Если в  не существует кратчайшего пути из  в , значит, не существует никакого вообще никакого  пути в  следовательно по теореме Форда-Фалкерсона найденный поток  максимальный.
[править]Оценка быстродействия
Лемма:
Если в сети  с источником  и стоком  увеличение потока производится вдоль кратчайших  путей в , то для всех вершин  длина кратчайшего пути  в остаточной сети  не убывает после каждого увеличения потока.
Доказательство:

Предположим противное, пусть существует вершина , что после какого-то увеличения потока длина кратчайшего пути из  в  уменьшилась. Обозначим потоки до и после увеличения соответственно за  и . Пусть  — вершина, расстояние  от  до которой минимально и уменьшилось с увеличением потока. Имеем . Рассмотрим путь , являющийся кратчайшим от  к  в . Тогда верно, что .По выбору  и из предыдущего утверждения получаем, что .
Предположим , тогда . Это противоречит .Пусть , но известно, что . Появление ребра  после увеличения потока означает увеличение потока по обратному ребру . Увеличение потока производится вдоль кратчайшего пути, поэтому кратчайший путь из  в  вдоль которого происходило увеличения выглядит как , из чего получаем . Данное утверждение противоречит . Итак мы пришли к противоречию с существованием вершины , кратчайшее расстояние до которой уменьшилось с увеличением потока.

Опираясь на предшествующую лемму, докажем следующую теорему, которая ограничивает сверху число итераций цикла while в алгоритме Эдмондса-Карпа.
Теорема:
Пусть для некоторой сети  с источником  и стоком  выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла while составляет .
Доказательство:

Рассмотрим множество ребер  остаточной сети , принадлежащих увеличивающему пути , таких что . Назовем данные ребра критическими. Покажем, что каждое из  ребер может становиться критическим не более, чем  раз. Заметим, что после увеличения потока вдоль пути  все критические ребра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути — критическое.
Рассмотрим две вершины  и  принадлежащие , соединенные некоторым ребром из . Увеличение производится вдоль кратчайших путей, поэтому если ребро становиться критическим в первый раз, верно, что . После увеличения потока ребро  исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру . Это может произойти только в том случае, если ребро  встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети  составлял , то поскольку увеличение производиться вдоль кратчайших путей, верно: . Согласно лемме , откуда .
Итак в промежуток времени между тем, когда ребро  становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от  до  увеличивается минимум на . Расстояние  в начальный момент времени больше либо равно . Среди промежуточных вершин на кратчайшем пути  не могут находиться ,  или . Следовательно к тому моменту, когда вершина  станет недостижимой из источника расстояние до нее не превысит . Получаем, что ребро  могло стать критическим не более  раз. Поскольку в графе не более  пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно .
Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет . На каждой итерации цикла while рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла whileтакже составляет .
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла while можно выполнить за время . Инициализация в процедуре Edmonds_Karpпроизводится за , следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет . Заметим также, что сущетсвует сеть "грибок" на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет .[править]Литература
    Максимальное паросочетание в двудольном графе, сведение к поиску  максимального потока
Пусть дан граф G = (V,E), паросочетание M в G это множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин.
Максимальное паросочетание — это такое паросочетание M в графе G, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем ребрам паросочетания. Другими словами, паросочетание M графа Gявляется максимальным, если любое ребро в G имеет непустое пересечение по крайней мере с одним ребром из M. Ниже приведены примеры максимальных паросочетаний (красные рёбра) в трёх графах.

Максимальные паросочетания[ HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9F%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5&veaction=edit&vesection=8" \o "Редактировать раздел \«Максимальные паросочетания\»" править | править вики-текст]
Максимальное паросочетание можно найти простым жадным алгоритмом. Наибольшее паросочетание является также максимальным, и, поэтому, имеется возможность найти самое большое максимальное паросочетание за полиномиальное время. Однако неизвестно никакого полиномиального по времени алгоритма для нахождения минимального максимального паросочетания, то есть максимального паросочетания, содержащего минимально возможное число рёбер.
Заметим, что наибольшее паросочетание из k рёбер является рёберным доминирующим множеством[en] с k рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с k рёбрами, мы можем построить наибольшее паросочетание с k рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества[10]. Обе эти задачи оптимизации известны как NP-трудные и являются классическими примерами NP-полных задач[11]. Обе задачи могут быть  HYPERLINK "https://ru.wikipedia.org/wiki/%D0%90%D0%BF%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC" \o "Аппроксимационный алгоритм" апроксимированы с коэффициентом 2 с полиномиальным временм — просто находим произвольное максимальное паросочетаниеM HYPERLINK "https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5" \l "cite_note-12" [12].
Дан двудольный граф , содержащий  вершин и  рёбер. Требуется найти наибольшее паросочетание, т.е. выбрать как можно больше рёбер, чтобы ни одно выбранное ребро не имело общей вершины ни с каким другим выбранным ребром.
Описание алгоритма
Необходимые определения
Паросочетанием  называется набор попарно несмежных рёбер графа (иными словами, любой вершине графа должно быть инцидентно не более одного ребра из множества ). Мощностью паросочетания назовём количество рёбер в нём. Наибольшим (или максимальным) паросочетанием назовём паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе. Все те вершины, у которых есть смежное ребро из паросочетания (т.е. которые имеют степень ровно один в подграфе, образованном ), назовём насыщенными этим паросочетанием.
Цепью длины  назовём некоторый простой путь (т.е. не содержащий повторяющихся вершин или рёбер), содержащий  рёбер.
Чередующейся цепью (в двудольном графе, относительно некоторого паросочетания) назовём цепь, в которой рёбра поочередно принадлежат/не принадлежат паросочетанию.
Увеличивающей цепью (в двудольном графе, относительно некоторого паросочетания) назовём чередующуюся цепь, у которой начальная и конечная вершины не принадлежат паросочетанию.
Теорема Бержа
Формулировка. Паросочетание является максимальным тогда и только тогда, когда не существует увеличивающих относительно него цепей.
Доказательство необходимости. Покажем, что если паросочетание  максимально, то не существует увеличивающей относительно него цепи. Доказательство это будет конструктивным: мы покажем, как увеличить с помощью этой увеличивающей цепи  мощность паросочетания  на единицу.
Для этого выполним так называемое чередование паросочетания вдоль цепи . Мы помним, что по определению первое ребро цепи  не принадлежит паросочетанию, второе — принадлежит, третье — снова не принадлежит, четвёртое — принадлежит, и т.д. Давайте поменяем состояние всех рёбер вдоль цепи : те рёбра, которые не входили в паросочетание (первое, третье и т.д. до последнего) включим в паросочетание, а рёбра, которые раньше входили в паросочетание (второе, четвёртое и т.д. до предпоследнего) — удалим из него.
Понятно, что мощность паросочетания при этом увеличилась на единицу (потому что было добавлено на одно ребро больше, чем удалено). Осталось проверить, что мы построили корректное паросочетание, т.е. что никакая вершина графа не имеет сразу двух смежных рёбер из этого паросочетания. Для всех вершин чередующей цепи , кроме первой и последней, это следует из самого алгоритма чередования: сначала мы у каждой такой вершины удалили смежное ребро, потом добавили. Для первой и последней вершины цепи  также ничего не могло нарушиться, поскольку до чередования они должны были быть ненасыщенными. Наконец, для всех остальных вершин, — не входящих в цепь , — очевидно, ничего не поменялось. Таким образом, мы в самом деле построили паросочетание, и на единицу большей мощности, чем старое, что и завершает доказательство необходимости.
Доказательство достаточности. Докажем, что если относительно некоторого паросочетания  нет увеличивающих путей, то оно — максимально.
Доказательство проведём от противного. Пусть есть паросочетание , имеющее бОльшую мощность, чем . Рассмотрим симметрическую разность  этих двух паросочетаний, т.е. оставим все рёбра, входящие в  или в , но не в оба одновременно.
Понятно, что множество рёбер  — уже наверняка не паросочетание. Рассмотрим, какой вид это множество рёбер имеет; для удобства будем рассматривать его как граф. В этом графе каждая вершина, очевидно, имеет степень не выше 2 (потому что каждая вершина может иметь максимум два смежных ребра — из одного паросочетания и из другого). Легко понять, что тогда этот граф состоит только из циклов или путей, причём ни те, ни другие не пересекаются друг с другом.
Теперь заметим, что и пути в этом графе  могут быть не любыми, а только чётной длины. В самом деле, в любом пути в графе  рёбра чередуются: после ребра из  идёт ребро из , и наоборот. Теперь, если мы рассмотрим какой-то путь нечётной длины в графе , то получится, что в исходном графе  это будет увеличивающей цепью либо для паросочетания , либо для . Но этого быть не могло, потому что в случае паросочетания  это противоречит с условием, а в случае  — с его максимальностью (ведь мы уже доказали необходимость теоремы, из которой следует, что при существовании увеличивающей цепи паросочетание не может быть максимальным).
Докажем теперь аналогичное утверждение и для циклов: все циклы в графе  могут иметь только чётную длину. Это доказать совсем просто: понятно, что в цикле рёбра также должны чередоваться (принадлежать по очереди то , то ), но это условие не может выполниться в цикле нечётной длины — в нём обязательно найдутся два соседних ребра из одного паросочетания, что противоречит определению паросочетания.
Таким образом, все пути и циклы графа  имеют чётную длину. Следовательно, граф  содержит равное количество рёбер из  и из . Но, учитывая, что в  содержатся все рёбра  и , за исключением их общих рёбер, то отсюда следует, что мощность  и  совпадают. Мы пришли к противоречию: по предположению паросочетание  было не максимальным, значит, теорема доказана.
Алгоритм Куна
Алгоритм Куна — непосредственное применение теоремы Бержа. Его можно кратко описать так: сначала возьмём пустое паросочетание, а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось — процесс останавливаем, — текущее паросочетание и есть максимальное.
Осталось детализировать способ нахождения увеличивающих цепей. Алгоритм Куна — просто ищет любую из таких цепей с помощью обхода в глубину или в ширину. Алгоритм Куна просматривает все вершины графа по очереди, запуская из каждой обход, пытающийся найти увеличивающую цепь, начинающуюся в этой вершине.
Удобнее описывать этот алгоритм, считая, что граф уже разбит на две доли (хотя на самом деле алгоритм можно реализовать и так, чтобы ему не давался на вход граф, явно разбитый на две доли).
Алгоритм просматривает все вершины  первой доли графа: . Если текущая вершина  уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем. Иначе — алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.
Поиск увеличивающей цепи осуществляется с помощью специального обхода в глубину или ширину (обычно в целях простоты реализации используют именно обход в глубину). Изначально обход в глубину стоит в текущей ненасыщенной вершине  первой доли. Просматриваем все рёбра из этой вершины, пусть текущее ребро — это ребро . Если вершина  ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра ; в таком случае просто включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины . Иначе, — если  уже насыщена каким-то ребром , то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра , . Для этого просто перейдём в нашем обходе в вершину  — теперь мы уже пробуем найти увеличивающую цепь из этой вершины.
Можно понять, что в результате этот обход, запущенный из вершины , либо найдёт увеличивающую цепь, и тем самым насытит вершину , либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина  уже не сможет стать насыщенной).
После того, как все вершины  будут просмотрены, текущее паросочетание будет максимальным.
Время работы
Итак, алгоритм Куна можно представить как серию из  запусков обхода в глубину/ширину на всём графе. Следовательно, всего этот алгоритм исполняется за время , что в худшем случае есть .
Однако эту оценку можно немного улучшить. Оказывается, для алгоритма Куна важно то, какая доля выбрана за первую, а какая — за вторую. В самом деле, в описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время , где  — число вершин первой доли. В худшем случае это составляет  (где  — число вершин второй доли). Отсюда видно, что выгоднее, когда первая доля содержит меньшее число вершин, нежели вторая. На очень несбалансированных графах (когда  и  сильно отличаются) это выливается в значительную разницу времён работы.
Реализация
Приведём здесь реализацию вышеописанного алгоритма, основанную на обходе в глубину, и принимающей двудольный граф в виде явно разбитого на две доли графа. Эта реализация весьма лаконична, и, возможно, её стоит запомнить именно в таком виде.
Здесь  — число вершин в первой доле,  — во второй доле,  — список рёбер из вершины  первой доли (т.е. список номеров вершин, в которые ведут эти рёбра из ). Вершины в обеих долях занумерованы независимо, т.е. первая доля — с номерами , вторая — с номерами .
Дальше идут два вспомогательных массива:  и . Первый —  — содержит в себе информацию о текущем паросочетании. Для удобства программирования, информация эта содержится только для вершин второй доли:  — это номер вершины первой доли, связанной ребром с вершиной  второй доли (или , если никакого ребра паросочетания из  не выходит). Второй массив —  — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, просто чтобы обход в глубину не заходил в одну вершину дважды).
Функция  — и есть обход в глубину. Она возвращает , если ей удалось найти увеличивающую цепь из вершины , при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.
Внутри функции просматриваются все рёбра, исходящие из вершины  первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину , либо если эта вершина  насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из , то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом  производим чередование в текущем ребре: перенаправляем ребро, смежное с , в вершину .
В основной программе сначала указывается, что текущее паросочетание — пустое (список  заполняется числами ). Затем перебирается вершина  первой доли, и из неё запускается обход в глубину , предварительно обнулив массив .
Стоит заметить, что размер паросочетания легко получить как число вызовов  в основной программе, вернувших результат . Само искомое максимальное паросочетание содержится в массиве .int n, k;
vector < vector<int> > g;
vector<int> mt;
vector<char> used;
 
bool try_kuhn (int v) {
if (used[v]) return false;
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (mt[to] == -1 || try_kuhn (mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
 
int main() {
... чтение графа ...
 
mt.assign (k, -1);
for (int v=0; v<n; ++v) {
used.assign (n, false);
try_kuhn (v);
}
 
for (int i=0; i<k; ++i)
if (mt[i] != -1)
printf ("%d %d\n", mt[i]+1, i+1);
}
Ещё раз повторим, что алгоритм Куна легко реализовать и так, чтобы он работал на графах, про которые известно, что они двудольные, но явное их разбиение на две доли не найдено. В этом случае придётся отказаться от удобного разбиения на две доли, и всю информацию хранить для всех вершин графа. Для этого массив списков  теперь задаётся не только для вершин первой доли, а для всех вершин графа (понятно, теперь вершины обеих долей занумерованы в общей нумерации — от  до ). Массивы  и  теперь также определены для вершин обеих долей, и, соответственно, их нужно поддерживать в этом состоянии.
Улучшенная реализация
Модифицируем алгоритм следующим образом. До основного цикла алгоритма найдём каким-нибудь простым алгоритмом произвольное паросочетание (простым эвристическим алгоритмом), и лишь затем будем выполнять цикл с вызовами функции kuhn(), который будет улучшать это паросочетание. В результате алгоритм будет работать заметно быстрее на случайных графах — потому что в большинстве графов можно легко набрать паросочетание достаточно большого веса с помощью эвристики, а потом улучшить найденное паросочетание до максимального уже обычным алгоритмом Куна. Тем самым мы сэкономим на запусках обхода в глубину из тех вершин, которые мы уже включили с помощью эвристики в текущее паросочетание.
Например, можно просто перебрать все вершины первой доли, и для каждой из них найти произвольное ребро, которое можно добавить в паросочетание, и добавить его. Даже такая простая эвристика способна ускорить алгоритм Куна в несколько раз.
Следует обратить внимание на то, что основной цикл придётся немного модифицировать. Поскольку при вызове функции  в основном цикле предполагается, что текущая вершина ещё не входит в паросочетание, то нужно добавить соответствующую проверку.
В реализации изменится только код в функции main():
int main() {
... чтение графа ...
 
mt.assign (k, -1);
vector<char> used1 (n);
for (int i=0; i<n; ++i)
for (size_t j=0; j<g[i].size(); ++j)
if (mt[g[i][j]] == -1) {
mt[g[i][j]] = i;
used1[i] = true;
break;
}
for (int i=0; i<n; ++i) {
if (used1[i]) continue;
used.assign (n, false);
try_kuhn (i);
}
 
for (int i=0; i<k; ++i)
if (mt[i] != -1)
printf ("%d %d\n", mt[i]+1, i+1);
}
Другой хорошей эвристикой является следующая. На каждом шаге будет искать вершину наименьшей степени (но не изолированную), из неё выбирать любое ребро и добавлять его в паросочетание, затем удаляя обе эти вершины со всеми инцидентными им рёбрами из графа. Такая жадность работает очень хорошо на случайных графах, даже в большинстве случаев строит максимальное паросочетание (хотя и против неё есть тест, на котором она найдёт паросочетание значительно меньшей величины, чем максимальное).
 
    Циркуляция (см. вики-конспекты)
Циркуляцией называется поток в сети  нулевой величины (см. рисунок 1).

Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)
То есть закон сохранения потока  должен выполняться для всех вершин графа, а значит нет нужды в истоке и стоке.
Содержание
 [убрать] 
1 Постановка задачи2 Решение3 Псевдокод4 Источники[править]Постановка задачи
Рассмотрим сеть , в которой про каждое ребро  известны величины:  — минимальная пропускная способность и  — максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.
Когда все  равны , достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.
[править]Решение
Для решения этой задачи заменим исходную сеть  на  следующим образом. Сначала добавим в граф вершины  — исток и  — сток. Для каждого ребра  добавим ребра  и , а также сделаем в ребре  изменения:  (см. рисунок 2).

Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований ребер.
Каждое ребро изначального графа заменяется на три новых. Если по ребру  в исходной сети протекает поток , то в новой сети по ребру должен течь поток, равный , то есть его пропускной способности. Поток, который вытекает из  по ребру в , заменяется на поток, который протекает по ребрам  и  (поскольку сумма их пропускных способностей в полученном графе равна ). Аналогично, для вершины  суммарный входящий поток не изменился. Таким образом, любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя ребрами в полученном графе. Заметим, что в сети  все , то есть мы имеем обыкновенную сеть.
Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство  для всех вершин графа. Это равносильно существованию потока между вершинами  и  в сети , который полностью насытит ребра, исходящие из истока. Действительно, этот поток в исходном графе насытит -ое ребро как минимум на , что и является необходимым требованием. Если этот поток существует, то будет выполнено:
 где , то есть для всех исходных вершин;
В , что удовлетворяет всем ограничениям.
Значит, этот поток и есть циркуляция.
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль ребер в сети соответствующие значения минимальной пропускной способности.
[править]Псевдокод
G // пустой граф, вершины 0 и n + 1 - исток и сток
n, m; // вершин, ребер в исходном графе
edge // ребро с полями (from, to, min_cap, cap)
Для i = 1 to m
считать ребро edge добавить в граф G ребро (0, edge.to, 0, edge.min_cap)
добавить в граф G ребро (edge.from, edge.to, 0, edge.cap - edge.min_cap)
добавить в граф G ребро (edge.from, n + 1, 0, edge.min_cap)
max_flow = наибольший поток в графе G
Для всех ребер, инцидентных истоку
если для текущего ребра flow < cap
циркуляции НЕТ
Поиск подстрок
Сравнение — «чёрный ящик»
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.
Преимущества:
позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.
Недостатки:
не выдается точка, в которой произошло несовпадение.
[править]По порядку сравнения паттерна в тексте
[править]Прямой
Преимущества:
отсутствие регрессии на «плохих» данных.
Недостатки:
не самая хорошая средняя асимптотическая сложность.
[править]Обратный
Паттерн движется по тексту слева направо, но сравнение подстрок происходит справа налево.
Преимущества:
при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов.
Недостатки:
производительность сильно зависит от данных.
[править]Сравнение в необычном порядке
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.[1][править]По количеству поисковых шаблонов
Сколько поисковых шаблонов может обработать алгоритм за один раз.
один шаблон (англ. single pattern algorithms)
конечное количество шаблонов (англ. finite set of patterns)
бесконечное количество шаблонов (англ. infinite number of patterns) (см. Теория формальных языков)
[править]По необходимости препроцессинга текста
Виды препроцессинга:
Префикс-функцияZ-функцияБорСуффиксный массивАлгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.
[править]Сравнение алгоритмов
— размер алфавита
 — длина текста
 — длина паттерна
 — размер ответа(кол-во пар)
 — суммарная длина всех паттернов
Название Среднее Худшее ПрепроцессингДополнительная память Кол-во поисковых шаблонов Порядок сравнения Описание
Наивный алгоритм (Brute Force algorithm) SingleПрямой Сравнение — «чёрный ящик». Если достаточно мало по сравнению с , то асимптотика будет близкой к , что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
Поиск подстроки в строке с помощью Z-функции SingleПрямой Алгоритм Рабина-Карпа (Karp-Rabin algorithm) Single / FiniteПрямой Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
Алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt algorith) SingleПрямой Использует префикс-функциюАлгоритм Колусси (Colussi algorithm) SingleПрямой / Обратный Оптимизация Алгоритма Кнута-Морриса-Пратта использует как прямой, так и обратный обход
Алгоритм Ахо-Корасик (Aho–Corasick string matching algorithm) FiniteПрямой Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как Красно-черное дерево. В последнем случае уменьшится расход памяти, но ухудшится асимптотика
Алгоритм Shift-Or   — размер машинного слова SingleПрямой Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если . Иначе деградирует и по памяти, и по сложности
Алгоритм Бойера-Мура (Boyer-Moore algorithm) SingleОбратный Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций[2]Поиск подстроки в строке с помощью суффиксного массива(Suffix array) SingleПрямой Использует  HYPERLINK "http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2" \o "Суффиксный массив" Суффиксный массив. Если использовать  HYPERLINK "http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%81%D0%B0%D0%B8_%D0%B8_%D0%B4%D1%80." \o "Алгоритм Касаи и др." Largest common prefix (lcp), то можно уменьшить асимптотику до . Суффиксный массив можно строить стандартными способами илиалгоритмом Каркайнена-Сандерса. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Каркайнена-СандерсаПоиск подстроки в строке с помощью суффиксного дерева (Suffix tree) SingleПрямой Позволяет выполнять поиск подстроки в строке за линейное время
    Допустимые/недопустимые сдвиги
Большинство текстовых редакторов умеет искать заданное слово в редактируемом тексте — хочется, чтобы это происходило быстро. Говоря формально, задача поиска подстрок (string-matching problem) состоит в следующем. Пусть даны «текст» — массив T[1..n] длины n и «образец» — массив P[1..m] длины m<n. Мы считаем, что элементы массивов P и T — символы некоторого конечного алфавита (например, X = {0, 1} или X = {а, b, ..., z}). Массивы, состоящие из символов алфавита X, называют строками (strings) символов, или словами в этом алфавите.
Будем говорить, что образец Р входит со сдвигом s, или, эквивалентно, входит с позиции s + 1 в текст Т, если 0≤ s≤ п — m и T[s+1, ... s + m] =P[1...m] (иными словами, если T[s+j] =P[j] при 1 ≤ j≤ m). Если Р входит со сдвигом s в текст Т, то говорят, что s — допустимый сдвиг, в противном случае s — недопустимый сдвиг. Задача поиска подстрок состоит в нахождении всех допустимых сдвигов для данных текста T и образца Р 
Пусть требуется найти все вхождения образца P='abaa' в текст T='аbсаbааbс'. Образец входит в текст только один раз, со сдвигом s=3 (стало быть, 3 — допустимый сдвиг).
Первый приходящий в голову алгоритм для поиска образца P в тексте Т последовательно проверяет равенство T[s+1, ... s + m] =P [1...m] для каждого из п — т + 1 возможных значений s.
Можно сказать, что мы двигаем образец вдоль текста и проверяем все его положения . Простейший алгоритм ищет образец P='aab' в тексте Т='acaabc'. Изображены четыре последовательные попытки. Буквы, для которых сравнение прошло успешно, соединены прямыми. Буквы, на которых выявлено несовпадение, соединены ломаными линиями. При этом s=2 -  единственный допустимый сдвиг.
Простейший алгоритм — не лучший. Неэффективность простейшего алгоритма связана с тем, что информация о тексте Т, получаемая при проверке данного сдвига s, никак не используется при проверке последующих сдвигов. Между тем такая информация может очень помочь. Пусть, например, P — 'aaab', и мы выяснили, что сдвиг s=0 допустим. Тогда сдвиги 1, 2 и 3 заведомо недопустимы, поскольку T[4] =b.
    Конкатенация строк, префикс строки, суффикс строки
В строке важен порядок символов, так, строки 01 и 10 различны. Длина строки равна числу символов в строке. Длина пустой строки равна нулю, длина строки 1 равна единице, длина строки 1001 четырем. Если X и Y строки, то их сцеплением или конкатенацией называется строка XY, полученная приписыванием символов строки Y за символами строки X.
В языке Turbo Pascal определен стандартный тип данных string. Значения этого типа – последовательность символов длиной от 0 до 255. При определении типа строки можно указать в квадратный скобках максимальный размер строки. Если размер строки не указан, то он считается равным 255.
Изображением строки называется последовательность символов, заключенная в апострофы. Значение для строковой переменной можно прочесть из стандартного файла ввода и поместить в стандартный файл вывода.
Операция + используется для конкатенации строк, в этом случае к первой строке приписывается вторая.
К строкам применимы операции отношения. Сравнение осуществляется слева направо в соответствии с кодами символов. При сравнении строк разной длины принято соглашение, что отсутствующий символ меньше любого кода символа строки, поэтому верно ‘дом’ < ‘дома’.
Символы в строке перенумерованы, начиная с 1. Количество символов в строке или длину строки можно определить с помощью стандартной функции length(s). Получить доступ к символу строки можно по его индексу, для этого за строковой переменной в квадратных скобках указывается индекс. Значение строковой переменной изменится, если изменится значение хотя бы одного из символов строки.
Префиксы и суффиксы строкиСтрока X называется префиксом строки S, если строка S представима как XY. Строка Y называется суффиксом строки S. В листинге 9.6. расположена программа, которая содержит две процедуры. Одна процедура по заданной строке выводит все префиксы этой строки, причем каждый префикс выводится с отдельной строки выходного файла. Вторая процедура выводит все суффиксы строки. В процедурах используется стандартная функция copy (s,n,i),которая возвращает подстроку строки s, начиная с символа номер n, состоящую из i символов.
Прямые переходы
Пусть в нашем автомате пока одно состояние — . Пройдем по образцу, добавляя для каждого его символа новое состояние и переход в него из предыдущего состояния по этому символу. Последнее состояние объявим допускающим. Таким образом, каждому состоянию теперь соответствует ровно один префикс образца. Пронумеруем их длинами соответствующих префиксов с увеличением на единицу.
[править]Суффиксные ссылки
Теперь нужно расставить остальные переходы. В итоговом автомате при переходе в состояние  префикс образца —  — должен быть максимальным его префиксом, равным суффиксу текста до последнего просмотренного символа, включительно. Переходы, осуществляющие перемещение в такие префиксы, называют суффиксными ссылками.
В качестве базы построения суффиксных ссылок проведем из  по всем символам алфавита, кроме первого символа образца, ссылки в : длина максимального текущего суффикса текста, равного префиксу образца, увеличивается максимум на один и только в том случае, когда очередные их символы совпадают. Пусть построены все переходы из состояний, номер которых меньше некоторого . Тогда для того, чтобы определить направление ссылки из состояния  по символу , нужно найти длину наибольшего префикса образца, из состояния которого по  ведет прямой переход (если таких префиксов нет, значит, символ прежде не встречался в образце — нужно перейти в ).Префикс-функция, взятая многократно от  символа образца, позволяет перебрать все префиксы образца, равные суффиксу его первых  символов. Таким образом, , где справа описан прямой переход либо переход из . Так как все переходы из первых  состояний уже построены,  соответствует нужному состоянию.
Если забыть про разницу в построении прямых переходов и суффиксных ссылок, можно заметить, что переходы  решают поставленную задачу нахождения максимального суффикса текста, равного префиксу образца.
Основные определения и описание структуры[править | править вики-текст]
 — непустое конечное множество символов, называемое алфавитом. Последовательность символов (возможно, пустая) из алфавита обозначается буквами r, s и t.  представляет собой перевёрнутую строку. Отдельные символы обозначаются буквами x, y или z.  — пустая строка. Символами из алфавита являются буквы a, b, …. Пока размер алфавита принимается постоянным. |t| обозначает длину строки t.  — все строки длины m,  и .
Префикс w строки t — строка такая, что wv = t для некоторой (возможно, пустой) строки v. Префикс называется собственным, если |v|  0.
Суффикс w строки t — строка такая, что vw = t для некоторой (возможно, пустой) строки v. Суффикс называется собственным, если |v|  0. Например, для строки «substring» подстрока «sub» является собственным префиксом, «ring» — собственным суффиксом.
Подстрока w строки t называется правым ветвлением, если t может быть представлена как  и  для некоторых строк  и , а также букв x  y. Левое ветвление определяется аналогично. Например, для «eabceeabcd» подстрока «abc» является правым ветвлением, так как в обоих её вхождениях в t справа от неё стоят различные символы, зато та же подстрока не является левым ветвлением, потому что слева от неё в обоих вхождениях стоит одинаковый символ «e».
-дерево T — корневое дерево с рёбрами, помеченными последовательностями из . Для каждого символа a из алфавита каждый узел в дереве Tимеет не более одного ребра, метка которого начинается c символа a. Ребро от t до s с меткой v мы будем обозначать .Пусть k — узел -дерева T, тогда path(k) — строка, которая представляет собой конкатенацию всех меток рёбер от корня до k. Мы назовем местоположением w, для которого path() = w.
Так как каждая ветвь уникальна, если path(t) = w, мы можем обозначить узел t за . Поддерево узла  обозначается .
Слова, которые представлены в -дереве T, задаются множеством, которое обозначается words(T). Слово w входит во множество words(T) тогда и только тогда, когда существует строка v (возможно, пустая) такая, что  — узел дерева T.
Если строка w входит в words(T), w = uv,  — узел дерева T, пару  будем называть ссылочной парой w по отношению к дереву T. Если u — наидлиннейший префикс такой, что  — ссылочная пара, мы будем называть  канонической ссылочной парой. Тогда мы будем писать . Местоположение  называется явным, если |v| = 0, и неявным в противном случае.
-дерево T, в котором каждое ребро помечено одиночным символом, называется атомарным (для него каждое местоположение является явным). -дерево T, в котором каждый узел является либо корнем, либо листом или узлом ветвления, называется компактным.
Атомарное -дерево также называют  (луч). Атомарное и компактное -дерево однозначно определены словами, которые они содержат.
Суффиксное дерево для строки t — это -дерево такое, что words(T) = {w| w — подслово t}. Для строки t атомарное суффиксное дерево обозначается ast(t), компактное суффиксное дерево обозначается cst(t).
Обратное префиксное дерево строки t — это суффиксное дерево для строки .Вложенный суффикс — суффикс, который входит в строку t где-нибудь ещё. Наидлиннейший вложенный суффикс называется активным суффиксомстроки t.
Свойства суффиксных деревьев[править | править вики-текст]
Лемма. Местоположение w явно в компактном суффиксном дереве тогда и только тогда, когда w является не вложенным суффиксом t или w — правое ветвление.
Доказательство. . Если  явно, то это может быть либо лист, либо вершина ветвления или корень (в этом случае  и w — вложенный суффиксt).
Если  — лист, тогда также является и суффиксом t. Значит, это должен быть не вложенный суффикс, так как иначе он появился бы где-нибудь ещё в строке t:  v — суффикс t такой, что w — префикс v. Этот узел не может быть листом.
Если  — узел ветвления, тогда должны существовать, по меньшей мере, два выходящих ребра из  с различными метками. Это означает, что существуют два различных суффикса u, v, что w — префикс u и w — префикс v, где v = wxs, u = , x . Следовательно, w — правое ветвление.
. Если w является не вложенным суффиксом t, это должен быть лист. Если w — правое ветвление, то имеются два суффикса u и v, u = wxs, v = ,x , тогда w является узлом ветвления. Лемма доказана.
Теперь легко видеть, почему ответ на вопрос, входит ли слово w в строку t, может быть найден за время O(|w|): нужно только проверить, является ли wместоположением (явным или неявным) в cst(t).
Метки рёбер должны представлять собой указатели на положение в строке, чтобы суффиксное дерево расходовало память размером O(n). Метка (p, q) ребра означает подстроку  или пустую строку, если p > q.
Укконен вводит название открытые рёбра для рёбер, заканчивающихся в листьях. Пометки открытых рёбер записывают как (p, ) вместо (p, |t|), где  — длина, всегда большая, чем |t|.
Пусть T — -дерево. Пусть  — узел T, v — наидлиннейший суффикс w такой, что  — также узел T. Непомеченное ребро от  до  называетсясуффиксным звеном. Если v = w, оно называется атомарным.
Утверждение. В ast(t) и cst(t$), где $  t, все суффиксные звенья являются атомарными.
Доказательство. Символ $ называется символом-стражем. Первая часть (для ast(t)) следует из определения, так как местоположения являются явными. Для доказательства второй (случай cst(t)) части мы должны показать, что для каждого узла   также является узлом cst(t). Если  — узел cst(t), то является либо листом, либо узлом ветвления. Если является листом, тогда aw — не вложенный суффикс t. Благодаря символу-стражу, из леммы следует, что все суффиксы (включая корень, пустой суффикс) являются явными, так как только корень — вложенный суффикс. Поэтому w является листом или корнем. Если  — узел ветвления, тогда aw — правое ветвление, как и w. Следовательно, местоположение  явно по лемме. Утверждение доказано.
Как следует из этого доказательства, символ-страж гарантирует существование листьев для всех суффиксов. С таким символом не может быть вложенных суффиксов, кроме пустого. Если мы опустим символ-страж, некоторые суффиксы могут стать вложенными, и их местоположения станут неявными.
Требования суффиксного дерева к памяти[править | править вики-текст]
Утверждение. Компактное суффиксное дерево может быть представлено в виде, требующем O(n) памяти.
Доказательство. Суффиксное дерево содержит не более одного листа на каждый суффикс (в точности один с символом-стражем). Каждый внутренний узел должен быть узлом ветвления, следовательно, внутренний узел имеет по меньшей мере двух потомков. Каждое ветвление увеличивает число листьев по меньшей мере на единицу, поэтому мы имеем не более n внутренних узлов и не более n листьев.
Для представления строк, являющихся метками рёбер, мы используем индексацию в исходной строке, как описано выше. Каждый узел имеет не более одного предка и, таким образом, общее число ребер не превышает 2n.
Аналогично, каждый узел имеет не более одного суффиксного звена, тогда общее число суффиксных звеньев также ограничено числом 2n. Утверждение доказано.
Как пример суффиксного дерева с 2n-1 вершинами можно рассмотреть дерево для слова . Размер атомарного суффиксного дерева для строки tсоставляет O().
    Простейший алгоритм
Дан текст  и паттерн  такие, что  и элементы этих строк — символы из конечного алфавита . Требуется проверить, входит ли паттерн  в текст .
Определение:
Будем говорить, что паттерн  встречается в тексте  со сдвигом , если  и . Если строка  встречается в строке , то  является подстрокой .
[править]Алгоритм
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие  для каждого из возможных значений .
[править]Псевдокод
Приведем пример псевдокода, который находит все вхождения строки  в  и возвращает массив позиций, откуда начинаются вхождения.
vector<int> naiveStringMatcher(t : string, p : string):
int n = t.length int m = p.length vector<int> ans for i = 0 to n - m
if t[i .. i + m - 1] == p
ans.push_back(i)
return ans[править]Время работы
Алгоритм работает за . В худшем случае  , что даёт . Однако если  достаточно мало по сравнению с , то тогда асимптотика получается близкой к , поэтому этот алгоритм достаточно широко применяется на практике.
[править]Сравнение с другими алгоритмами
[править]Преимущества
Требует  памяти.
Приемлемое время работы на практике (см. выше). Благодаря этом алгоритм применяется, например, в браузерах и текстовых редакторах (при использовании Ctrl + F), потому что обычно паттерн, который нужно найти, очень короткий по сравнению с самим текстом. Также наивный алгоритм используется в стандартных библиотеках языков высокого уровня (C++, Java), потому что он не требует дополнительной памяти.
Простая и понятная реализация.
[править]Недостатки
Требует  операций, вследствие чего алгоритм работает медленно в случае, когда длина паттерна достаточно велика (см. выше).
    Алгоритм Рабина-Карпа
Алгоритм  Рабина-Карпа
Рабин и Карп изобрели алгоритм поиска подстрок, который эффективен на практике и к тому же обобщается на другие аналогичные задачи. В среднем он работает достаточно быстро.
Предположим для начала, что Х = {0, 1, 2, ..., 9} (в общем случае можно считать, что каждый символ в алфавите Х есть d-ичная цифра, где d= |Х|). Тогда строку из k символов можно рассматривать как десятичную запись числа (k-значного), а сами символы как цифры.
Если P[1..т] — образец, то через p обозначим число, десятичной записью которого он является; аналогично, если T[1..n] — текст, то для всех значений s =0,1,..., n-m обозначим через ts число, десятичной записью которого является строка T[s+ 1 .. s+ т]. Очевидно, s является допустимым сдвигом тогда и только тогда, когда ts= p. Если бы мы могли вычислить p за время О(m) и все ti,-за время O(n), то мы смогли бы найти все допустимые сдвиги за время О(n), сравнивая р со всеми ts по очереди.
Вычислить р за время О(m) действительно можно, используя схему Горнера:
P= Р[m] + 10(Р[m-1 ]+ 10(Р[m-2 ]+ ...+ 10(P[2]+ P[1])...)).
Точно так же за время O(m) можно вычислить t0.
Чтобы вычислить t1,t2,…tn-m за время O(n -m), можно воспользоваться формулой
ts+1= 10(ts-10m-1T[s+1])+T[s+m+1].
До сих пор мы не учитывали того, что числа р и t велики — настолько, что предположение о выполнении арифметических операций за время 0(1) едва ли допустимо. К счастью, эту трудность можно обойти следующим образом: надо проводить вычисления чисел р и t0 по модулю фиксированного числа q. Тогда все числа не превосходят q и можно считать, что число р и все tj будут действительно вычислены за время 0(n+ m). Обычно в качестве q выбирают простое число, для которого 10q помещается в машинное слово - это упрощает программирование вычислений. В общем случае (для алфавита {0, 1, 2, ..., d}) выбирают такое простое число d, что dq помещается в машинное слово (благодаря этому все арифметические операции происходят в пределах одного слова); последнее рекуррентное соотношение приобретает вид
ts+1=(d(ts-T[s+1]h)+T{s+m+1}mod q, где h = dm-1 (mod q).
Вычисления по модулю q хороши всем, кроме одного: из равенства ts = p (mod q) еще не следует, что ts =p. Поэтому, если ts ≠ p (mod q), то сдвиг s заведомо недопустим и о нем можно забыть, а если ts = p (mod q) , то надо еще проверить, совпадают ли строки Р[1..m] и T[s+1..s + m] на самом деле. Если совпадают, то мы нашли вхождение образца в строку, а если не совпадают, то произошло холостое срабатывание (spurious hit). Если простое число q достаточно велико, то можно надеяться, что дополнительные затраты на анализ холостых срабатываний будут невелики.
Метод хеширования
Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: , где  — это некоторое простое число, а  — некоторое большое число, для уменьшения числа коллизий (обычно берётся  или , чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.
При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за :.
.
Получается : .
[править]Алгоритм
Алгоритм начинается с подсчета  и .
Для  вычисляется  и сравнивается с . Если они оказались равны, то образец  скорее всего содержится в строке начиная с позиции , хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.
Для ускорения работы алгоритма оптимально предпосчитать .[править]Псевдокод
RabinKarp (s[1..n], p[1..m])
hp = hash(p[1..m])
h = hash(s[1..m])
for i = 1 to n - m + 1
if h == hp answer.add(i)
h = (p * h - p * hash(s[i]) + hash(s[i + m])) mod r
if answer.size() == 0
return not found
else return answerНовый хеш  был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что  — пустой символ.
[править]Время работы
Изначальный подсчёт хешей выполняется за . В цикле всего  итераций, каждая выполняется за . Итоговое время работы алгоритма .[править]Надёжность
Если количество подстрок данной строки превышает количество хешей, то наступление коллизий неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть высока, не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.
Например если взять , за  принять строку Туэ-Морса[1] длиной  , то алгоритм находит лишние вхождения почти в половине случаев.
    Конечный автомат (состояния, начальное сост., допускающее сост., входной алфавит, функция переходов)
Конечный автомат — абстрактный автомат, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют различные способы задания конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки: , где
 — входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;
 — множество состояний;
 — начальное состояние ; — множество заключительных состояний ; — функция переходов, определенная как отображение , такое, что , то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).
Конечный автомат начинает работу в состоянии q0, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.
Конечные автоматы широко используются на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспеченияна основе моделей.
Работа КА заключается в преобразовании входной цепочки символов в выходную. Закон этого преобразования определяет поведение КА. Задача проектирования КА состоит в создании КА, обеспечивающем заданные правила преобразования цепочек. Очевидно, что отсутствие у КА внутренней памяти ограничивает его возможности по преобразованию цепочек (общепринятый термин -моделирующая способность). С другой стороны, эти же ограничения позволяют решать в общем случае многие проблемы (термин – алгоритмическая разрешимость, т.е. принципиальная возможность разработать соответствующий алгоритм).
Хотя автоматы и можно представить в традиционной для алгоритма технологии блок-схем (управляющие КА так и строятся на основе разметки блок-схемы алгоритма), наиболее удобной формой их представления для человека является графическая - диаграмма состояний-переходов, а для программирования и формальных преобразований – табличная. Основные элементы диаграммы состояний – переходов:
состояние представляет собой окружность, содержащую номер или наименование состояния;
направленная дуга, соединяющая состояния Sk и Sm, определяется значениями функций переходов и действий: если  Sm=P(Sk,Ii) и On=D(Sk,Ii), то имеется переход КА из  Sk вSm , который обозначается дугой, соединяющей эти вершины. Дуга подписывается парой символов Ii/On . Это означает, что переход по дуге при поступлении на вход символа Iiсопровождается  формированием выходного символа On.
Если поведение какого-либо объекта можно описать набором предложений вида: «Находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D», то такая система будет представлять собой конечный автомат.

Анализируя приведенный здесь пример диаграммы состояний-переходов и вид преобразования цепочек, можно сделать вывод о поведении автомата и сущности выполняемых им преобразований. Нетрудно заметить, что получая входные цепочки, содержащие символы a и b в произвольном порядке, КА формирует аналогичные цепочки более регулярного вида. Так, из подряд идущих символов b он оставляет один, а в последовательности символов a оставляет все нечетные, кроме первого. При нечетном количестве символов a на входе КА добавляет еще один символ a в выходную последовательность.  Отсюда можно вычислить закон преобразования длины входной цепочки символов a  -  Na(out) = (Na(in)+1)/2
Анализируя состояния и условия переходов в них, можно определить их содержательный «смысл»: состояния S1 ,S2 обозначают нечетное и четное число подряд прочитанных символов a. 
Табличная форма представления КА включает в себя представление функций переходов и выходов виде таблиц.
 
P a b
S0 1 0
S1 2 0
S2 1 0
 
D a b
S0 b e
S1 e a
S2 a e
На диаграмме состояний-переходов не может быть двух и более дуг из одного состояния, помеченных одним и тем же входным символом.  Если это не так, то такая неканоническая форма называется недетерминарованным КА. Такой КА не имеет адекватного табличного (функционального) представления, но может быть преобразован в обычный детерминированный.
Автоматные модели в программировании
При разработке программ, характеризующейся сложной логикой управления, можно применять автоматный подход, который позволяет сделать текст программы более регулярным и компактным. То же самое решение можно применить, если программа активизируется внешними событиями (событийное программирование) и требуется отследить заданную последовательность наступления событий. В качестве примера, реализованного в виде автоматной модели, рассмотрим функцию, которая исключает из строки комментарии вида “ /* ... */ ”
Прежде всего, необходимо определить состояния автомата, возможные при просмотре очередного символа строки:
состояние 0 - идет обычный текст;
состояние 1 - обнаружен символ “/”;
состояние 2 - обнаружено начало комментария “/*”;
состояние 3 - в комментарии обнаружен символ “*”.
Программа будет выглядеть следующим образом:
 
void f(char in[],char out[])
{int i, s, j;                                              // s – текущее состояние автомата
for(i=0,s=0,j=0; in[i]!=0; i++)                    // i -  индекс текущего символа входной строки
switch(s)                                               // j – индекс текущего символа выходной строки
      {    
case 0: if (in[i])!=’/’ out[j++] = in[i];           // символы копируются только в состоянии 0
            else s=1;
            break;
case 1: if (in[i]!=’*’)  { out[j++]=in[i-1]; out[j++]=in[i]; s=0; }
            else s=2;
            break;
case 2: if (in[i]==’*’) s=3;
            break;
case 3: if (in[i]==’/’) s=0;
            break;
}}
Подробнее рассмотрим характерные особенности этой программы:
программа представляет собой цикл, в каждом шаге которой анализируется очередной символ из входной строки. Заметим, что только текущий. Программа принципиально не анализирует ни предыдущих, ни последующих символов. Текущий символ играет, таким образом. Роль входного сигнала, по которому автомат переходит из одного состояния в другое.
программа имеет переменную s, которая и представляет собой текущее состояние КА. В теле основного цикла программы выполняется переключение (switсh) по всем возможным значениям этой переменной - состояниям КА.
в каждом состоянии реализуется логика его перехода в другие состояния на основе анализа текущего символа - входного сигнала и вырабатывается соответствующее действие. Например, в состоянии 1, когда программа уже обнаружила символ “/” - возможное начало комментария, она проверяет, не является ли текущий символ “*”. Если это так, автомат переводится в состояние 2 - нахождение внутри комментария, если нет, то в выходную строку переписывается предыдущий “/” и текущий символы, а автомат возвращается в состояние 0.
    Автомат поиска подстрок (построение автомата, поиск подстрок с его помощью)
Автомат для поиска состоит из:
алфавита , из символов которого состоят текст и образец;
множества состояний ;допускающего состояния ;начального состояния ;множества переходов  из одного состояния в другое по символам .
Переход в  означает, что удалось найти вхождение образца в текст.
[править]Переходы между состояниями
[править]Прямые переходы
Пусть в нашем автомате пока одно состояние — . Пройдем по образцу, добавляя для каждого его символа новое состояние и переход в него из предыдущего состояния по этому символу. Последнее состояние объявим допускающим. Таким образом, каждому состоянию теперь соответствует ровно один префикс образца. Пронумеруем их длинами соответствующих префиксов с увеличением на единицу.
[править]Суффиксные ссылки
Теперь нужно расставить остальные переходы. В итоговом автомате при переходе в состояние  префикс образца —  — должен быть максимальным его префиксом, равным суффиксу текста до последнего просмотренного символа, включительно. Переходы, осуществляющие перемещение в такие префиксы, называют суффиксными ссылками.
В качестве базы построения суффиксных ссылок проведем из  по всем символам алфавита, кроме первого символа образца, ссылки в : длина максимального текущего суффикса текста, равного префиксу образца, увеличивается максимум на один и только в том случае, когда очередные их символы совпадают. Пусть построены все переходы из состояний, номер которых меньше некоторого . Тогда для того, чтобы определить направление ссылки из состояния  по символу , нужно найти длину наибольшего префикса образца, из состояния которого по  ведет прямой переход (если таких префиксов нет, значит, символ прежде не встречался в образце — нужно перейти в ).Префикс-функция, взятая многократно от  символа образца, позволяет перебрать все префиксы образца, равные суффиксу его первых  символов. Таким образом, , где справа описан прямой переход либо переход из . Так как все переходы из первых  состояний уже построены,  соответствует нужному состоянию.
Если забыть про разницу в построении прямых переходов и суффиксных ссылок, можно заметить, что переходы  решают поставленную задачу нахождения максимального суффикса текста, равного префиксу образца.
[править]Псевдокод
Построение автомата:
/*s — образец
m - длина образца
— алфавит
— размер алфавита
— префикс-функция образца
элементы строк и массивов нумеруются с единицы*/
trans = array[m + 1][] // заполнен элементами null, содержит множество переходов
for i = 1 to m:
trans[i][s[i]] = i + 1 // вставили прямые переходы
for every char in :
if char != s[1]:
trans[1][char] = 1 // вставили все переходы из стартового состояния
for i = 2 to m + 1:
for every char in :
if char != s[i]:
trans[i][char] = trans[][char] // вставляем суффиксные ссылки
Поиск вхождений образца в тексте:
/*t — текст
n — длина текста
m — длина образца
qs — стартовое состояние
qf — допускающее, то есть последнее, состояние
trans — полученный выше массив переходов
элементы строк и массивов нумеруются с единицы*/
state = qs // текущее состояние
for i = 1 to n:
if state == qf:
yield i - m // вывод позиции в тексте, начиная с которой, в него входит образец
state = trans[state][t[i]]
if state == qf:
yield n - m + 1 // образец является суффиксом текста
[править]Пример использования

Строка a b b a b
-функция 0 0 0 1 2
Состояние 1 2 3 4 5 6
Переходы по a 2 2 2 5 2 2
Переходы по b 1 3 4 1 6 4

    Префикс-функция, построение автомата поиска подстрок с ее использованием  (см. вики-конспекты)  
Префикс-функция (англ. prefix-function) от строки — массив длин наибольших  HYPERLINK "http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B8%D0%BE%D0%B4_%D0%B8_%D0%B1%D0%BE%D1%80%D0%B4%D0%B5%D1%80,_%D0%B8%D1%85_%D1%81%D0%B2%D1%8F%D0%B7%D1%8C" \l ".D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F" \o "Период и бордер, их связь" бордеров для каждой позиции этой строки
Здесь и далее считаем, что символы в строках нумеруются с .Определим префикс-функцию от строки  в позиции  следующим образом:  . Если мы не нашли такого , то 
Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за . Будем считать, что префикс-функция хранится в массиве .[править]Псевдокод
int[] prefixFunction(string s):
int[] p = int[s.length]
fill(p, 0)
for i = 1 to n
for k = 1 to i if s[1..k] == s[i - k + 1..i]
p[i] = k
return p
[править]Пример
Рассмотрим строку , для которой значение префикс-функции равно .
Шаг Строка Значение функции
a 0
ab0
abc0
abca1
abcab2
abcabc3
abcabcd0
[править]Время работы
Всего  итераций цикла, на каждой из который происходит сравнение строк за , что дает в итоге .
[править]Эффективный алгоритм
Вносятся несколько важных замечаний:
Заметим, что . Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции  и имеющий длину , удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции  и имеющий длину , следовательно неравенство  неверно.
Избавимся от явных сравнений строк. Пусть мы вычислили , тогда, если , то . Если окажется, что , то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому  HYPERLINK "http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B8%D0%BE%D0%B4_%D0%B8_%D0%B1%D0%BE%D1%80%D0%B4%D0%B5%D1%80,_%D0%B8%D1%85_%D1%81%D0%B2%D1%8F%D0%B7%D1%8C" \l ".D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F" \o "Период и бордер, их связь" бордеру наибольшей длины, для этого подберем такое , что . Делаем это следующим образом. За исходное  необходимо взять , что следует из первого пункта. В случае, когда символы  и  не совпадают,  — следующее потенциальное наибольшее значение , что видно из рисунка. Последнее утверждение верно, пока , что позволит всегда найти его следующее значение. Если , то  при  , иначе .

[править]Псевдокод
int[] prefixFunction(string s):
p[1] = 0
for i = 2 to n
k = p[i - 1]
while k > 0 and s[i] != s[k + 1]
k = p[k]
if s[i] == s[k + 1]
k++
p[i] = k
return p
[править]Время работы
Время работы алгоритма составит . Для доказательства этого нужно заметить, что итоговое количество итераций цикла  определяет асимптотику алгоритма. Теперь стоит отметить, что  увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение . Поскольку внутри цикла значение  лишь уменьшается, получается, что  не может суммарно уменьшиться больше, чем  раз. Значит цикл  в итоге выполнится не более  раз, что дает итоговую оценку времени алгоритма .
[править]Построение префикс-функции по Z-функции
[править]Постановка задачи
Дан массив с корректной Z-функцией для строки , получить за  массив с префикс-функцией для строки .
[править]Описание алгоритма
Пусть Z-функция хранится в массиве . Префикс-функцию будем записывать в массив . Заметим, что если  то для всех элементов с индексом , где , значение  будет не меньше, чем длина подстроки с  по , что равно  (как изображено на рисунке).
Также заметим, что если мы уже установили в какую-то позицию значение  с позиции , а потом пытаемся установить значение  c позиции , причём  и , то изменение с позиции  только уменьшит значение . Действительно, значение после первого присвоения . В итоге получаем алгоритм: идем слева направо по массиву  и, находясь на позиции , пытаемся записать в  от позиции  до  значение  где  пробегает все значения , пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.
Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только . Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество . Количество установленных значений — . А число тоже будет не больше , так как каждый  переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику .

[править]Псевдокод
int[] buildPrefixFunctionFromZFunction(int[] z):
int[] p = int[z.length]
fill(p, 0)
for i = 2 to z.length - 1
for j = z[i] - 1 downto 0
if p[i + j] > 0
break else p[i + j] = j + 1
return p
[править]Построение строки по префикс-функции
[править]Постановка задачи
Восстановить строку по префикс-функции за , считая алфавит неограниченным.
[править]Описание алгоритма
Здесь для удобства будем считать, что строки и массивы нумеруются с нуля.
Пусть в массиве  хранятся значения префикс-функции, в  будет записан ответ. Пойдем по массиву  слева направо.
Пусть мы хотим узнать значение . Для этого посмотрим на значение : если , тогда в  запишем новый символ, иначе . Обратим внимание, что нам уже известно, так как .[править]Реализация
string buildFromPrefix(int[] p):
s = ""
for i = 1 to p.length if p[i] == 0
s += new character
else s += s[p[i]]
return s
[править]Доказательство корректности алгоритма
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
Пусть  — данная префикс-функция, строку  построил наш алгоритм,  — массив значений префикс-функции для .
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива  прибавление нового символа не влияет, так как при подсчёте префикс-функции на -ой позиции рассматриваются символы на позициях не больше . Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
База очевидна для строки длины .Переход: пусть до -ой позиции мы построили строку, что . Возможны два случая:
. Тогда мы добавляем новый символ, поэтому  тоже будет равно .
. Бордер строки  имеет длину . Поэтому если дописать к строке  символ , то бордер нашей новой строки станет равен , как можно увидеть на рисунке.
Приближенные алгоритмы решения NP-трудных задач
    Понятие NP-трудности, NP-полноты
    Задача коммивояжера
    Приближенный алгоритм решения задачи коммивояжера
    Эволюционные алгоритмы
    Решение задачи коммивояжера с помощью эволюционного алгоритма

Приложенные файлы

  • docx 15818656
    Размер файла: 2 MB Загрузок: 1

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