e-maxx_algo

некоторые другие приложения дискретного преобразования Фурье.

Всевозможные суммы

Всевозможные скалярные произведения

Даны два массива и одной длины . Требуется вывести значения каждого скалярного произведения вектора на очередной циклический сдвиг вектора .

Поскольку все элементы , то мы получаем:

Две полоски

Даны две полоски, заданные как два булевских (т.е. числовых со значениями 0 или 1) массива и . Требуется

найти все такие позиции на первой полоске, что если приложить, начиная с этой позиции, вторую полоску, ни в каком месте не получится сразу на обеих полосках. Эту задачу можно переформулировать таким образом: дана карта полоски, в виде 0/1 — можно вставать в эту клетку или нет, и дана некоторая фигурка в виде шаблона (в виде массива, в котором 0 — нет клетки, 1 — есть), требуется найти все позиции в полоске, к которым можно приложить фигурку.

Эта задача фактически ничем не отличается от предыдущей задачи — задачи о скалярном произведении. Действительно, скалярное произведение двух 0/1 массивов — это количество элементов, в которых одновременно оказались единицы. Наша задача в том, чтобы найти все циклические сдвиги второй полоски так, чтобы не нашлось ни одного элемента, в котором бы в обеих полосках оказались единицы. Т.е. мы должны найти все циклические сдвиги второго массива, при которых скалярное произведение равно нулю.

Таким образом, эту задачу мы решили за .

Поиск в ширину

Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах.

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

Алгоритм работает за , где — число вершин, — число рёбер.

Описание алгоритма

На вход алгоритма подаётся заданный граф (невзвешенный), и номер стартовой вершины . Граф может быть как ориентированным, так и неориентированным, для алгоритма это не важно.

Сам алгоритм можно понимать как процесс "поджигания" графа: на нулевом шаге поджигаем только вершину . На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; т.е. за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).

Более строго это можно представить следующим образом. Создадим очередь , в которую будут помещаться

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

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

(для этого надо завести массив "предков" , в котором для каждой вершины хранить номер вершины, по которой мы попали в эту вершину).

Реализация

Реализуем вышеописанный алгоритм на языке C++. Входные данные:

vector < vector<int> > g; // граф int n; // число вершин

int s; // стартовая вершина (вершины везде нумеруются с нуля)

// чтение графа

...

Сам обход:

queue<int> q; q.push (s);

vector<bool> used (n);

vector<int> d (n), p (n); used[s] = true;

p[s] = -1;

while (!q.empty()) {

int v = q.front(); q.pop();

for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i];

if (!used[to]) { used[to] = true;

q.push (to);

d[to] = d[v] + 1; p[to] = v;

}

}

}

Если теперь надо восстановить и вывести кратчайший путь до какой-то вершины , это можно сделать следующим образом:

if (!used[to])

cout << "No path!";

else {

vector<int> path;

for (int v=to; v!=-1; v=p[v]) path.push_back (v);

reverse (path.begin(), path.end()); cout << "Path: ";

for (size_t i=0; i<path.size(); ++i) cout << path[i] + 1 << " ";

}

Приложения алгоритма

●Поиск кратчайшего пути в невзвешенном графе.

●Поиск компонент связности в графе за .

Для этого мы просто запускаем обход в ширину от каждой вершины, за исключением вершин, оставшихся

●Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа.

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

в ширину по графу, где состоянием (вершиной) является набор координат: координаты робота, и координаты всех коробок.

●Нахождение кратчайшего пути в 0-1-графе (т.е. графе взвешенном, но с весами равными только 0 либо 1): достаточно немного модифицировать поиск в ширину: если текущее ребро нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди.

●Нахождение кратчайшего цикла в неориентированном невзвешенном графе: производим поиск в ширину из каждой вершины; как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл, и останавливаем обход в ширину; среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.

путь из стартовой вершины в конечную, с чётностью, равной 0.

Задачи в online judges

