डेटा संरचना में एक डिग्राफ पर गहराई-पहली खोज

ग्राफ की पहली गहराई खोज समान होती है। लेकिन डिग्राफ या निर्देशित ग्राफ के लिए, हम कुछ प्रकार के किनारों को पा सकते हैं। DFS एल्गोरिथम एक ट्री बनाता है जिसे DFS ट्री कहा जाता है। किनारों के चार प्रकार होते हैं जिन्हें -

• ट्री एज (T) − वे किनारे जो DFS ट्री में मौजूद होते हैं

• फॉरवर्ड एज (F) - पेड़ के किनारों के एक सेट के समानांतर। (छोटी डीएफएस संख्या से बड़ी डीएफएस संख्या तक, और बड़ी डीएफएस पूर्ण संख्या से छोटी डीएफएस पूर्णता संख्या तक)

• पिछड़ा किनारा (B) - बड़ी डीएफएस संख्या से छोटी डीएफएस संख्या और छोटी डीएफएस पूर्णता संख्या से बड़ी डीएफएस पूर्णता संख्या तक।

• क्रॉस एज (सी) - छोटी डीएफएस संख्या से बड़ी डीएफएस संख्या, और छोटी डीएफएस पूर्णता संख्या से बड़ी डीएफएस पूर्णता संख्या।

मान लीजिए कि हमारे पास नीचे जैसा ग्राफ है -

अब हम A को प्रारंभिक शीर्ष मानकर DFS निष्पादित करेंगे, और DFS संख्या और DFS पूर्णता संख्याएँ डालेंगे। तो पेड़ नीचे जैसा दिखेगा -

तो DFS ट्रैवर्सल A, B, F, D, G, C, E

पेड़ के किनारे हैं - टी ={(ए, बी), (बी, एफ), (एफ, डी), (एफ, जी), (ए, सी), (सी, ई)}

आगे के किनारे हैं - F ={(A, G)}

पीछे के किनारे हैं - B ={(G, B)}

क्रॉस किनारों हैं −C ={(G, D)}