Consider performing Depth-First Search (DFS) on an undirected and unweighted graph $\bar{G}$ starting at vertex $S$. For any vertex $u$ in $G$, where $d[u]$ is the length of the shortest path from $S$ to $u$, let $(u \geqslant v)$ be an edge in $G$ such that $d[u] < d[v]$.
If $u$ is explored first in the DFS traversal in the direction from $u$ to $v$, then in the above DFS, the edge $(u, v)$ becomes:
- A forward edge
- A back edge
- A cross edge
- A tree edge
