Euler порядок посещений вершин
Классифицировать рёбра можно по времени входа и выхода конечных вершин и ребра .
Такая классификация часто используется в различных задачах.
Выполняется DFS, и все встреченные рёбра классифицируются по следующим правилам:
Если вершина не посещена:
Если вершина уже посещена:
Обратные рёбра (Back Edges) — если является предком , то ребро является обратным.
Вершина является предком тогда и только тогда, когда мы уже вошли в , но ещё не вышли из неё.
Обратные рёбра завершают цикл, так как существует путь от предка к потомку (в дереве DFS) и ребро от потомка к предку (обратное ребро). Таким образом образуется цикл.
Циклы могут быть обнаружены с помощью обратных рёбер.
Прямые рёбра (Forward Edges) — если является потомком , то ребро является прямым.
Другими словами, если мы уже посетили и вышли из и при этом , то ребро является прямым.
Перекрёстные рёбра (Cross Edges) — если не является ни предком, ни потомком , то ребро является перекрёстным.
Другими словами, если мы уже посетили и вышли из и при этом , то ребро является перекрёстным.
Здесь:
Примечание:
При выполнении DFS каждой вершине сопоставляются два момента времени:
Если во время DFS записывать вершины в массив в порядке входа (по ), возникает ключевое свойство:
Все вершины поддерева вершины образуют непрерывный отрезок в порядке .
Вершина находится в поддереве вершины тогда и только тогда, когда
Это фундаментальное свойство DFS-нумерации.
DFS устроен так:
Следовательно:
Поэтому их значения лежат внутри интервала .
Вершина является предком вершины тогда и только тогда, когда
Свойство tin/tout позволяет свести задачи на дереве к задачам на массиве.
Поддерево вершины превращается в отрезок:
Поэтому многие задачи на деревьях решаются структурами для массивов:
int tim; // timer
int tin[N]; // time when dfs got in to vertex x
int tout[N]; // time when dfs gout out from vertex x
bool used[N]; // true if vertex x was visited
vector<int> v[N]; // edges
void dfs(int x) {
used[x] = true; // mark current vertex as visited
tin[x] = (++timer); // time when x is visited
for (int y: v[x]) {
if (used[y]) { // already visited vertex
if (tout[y] == 0) { // dfs didn't get out yet from vertex y
// back edge
} else if (tin[x] < tin[y]) {
// forward edge
} else {
// cross edge
}
continue;
}
// (x, y) is tree edge
dfs(y);
}
tout[x] = timer; // time when dfs gets out from vertex x
}