Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Алгоритмы C++

.pdf
Скачиваний:
679
Добавлен:
15.03.2016
Размер:
6 Mб
Скачать

Нахождение Эйлерова пути за O (M)

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

Алгоритм

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

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

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

Искать все циклы и объединять их будем одной рекурсивной процедурой:

procedure FindEulerPath (V)

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

вызываем FindEulerPath из второго конца этого ребра;

2.добавляем вершину V в ответ.

Сложность этого алгоритма, очевидно, является линейной относительно числа рёбер. Но этот же алгоритм мы можем записать в нерекурсивном варианте:

stack St;

в St кладём любую вершину (стартовая вершина); пока St не пустой

пусть V - значение на вершине St;

если степень(V) = 0, то добавляем V к ответу; снимаем V с вершины St;

иначе

находим любое ребро, выходящее из V; удаляем его из графа;

второй конец этого ребра кладём в St;

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

Задача о домино

Приведём здесь классическую задачу на эйлеров цикл - задачу о домино.

Имеется N доминошек, как известно, на двух концах доминошки записано по одному числу (обычно от 1 до 6, но в нашем случае не важно). Требуется выложить все доминошки в ряд так, чтобы у любых двух соседних доминошек числа, записанные на их общей стороне, совпадали. Доминошки разрешается переворачивать.

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

Реализация

Приведенная ниже программа ищет и выводит эйлеров цикл или путь в графе, или выводит -1, если его не существует.

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

цикл), поступим таким образом: если V1 и V2 - это две вершины нечётной степени, то просто добавим ребро (V1,V2), в полученном графе найдём эйлеров цикл (он, очевидно, будет существовать), а затем удалим из ответа "фиктивное" ребро (V1,V2). Эйлеров цикл будем искать в точности так, как описано выше (нерекурсивной версией), и заодно по окончании этого алгоритма проверим, связный был граф или нет (если граф был не связный, то по окончании работы алгоритма в графе останутся некоторые рёбра, и в этом случае нам надо вывести -1).

Наконец, программа учитывает, что в графе могут быть изолированные вершины.

int main() {

int n;

vector < vector<int> > g (n, vector<int> (n));

... чтение графа в матрицу смежности ...

vector<int> deg (n); for (int i=0; i<n; ++i)

for (int j=0; j<n; ++j) deg[i] += g[i][j];

int first = 0;

while (!deg[first]) ++first;

int v1 = -1, v2 = -1; bool bad = false;

for (int i=0; i<n; ++i) if (deg[i] & 1)

if (v1 == -1) v1 = i;

else if (v2 == -1) v2 = i;

else

bad = true;

if (v1 != -1)

++g[v1][v2], ++g[v2][v1];

stack<int> st; st.push (first); vector<int> res; while (!st.empty())

{

int v = st.top(); int i;

for (i=0; i<n; ++i) if (g[v][i])

break;

if (i == n)

{

res.push_back (v); st.pop();

}

else

{

--g[v][i]; --g[i][v]; st.push (i);

}

}

if (v1 != -1)

for (size_t i=0; i+1<res.size(); ++i)

if (res[i] == v1 && res[i+1] == v2 || res[i] == v2

&& res[i+1] == v1)

{

vector<int> res2;

for (size_t j=i+1; j<res.size(); ++j) res2.push_back (res[j]);

for (size_t j=1; j<=i; ++j) res2.push_back (res[j]);

res = res2; break;

}

for (int i=0; i<n; ++i)

for (int j=0; j<n; ++j) if (g[i][j])

bad = true;

if (bad)

puts ("-1");

else

for (size_t i=0; i<res.size(); ++i) printf ("%d ", res[i]+1);

}

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

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

Решим эту задачу с помощью поиска в глубину за O (M).

Алгоритм

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

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

Реализация

Здесь приведена реализация для случая ориентированного графа.

int n;

vector < vector<int> > g; vector<char> cl; vector<int> p;

int cycle_st, cycle_end;

bool dfs (int v) { cl[v] = 1;

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

if (cl[to] == 0) { p[to] = v;

if (dfs (to)) return true;

}

else if (cl[to] == 1) {

cycle_end = v; cycle_st = to; return true;

}

}

cl[v] = 2; return false;

}

int main() {

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

p.assign (n, -1); cl.assign (n, 0); cycle_st = -1;

for (int i=0; i<n; ++i) if (dfs (i))

break;

if (cycle_st == -1)

puts ("Acyclic");

else {

puts ("Cyclic"); vector<int> cycle; cycle.push_back (cycle_st);

for (int v=cycle_end; v!=cycle_st; v=p[v]) cycle.push_back (v);

cycle.push_back (cycle_st);

reverse (cycle.begin(), cycle.end()); for (size_t i=0; i<cycle.size(); ++i)

printf ("%d ", cycle[i]+1);

}

}

Наименьший общий предок. Нахождение за O (sqrt (N)) и O (log N) с препроцессингом O (N)

