DFS cho đồ thị có hướng (digraph) tương tự đồ thị vô hướng, nhưng có thêm phân loại cạnh. Thuật toán DFS tạo thành cây DFS. Có 4 loại cạnh:
- Tree Edge (T) – Cạnh nằm trong cây DFS.
- Forward Edge (F) – Song song với tập cạnh cây (từ số DFS nhỏ đến lớn, số hoàn thành DFS lớn đến nhỏ).
- Backward Edge (B) – Từ số DFS lớn đến nhỏ, số hoàn thành nhỏ đến lớn.
- Cross Edge (C) – Từ số DFS lớn đến nhỏ, số hoàn thành lớn đến nhỏ.
Giả sử đồ thị:
Thực hiện DFS từ A, gán số DFS và số hoàn thành. Cây DFS:
DFS traversal: A, B, F, D, G, C, E
Tree edges: T = {(A,B), (B,F), (F,D), (F,G), (A,C), (C,E)}
Forward edges: F = {(A,G)}
Backward edges: B = {(G,B)}
Cross edges: C = {(G,D)}