algorithm
गहराई पहली खोज

गहराई-पहली खोज का परिचय

गहराई-पहली खोज पेड़ या ग्राफ डेटा संरचनाओं को खोजने या खोजने के लिए एक एल्गोरिथ्म है। एक रूट पर शुरू होता है और बैकट्रैकिंग से पहले प्रत्येक शाखा के साथ जहाँ तक संभव हो पाता है। गहराई-पहली खोज के एक संस्करण की जांच 19 वीं शताब्दी के फ्रांसीसी गणितज्ञ चार्ल्स पियरे ट्रेमेक्स ने mazes को हल करने की रणनीति के रूप में की थी।

डेप्थ-फर्स्ट सर्च एक सोर्स वर्टेक्स से उपलब्ध सभी वर्टिकल को खोजने का एक व्यवस्थित तरीका है। चौड़ाई-पहली खोज की तरह, DFS किसी दिए गए ग्राफ़ के जुड़े घटक को पीछे छोड़ता है और एक फैले हुए वृक्ष को परिभाषित करता है। गहराई-पहली खोज का मूल विचार हर किनारे को व्यवस्थित रूप से खोज रहा है। हम आवश्यक के रूप में एक अलग कोने से शुरू करते हैं। जैसे ही हम एक शीर्ष खोजते हैं, डीएफएस (बीएफएस के विपरीत, जो एक कतार में एक शीर्ष डालता है, ताकि बाद में यह वहां से बाहर निकले) से खोज शुरू हो जाए।

आइए एक उदाहरण देखें। हम इस ग्राफ को पीछे छोड़ देंगे:

हम इन नियमों का पालन करते हुए ग्राफ को आगे बढ़ाएँगे:

• हम स्रोत से शुरू करेंगे।
• कोई भी नोड दो बार नहीं जाएगा।
• नोड्स हम अभी तक नहीं आए थे, सफेद रंग के होंगे।
• जिस नोड पर हम गए थे, लेकिन उसके सभी बच्चे नोड्स पर नहीं गए थे, रंगीन ग्रे होंगे।
• पूरी तरह से ट्रैवर्स किए गए नोड्स काले रंग के होंगे।

आइए इसे कदम से कदम मिलाकर देखें:

हम एक महत्वपूर्ण कीवर्ड देख सकते हैं। वह बैकएज है । आप देख सकते हैं। 5-1 को बैकेज कहा जाता है। ऐसा इसलिए है, क्योंकि हम अभी तक नोड -1 के साथ नहीं हैं, इसलिए दूसरे नोड से नोड -1 तक जाने का मतलब है कि ग्राफ में एक चक्र है। डीएफएस में, यदि हम एक ग्रे नोड से दूसरे में जा सकते हैं, तो हम निश्चित हो सकते हैं कि ग्राफ में एक चक्र है। यह एक ग्राफ में चक्र का पता लगाने के तरीकों में से एक है। स्रोत नोड और हमारे द्वारा देखे जाने वाले नोड्स के आदेश के आधार पर, हम चक्र में किसी भी किनारे का पता लगा सकते हैं। उदाहरण के लिए: यदि हम पहले 1 से 5 पर गए थे, तो हमने 2-1 को बैकडेज के रूप में पाया।

ग्रे नोड से सफ़ेद नोड तक जाने के लिए हम जो बढ़त लेते हैं उसे ट्री एज कहा जाता है। यदि हम केवल पेड़ के किनारे को रखते हैं और दूसरों को हटाते हैं, तो हमें DFS पेड़ मिलेगा।

अप्रत्यक्ष ग्राफ़ में, यदि हम पहले से ही विज़िट किए गए नोड पर जा सकते हैं, तो यह एक बैकडेज होना चाहिए। लेकिन निर्देशित रेखांकन के लिए, हमें रंगों की जांच करनी चाहिए। अगर हम केवल एक ग्रे नोड से दूसरे ग्रे नोड में जा सकते हैं, तो इसे एक बैकज कहा जाता है ।

डीएफएस में, हम प्रत्येक नोड के लिए टाइमस्टैम्प भी रख सकते हैं, जिसका उपयोग कई तरीकों से किया जा सकता है (जैसे: टोपोलॉजिकल सॉर्ट)।

1. जब नोड वी को सफेद से ग्रे में बदल दिया जाता है तो समय को d [v] में दर्ज किया जाता है।
2. जब नोड v को धूसर से बदलकर काला किया जाता है तो समय f [v] में दर्ज किया जाता है ।

यहाँ d [] का अर्थ है खोज समय और f [] का अर्थ है समय समाप्त करना । हमारे छद्म कोड की तरह दिखेगा:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

जटिलता:

प्रत्येक नोड और किनारों का एक बार दौरा किया जाता है। तो DFS की जटिलता O (V + E) है , जहाँ V नोड्स की संख्या को दर्शाता है और E किनारों की संख्या को दर्शाता है।

गहराई पहली खोज के आवेदन:

• एक अप्रत्यक्ष ग्राफ में सभी जोड़ी सबसे छोटा रास्ता खोजना।
• एक ग्राफ में चक्र का पता लगाना।
• रास्ता पाना।
• सामयिक क्रमबद्ध।
• एक ग्राफ द्विदलीय है तो परीक्षण।
• मजबूती से जुड़े घटक ढूँढना।
• एक समाधान के साथ पहेलियाँ सुलझाना।