В этой статье рассмотрены основные применения обхода в глубину: топологическая сортировка, нахождение компонент сильной связности, решение задачи 2-SAT, нахождение мостов и точек сочленения, а также построение эйлерова пути и цикла в графе.
Поиском в глубину (англ. depth-first search, DFS) называется рекурсивный алгоритм обхода дерева или графа, начинающий в корневой вершине (в случае графа её может быть выбрана произвольная вершина) и рекурсивно обходящий весь граф, посещая каждую вершину ровно один раз.
const int maxn = 1e5;
bool used[maxn]; // тут будем отмечать посещенные вершины
void dfs(int v) {
used[v] = true;
for (int u : g[v])
if (!used[u])
dfs(v);
}Немного его модифицируем, а именно будем сохранять для каждой вершины, в какой момент мы в неё вошли и в какой вышли — соответствующие массивы будем называть
Как их заполнить: заведем таймер, отвечающий за «время» на текущем состоянии обхода, и будем инкрементировать его каждый раз, когда заходим в новую вершину:
int tin[maxn], tout[maxn];
int t = 0;
void dfs(int v) {
tin[v] = t++;
for (int u : g[v])
if (!used[u])
dfs(u);
tout[v] = t; // иногда счетчик тут тоже увеличивают
}У этих массивов много полезных свойств:
- Вершина
$u$ является предком$v$ $\iff tin_v \in [tin_u, tout_u)$ . Эту проверку можно делать за константу. - Два полуинтервала —
$[tin_v, tout_v)$ и$[tin_u, tout_u)$ — либо не пересекаются, либо один вложен в другой. - В массиве
$tin$ есть все числа из промежутка от 0 до$n-1$ , причём у каждой вершины свой номер. - Размер поддерева вершины
$v$ (включая саму вершину) равен$tout_v - tin_v$ . - Если ввести нумерацию вершин, соответствующую
$tin$ -ам, то индексы любого поддерева всегда будут каким-то промежутком в этой нумерации.
Эти свойства часто бывают полезными в задачах на деревья.
Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.
Определение. Точкой сочленения называется врешина, при удалении которой связный неориентированный граф становится несвязным.
Пример задачи, где их интересно искать: дана топология сети (компьютеры и физические соединения между ними) и требуется установить все единые точки отказа — узлы и связи, без которых будут существовать два узла, между которыми не будет пути.
Наивный алгоритм поочередного удаления каждого ребра
Запустим DFS из произвольной вершины. Введем новые виды рёбер:
-
Прямые рёбра — те, по которым были переходы в dfs.
-
Обратные рёбра — то, по которым не было переходов в dfs.
Заметим, что никакое обратное ребро
Значит, остается только проверить все прямые рёбра. Это уже немного лучше — такой алгоритм будет работать за
Сооптимизировать его до линейного времени (до одного прохода dfs) поможет замечание о том, что обратные рёбра могут вести только «вверх» — к какому-то предку в дереве обхода графа, но не в другие «ветки» — иначе бы dfs увидел это ребро раньше, и оно было бы прямым, а не обратным.
Тогда, чтобы определить, является ли прямое ребро
Для ясности, обозначим эту величину как
Если это условие (
const int maxn = 1e5;
bool used[maxn];
int h[maxn], d[maxn];
void dfs(int v, int p = -1) {
used[u] = true;
d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
for (int u : g[v]) {
if (u != p) {
if (used[u]) // если рябро обратное
d[v] = min(d[v], h[u]);
else { // если рябро прямое
dfs(u, v);
d[v] = min(d[v], d[u]);
if (h[v] < d[v]) {
// ребро (v, u) -- мост
}
}
}
}
}Примечание. Более известен алгоритм, вместо глубин вершин использующий их
Задача поиска точек сочленения не сильно отличается от задачи поиска мостов.
Вершина
Используя этот факт, можно оставить алгоритм практически прежним — нужно проверить этот критерий для всех прямых рёбер
void dfs(int v, int p = -1) {
used[u] = 1;
d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
int children = 0; // случай с корнем обработаем отдельно
for (int u : g[u]) {
if (u != p) {
if (used[u])
d[v] = min(d[v], h[u]);
else {
dfs(u, v);
d[v] = min(d[v], d[u]);
if (dp[v] >= tin[u] && p != -1) {
// u -- точка сочленения
}
children++;
}
}
}
if (p == -1 && children > 1) {
// v -- корень и точка сочленения
}
}Единственный крайний случай — это корень, так как в него мы по определению войдём раньше других вершин. Но фикс здесь очень простой — достаточно посмотреть, было ли у него более одной ветви в обходе (если корень удалить, то эти поддеревья станут несвязными между собой).
Задача топологической сортировки графа звучит так: дан ориентированный граф, нужно упорядочить его вершины в массиве так, чтобы все графа рёбра вели из более ранней вершины в более позднюю.
Это может быть полезно, например, при планировании выполнения связанных задач: вам нужно одеться, в правильном порядке надев шорты (1), штаны (2), ботинки (3), подвернуть штаны (4) — как хипстеры — и завязать шнурки (5).
Во-первых, сразу заметим, что граф с циклом топологически отсортировать не получится — как ни располагай цикл в массиве, все время идти вправо по ребрам цикла не получится.
Во-вторых, верно обратное. Если цикла нет, то его обязательно можно топологически отсортировать — сейчас покажем, как.
Заметим, что вершину, из которой не ведет ни одно ребро, можно всегда поставить последней, а такая вершина в ациклическом графе всегда есть (иначе можно было бы идти по обратным рёбрам бесконечно). Из этого сразу следует конструктивное доказательство: будем итеративно класть в массив вершину, из которой ничего не ведет, и убирать ее из графа. После этого процесса массив надо будет развернуть.
Этот алгоритм проще реализовать, обратив внимание на времена выхода вершин в dfs. Вершина, из которой мы выйдем первой — та, у которой нет новых исходящих ребер. Дальше мы будем выходить только из тех вершин, которые если имеют исходящие ребра, то только в те вершины, из которых мы уже вышли.
Следовательно, достаточно просто выписать вершины в порядке выхода из dfs, а затем полученный список развернуть, и мы получим какую-то из корректных топологических сортировок.
Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? В них тоже иногда требуется найти какую-то структуру.
Для этого можно ввести понятие сильной связности.
Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.
Понятно, что такое отношение транзитивно: если
Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.
Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать. Задачу о сжатии каждой компоненты сильной связности в одну вершину называют конденсацией графа, и её решение мы сейчас опишем.
Если мы знаем, какие вершины лежат в каждой компоненте сильной связности, то построить граф конденсации несложно: дальше нужно лишь провести некоторые манипуляции со списками смежности. Поэтому сразу сведем исходную задачу к нахождению самих компонент.
Лемма. Запустим dfs. Пусть
Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.
Пусть первой была достигнута компонента
Второй случай проще: из
Из этого факта следует первая часть решения. Отсортируем вершины по убыванию времени выхода (как бы сделаем топологическую сортировку, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины в сортировке. В эту компоненту точно не входят никакие рёбра из других компонент — иначе нарушилось бы условие леммы, ведь у первой вершины
После того, как мы сделали это с первой вершиной, мы можем пойти по топологически отсортированному списку дальше и делать то же самое с вершинами, для которых компоненту связности мы ещё не отметили.
vector<int> g[maxn], t[maxn];
vector<int> order;
bool used[maxn];
int component[maxn];
int cnt_components = 0;
// топологическая сортировка
void dfs1(int v) {
used[v] = true;
for (int u : g[v]) {
if (!used[u])
dfs1(u);
order.push_back(v);
}
// маркировка компонент сильной связности
void dfs2(int v) {
component[v] = cnt_components;
for (int u : t[v])
if (cnt_components[u] == 0)
dfs2(u);
}
// в содержательной части main:
// транспонируем граф
for (int v = 0; v < n; v++)
for (int u : g[v])
t[u].push_back(v);
// запускаем топологическую сортировку
for (int i = 0; i < n; i++)
if (!used[i])
dfs1(i);
// выделяем компоненты
reverse(order.begin(), order.end());
for (int v : order)
if (component[v] == 0)
dfs2(v);TL;DR:
-
Сортируем вершины в порядке убывания времени выхода.
-
Проходимся по массиву вершин в этом порядке, и для ещё непомеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компонентой связности.
После этого номера компонент связности будут топологически отсортированы.
Ликбез. Конъюнкция — это «правильный» термин для логического «И» (обозначается true тогда и только тогда, когда обе переменные true.
Ликбез. Дизъюнкция — это «правильный» термин для логического «ИЛИ» (обозначается false тогда и только тогда, когда обе переменные false.
Рассмотрим конъюнкцию дизъюнктов, то есть «И» от «ИЛИ» от каких-то перемений или их отрицаний. Например, такое выражение:
(a | b) & (!c | d) & (!a | !b)Если буквами: (А ИЛИ B) И (НЕ C ИЛИ D) И (НЕ A ИЛИ НЕ B).
Можно показать, что любую логическую формулу можно представить в таком виде.
Задача satisfiability (SAT) заключается в том, чтобы найти такие значения переменных, при которых выражение становится истинным, или сказать, что такого набора значений нет. Для примера выше такими значениями являются a=1, b=0, c=0, d=1 (убедитесь, что каждая скобка стала true).
В случае произвольных формул эта задача быстро не решается. Мы же хотим решить её частный случай — когда у нас в каждой скобке ровно две переменные (2-SAT).
Казалось бы — причем тут графы? Заметим, что выражение
Затем построим граф импликаций: для каждой переменной в графе будет по две вершины, (обозначим их через
Заметим, что если для какой-то переменной
Оказывается, что это условие является не только достаточным, но и необходимым. Доказательством этого факта служит описанный ниже алгоритм.
Переформулируем данный критерий в терминах теории графов. Если из одной вершины достижима вторая и наоборот, то эти две вершины находятся в одной компоненте сильной связности. Тогда критерий существования решения звучит так: для того, чтобы задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной
Пусть решение существует, и нам надо его найти. Заметим, что, несмотря на то, что решение существует, для некоторых переменных может выполняться, что из
Утверждается следующее. Пусть
Докажем, что при таком выборе значений мы не придём к противоречию. Пусть, для определённости, выбрана вершина
Во-первых, докажем, что из
Во-вторых, докажем, что из любой вершины
Итак, мы построили алгоритм, который находит искомые значения переменных в предположении, что для любой переменной
Определение. Эйлеров путь — это путь в графе, проходящий через все его рёбра.
Определение. Эйлеров цикл — это эйлеров путь, являющийся циклом.
Для простоты в обоих случаях будем считать, что граф неориентированный.
Также существует понятие гамильтонова пути и цикла — они посещают все вершины по разу, а не рёбра. Нахождение гамильтонова цикла (задача коммивояжера, англ. travelling salesman problem) — одна из самых известных NP-полных задач, в то время как нахождение эйлерового цика решается за линейное время — и мы сейчас покажем, как.
Теорема. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны.
Доказательство. Необходимость показывается так: можно просто взять эйлеров цикл и ориентировать все его ребра в порядке обхода. Тогда из каждой вершины будет выходить столько же рёбер, сколько входить, а значит степень у всех вершин исходного неориентированного графа была четной.
Достаточность докажем конструктивно — предъявим алгоритм нахождения.
const int maxn = 1e5;
set<int> g[maxn];
void euler(int v) {
while (!g[v].empty()) {
u = *g[v].begin();
g[v].erase(g[v].begin());
dfs(u);
}
cout << v << " ";
}Если условие на четность степеней вершин выполняется, то этот алгоритм действительно выводит эйлеров цикл, то есть последовательность из
Следствие. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями не превосходит 2.
Кстати, аналогичная теорема есть и для ориентированного графа (можете сами попытаться сформулировать).
Доказать это можно например через лемму о рукопожатиях.
Как теперь мы будем решать задачу нахождения цикла в предположении, что он точно есть. Давайте запустимся из произвольной вершины, пройдем по любому ребру и удалим его.
void euler(int v){
stack >s;
s.push({v, -1});
while (!s.empty()) {
v = s.top().first;
int x = s.top().second;
for (int i = 0; i < g[v].size(); i++){
pair e = g[v][i];
if(!u[e.second]){
u[e.second]=1;
s.push(e);
break;
}
}
if (v == s.top().first) {
if (~x) {
p.push_back(x);
}
s.pop();
}
}
}Упражнение. Сформулируйте и докажите аналогичные утверждения для случая ориентированного графа.