ग्राफ के लिए डेप्थ-फर्स्ट सर्च समान हैं। लेकिन डायग्राफ या निर्देशित ग्राफ (directed graphs) के लिए, हम कुछ प्रकार के किनारे ढूंढ सकते हैं। DFS एल्गोरिदम एक ट्री बनाता है जिसे DFS ट्री कहा जाता है। चार प्रकार के किनारे होते हैं:
ट्री एज (Tree Edge - T) – वे किनारे जो DFS ट्री में मौजूद हैं
फॉरवर्ड एज (Forward Edge - F) – ट्री किनारों के एक सेट के समानांतर। (छोटे DFS नंबर से बड़े DFS नंबर तक, और बड़े DFS पूर्णता नंबर से छोटे DFS पूर्णता नंबर तक)
बैकवर्ड एज (Backward Edge - B) – बड़े DFS नंबर से छोटे DFS नंबर तक और छोटे DFS पूर्णता नंबर से बड़े DFS पूर्णता नंबर तक।
क्रॉस एज (Cross Edge - C) – बड़े DFS नंबर से छोटे DFS नंबर तक, और बड़े DFS पूर्णता नंबर से छोटे DFS पूर्णता नंबर तक।
मान लीजिए हमारे पास नीचे जैसा ग्राफ है:
अब हम A को प्रारंभिक शीर्ष मानकर DFS करेंगे, और DFS नंबर और DFS पूर्णता नंबर डालेंगे। तो ट्री नीचे जैसा दिखेगा:
इसलिए DFS ट्रैवर्सल है: A, B, F, D, G, C, E
ट्री किनारे हैं: T = {(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}
फॉरवर्ड किनारे हैं: F = {(A, G)}
बैकवर्ड किनारे हैं: B = {(G, B)}
क्रॉस किनारे हैं: C = {(G, D)}
