Обход в глубину: различия между версиями
Материал из Algocode wiki
Debnatkh (обсуждение | вклад) (Новая страница: «'''Поиском в глубину''' (англ. ''depth-first search'', '''DFS''') называется рекурсивный алгоритм обхода д...») |
(нет различий)
|
Текущая версия на 00:27, 19 сентября 2019
Поиском в глубину (англ. 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);
}
Немного его модифицируем, а именно будем сохранять для каждой вершины, в какой момент мы в неё вошли и в какой вышли — соответствующие массивы будем называть \(tin\) и \(tout\).
Как их заполнить: заведем таймер, отвечающий за «время» на текущем состоянии обхода, и будем инкрементировать его каждый раз, когда заходим в новую вершину:
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\)-ам, то индексы любого поддерева всегда будут каким-то промежутком в этой нумерации.
Эти свойства часто бывают полезными в задачах на деревья.