Euler order of visiting vertices
Edges can be classified by the entry and exit times of the end vertices and of the edge .
Such a classification is often used in various problems.
DFS is performed, and all encountered edges are classified according to the following rules:
If vertex is not visited:
If vertex is already visited:
Back Edges — if is an ancestor of , then the edge is a back edge.
Vertex is an ancestor of if and only if we have already entered , but have not yet exited it.
Back edges complete a cycle, since there exists a path from the ancestor to the descendant (in the DFS tree) and an edge from the descendant to the ancestor (a back edge). Thus a cycle is formed.
Cycles can be detected using back edges.
Forward Edges — if is a descendant of , then the edge is a forward edge.
In other words, if we have already visited and exited and at the same time , then the edge is a forward edge.
Cross Edges — if is neither an ancestor nor a descendant of , then the edge is a cross edge.
In other words, if we have already visited and exited and at the same time , then the edge is a cross edge.
Here:
Note:
When performing DFS, each vertex is assigned two moments in time:
If during DFS we write vertices into an array in the order of entry (by ), a key property arises:
All vertices of the subtree of vertex form a continuous segment in order.
Vertex is in the subtree of vertex if and only if
This is a fundamental property of DFS numbering.
DFS is arranged as follows:
Therefore:
Therefore their values lie within the interval .
Vertex is an ancestor of vertex if and only if
The tin/tout property makes it possible to reduce problems on a tree to problems on an array.
A vertex’s subtree turns into a segment:
Therefore many problems on trees are solved with data structures for arrays:
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
}