Пусть дано дерево G. На вход поступают запросы вида (V1, V2), для каждого запроса требуется найти их наименьшего общего предка, т.е. вершину V, которая лежит на пути от корня до V1, на пути от корня до V2, и из всех таких вершин следует выбирать самую нижнюю. Иными словами, искомая вершина V - предок и V1, и V2, и среди всех таких общих предков выбирается нижний. Очевидно, что наименьший общий предок вершин V1 и V2 - это их общий предок, лежащий на кратчайшем пути из V1 в V2. В частности, например, если V1 является предком V2, то V1 является их наименьшим общим предком.

На английском эта задача называется задачей LCA - Least Common Ancestor.

Идея алгоритма

Перед тем, как отвечать на запросы, выполним так называемый препроцессинг. Запустим обход в глубину из корня, который будет строить список посещения вершин Order (текущая вершина добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына), нетрудно заметить, что итоговый размер этого списка будет O (N). И построим массив First[1..N], в котором для каждой вершины будет указана позиция в массиве Order, в которой стоит эта вершина, т.е. Order[First[I]] = I для всех I. Также с помощью поиска в глубину найдём высоту каждой вершины (расстояние от корня до неё) - H[1..N].

Как теперь отвечать на запросы? Пусть имеется текущий запрос - пара вершин V1 и V2. Рассмотрим список Order

между индексами First[V1] и First[V2]. Нетрудно заметить, что в этом диапазоне будет находиться и искомое LCA (V1, V2), а также множество других вершин. Однако LCA (V1, V2) будет отличаться от остальных вершин тем, что это

будет вершина с наименьшей высотой.

Таким образом, чтобы ответить на запрос, нам нужно просто найти вершину с наименьшей высотой в массиве Order в диапазоне между First[V1] и First[V2]. Таким образом, задача LCA сводится к задаче

RMQ ("минимум на отрезке"). А последняя задача решается с помощью структур данных (см. задача RMQ).

Если использовать sqrt-декомпозицию, то можно получить решение, отвечающее на запрос за O (sqrt (N)) и выполняющее препроцессинг за O (N).

Если использовать дерево отрезков, то можно получить решение, отвечающее на запрос за O (log (N)) и выполняющее препроцессинг за O (N).

Реализация

Здесь будет приведена готовая реализация LCA с использованием дерева отрезков:

typedef vector < vector<int> > graph;

typedef vector<int>::const_iterator const_graph_iter;

vector<int> lca_h, lca_dfs_list, lca_first, lca_tree; vector<char> lca_dfs_used;

void lca_dfs (const graph & g, int v, int h = 1)

{

lca_dfs_used[v] = true; lca_h[v] = h; lca_dfs_list.push_back (v);

for (const_graph_iter i = g[v].begin(); i != g[v].end(); ++i) if (!lca_dfs_used[*i])

{

lca_dfs (g, *i, h+1); lca_dfs_list.push_back (v);

}

}

void lca_build_tree (int i, int l, int r)

{

if (l == r)

lca_tree[i] = lca_dfs_list[l];

else

{

int m = (l + r) >> 1; lca_build_tree (i+i, l, m); lca_build_tree (i+i+1, m+1, r);

if (lca_h[lca_tree[i+i]] < lca_h[lca_tree[i+i+1]]) lca_tree[i] = lca_tree[i+i];

else

lca_tree[i] = lca_tree[i+i+1];

}

}

void lca_prepare (const graph & g, int root)

{

int n = (int) g.size(); lca_h.resize (n); lca_dfs_list.reserve (n*2); lca_dfs_used.assign (n, 0);

lca_dfs (g, root);

int m = (int) lca_dfs_list.size(); lca_tree.assign (lca_dfs_list.size() * 4 + 1, -1); lca_build_tree (1, 0, m-1);

lca_first.assign (n, -1); for (int i = 0; i < m; ++i)

{

int v = lca_dfs_list[i]; if (lca_first[v] == -1)

lca_first[v] = i;

}

}

int lca_tree_min (int i, int sl, int sr, int l, int r)

{

if (sl == l && sr == r) return lca_tree[i];

int sm = (sl + sr) >> 1; if (r <= sm)

return lca_tree_min (i+i, sl, sm, l, r); if (l > sm)

return lca_tree_min (i+i+1, sm+1, sr, l, r); int ans1 = lca_tree_min (i+i, sl, sm, l, sm);

int ans2 = lca_tree_min (i+i+1, sm+1, sr, sm+1, r); return lca_h[ans1] < lca_h[ans2] ? ans1 : ans2;

}

int lca (int a, int b)

{

int left = lca_first[a], right = lca_first[b];

if (left > right) swap (left, right);

return lca_tree_min (1, 0, (int)lca_dfs_list.size()-1, left, right);

}

int main()

{

graph g; int root;

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

lca_prepare (g, root);

for (;;)

{

int v1, v2; // поступил запрос

int v = lca (v1, v2); // ответ на запрос

}

}

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]