Список задач, которые можно сдать, используя обход в ширину: ● SGU #213 "Strong Defence" [сложность: средняя]

Поиск в глубину

Это один из основных алгоритмов на графах.

В результате поиска в глубину находится лексикографически первый путь в графе. Алгоритм работает за O (N+M).

Применения алгоритма

●Поиск любого пути в графе.

●Поиск лексикографически первого пути в графе.

●Проверка, является ли одна вершина дерева предком другой:

В начале и конце итерации поиска в глубину будет запоминать "время" захода и выхода в каждой вершине. Теперь за O

(1) можно найти ответ: вершина i является предком вершины j тогда и только тогда, когда starti < startj и endi > endj.

●Задача LCA (наименьший общий предок).

●Топологическая сортировка:

Запускаем серию поисков в глубину, чтобы обойти все вершины графа. Отсортируем вершины по времени выхода по убыванию - это и будет ответом.

●Проверка графа на ацикличность и нахождение цикла

●Поиск компонент сильной связности:

Сначала делаем топологическую сортировку, потом транспонируем граф и проводим снова серию поисков в глубину в порядке, определяемом топологической сортировкой. Каждое дерево поиска - сильносвязная компонента.

●Поиск мостов:

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

Реализация

vector < vector<int> > g; // граф int n; // число вершин

vector<int> color; // цвет вершины (0, 1, или 2)

vector<int> time_in, time_out; // "времена" захода и выхода из вершины int dfs_timer = 0; // "таймер" для определения времён

void dfs (int v) {

time_in[v] = dfs_timer++; color[v] = 1;

for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (color[*i] == 0)

dfs (*i);

color[v] = 2;

time_out[v] = dfs_timer++;

}

Это наиболее общий код. Во многих случаях времена захода и выхода из вершины не важны, так же как и не важны цвета вершин (но тогда надо будет ввести аналогичный по смыслу булевский массив used). Вот наиболее

простая реализация:

vector < vector<int> > g; // граф int n; // число вершин

vector<char> used;

void dfs (int v) { used[v] = true;

for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (!used[*i])

dfs (*i);

}

Топологическая сортировка

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

Иными словами, требуется найти перестановку вершин (топологический порядок), соответствующую порядку, задаваемому всеми рёбрами графа.

Топологическая сортировка может быть не единственной (например, если граф — пустой; или если есть три такие вершины , , , что из есть пути в и в , но ни из в , ни из в добраться нельзя).

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

Распространённая задача на топологическую сортировку — следующая. Есть переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из вершин.

Алгоритм

Для решения воспользуемся обходом в глубину.

Предположим, что граф ацикличен, т.е. решение существует. Что делает обход в глубину? При запуске из какойто вершины он пытается запуститься вдоль всех рёбер, исходящих из . Вдоль тех рёбер, концы которых уже были посещены ранее, он не проходит, а вдоль всех остальных — проходит и вызывает себя от их концов.

Таким образом, к моменту выхода из вызова все вершины, достижимые из как непосредственно (по

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

получится топологическая сортировка.

Эти объяснения можно представить и в несколько ином свете, с помощью понятия "времени выхода" обхода в глубину. Время выхода для каждой вершины — это момент времени, в который закончил работать вызов

обхода в глубину от неё (времена выхода можно занумеровать от до ). Легко понять, что при обходе в

топологическая сортировка — это сортировка в порядке убывания времён выхода.

Реализация

Приведём реализацию, предполагающую, что граф ацикличен, т.е. искомая топологическая сортировка существует. При необходимости проверку графа на ацикличность легко вставить в обход в глубину, как описано в статье по обходу

вглубину.

int n; // число вершин vector<int> g[MAXN]; // граф bool used[MAXN];

vector<int> ans; void dfs (int v) {

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i];

if (!used[to]) dfs (to);

}

ans.push_back (v);

}

void topological_sort() {

for (int i=0; i<n; ++i) used[i] = false;

ans.clear();

for (int i=0; i<n; ++i) if (!used[i])

dfs (i);

reverse (ans.begin(), ans.end());

}

Здесь константе следует задать значение, равное максимально возможному числу вершин в графе.

Основная функция решения — это topological_sort, она инициализирует пометки обхода в глубину, запускает его, и ответ в итоге получается в векторе .

Задачи в online judges

Список задач, в которых требуется искать топологическую сортировку:

Алгоритм поиска компонент связности в графе

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

Алгоритм решения

Для решения можно воспользоваться как обходом в глубину, так и обходом в ширину.

Фактически, мы будем производить серию обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл — образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности. И так далее, пока все вершины не станут помеченными.

же вершины дважды, а, значит, каждое ребро будет просмотрено ровно два раза (с одного конца и с другого конца).

Реализация

Для реализации чуть более удобным является обход в глубину:

int n;

vector<int> g[MAXN]; bool used[MAXN]; vector<int> comp;

void dfs (int v) { used[v] = true;

comp.push_back (v);

for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i];

if (! used[to]) dfs (to);

}

}

void find_comps() {

for (int i=0; i<n; ++i) used[i] = false;

for (int i=0; i<n; ++i) if (! used[i]) {

comp.clear(); dfs (i);

cout << "Component:";

for (size_t j=0; j<comp.size(); ++j) cout << ' ' << comp[j];

cout << endl;

}

}

Основная функция для вызова — , она находит и выводит компоненты связности графа.

Мы считаем, что граф задан списками смежности, т.е. содержит список вершин, в которые есть рёбра из вершины

. Константе следует задать значение, равное максимально возможному количеству вершин в графе. Вектор содержит список вершин в текущей компоненте связности.

Поиск компонент сильной связности, построение конденсации графа

Определения, постановка задачи

Дан ориентированный граф , множество вершин которого и множество рёбер — . Петли и кратные рёбра допускаются. Обозначим через количество вершин графа, через — количество рёбер.

Компонентой сильной связности (strongly connected component) называется такое (максимальное

по включению) подмножество вершин , что любые две вершины этого подмножества достижимы друг из друга, т.е.

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

Алгоритм

Описываемый здесь алгоритм был предложен независимо Косараю (Kosaraju) и Шариром (Sharir) в 1979 г. Это очень простой в реализации алгоритм, основанный на двух сериях поисков в глубину, и потому работающий за

время .

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

связности как минимум из величин для всех .

● Первой была достигнута компонента . Опять же, в какой-то момент времени обход в глубину заходит в

Доказанная теорема является основой алгоритма поиска компонент сильной связности. Из неё следует,

некоторая вершина , принадлежащая "корневой" компоненте сильной связности, т.е. в которую не входит ни одно ребро в графе конденсаций. Теперь нам хотелось бы запустить такой обход из этой вершины , который бы посетил только эту компоненту сильной связности и не зашёл ни в какую другую; научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из графа вершины первой выделенной компоненты, мы снова найдём среди оставшихся вершину с наибольшей величиной , снова запустим из неё этот обход, и т.д.

из рассматриваемой нами "корневой" компоненты уже не будут выходить рёбра в другие компоненты.

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

, достаточно запустить обход из вершины в графе . Этот обход посетит все вершины этой компоненты

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

из неё, и т.д.

Итак, мы построили следующий алгоритм выделения компонент сильной связности:

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

Наконец, уместно отметить связь с понятием топологической сортировки. Во-первых, шаг 1

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

Реализация

vector < vector<int> > g, gr; vector<char> used; vector<int> order, component;

void dfs1 (int v) { used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) if (!used[ g[v][i] ])

dfs1 (g[v][i]); order.push_back (v);

}

void dfs2 (int v) { used[v] = true;

component.push_back (v);

for (size_t i=0; i<gr[v].size(); ++i) if (!used[ gr[v][i] ])

dfs2 (gr[v][i]);

}

int main() {