Ad Code

Responsive Advertisement

Applications of DFS in Hindi

 

Depth-first search (DFS) एक ग्राफ को ट्रेस करने के लिए उपयोग किया जाने वाला Algorithmएल्गोरिदम है। निम्नलिखित समस्याएं हैं जो DFS का उपयोग उभड़ा हुआ ब्लॉक के रूप में करती हैं।


1) अनवीटेड ग्राफ के लिए, ग्राफ का DFS minimum spanning tree का उत्पादन करता है।

Applications of DFS
Applications of DFS



2) Detecting cycle in a graph : एक Graph में एक Cycle होता है यदि और केवल तभी जब हम DFS के दौरान बैक एज देखते हैं। तो हम
Graph के लिए DFS चला सकते हैं और बैक किनारों के लिए जांच कर सकते हैं।


3)  Path Finding: हम दो दिए गए वर्टीकल U और Z के बीच का रास्ता खोजने के लिए डीएफएस एल्गोरिथ्म का विशेषज्ञ बन सकते हैं।

i) शुरुआत के शीर्ष के रूप में U के साथ DFS(G, u) को कॉल करें।

ii) स्टार्ट वर्टेक्स और वर्तमान वर्टेक्स के बीच पथ का ट्रैक रखने के लिए स्टैक S का उपयोग करें।

iii) जैसे ही गंतव्य शीर्ष z का सामना करना पड़ता है, पथ को वापस कर दें

contents of the stack For Applications of DFS



4) Topological Sorting: Topological Sorting का उपयोग मुख्य रूप से  scheduling jobs के बीच दी गई निर्भरता से
jobs के निर्धारण के लिए किया जाता है। कंप्यूटर विज्ञान में, इस प्रकार के एप्लिकेशन इंस्ट्रूमेंटेशन, स्प्रेडशीट, लॉजिक सिंथेसिस में फार्मूला वैल्यू को पुनर्संयोजित करते समय फॉर्मूला सेल मूल्यांकन के आदेश, मेकफाइल्स, डेटा सीरियललाइज़ेशन में प्रदर्शन करने के लिए संकलन कार्यों के क्रम का निर्धारण और लिंकर्स में प्रतीक निर्भरता को हल करने में उत्पन्न होते हैं।


5)To test if a graph is bipartite: हम BFS या DFS में वृद्धि कर सकते हैं, जब हम पहली बार एक नया शीर्ष खोजते हैं, तो उसे उसके parents का विरोध करते हुए रंग दें, और एक दूसरे किनारे के लिए, यह जाँचें कि एक ही रंग के दो कोने लिंक न करें। किसी भी जुड़े घटक में पहला शीर्ष लाल या काला हो सकता है!


6) Finding Strongly Connected Components of a graph: यदि ग्राफ में प्रत्येक शीर्ष से हर दूसरे शीर्ष पर एक मार्ग हो तो निर्देशित ग्राफ को दृढ़ता से जोड़ा जाता है।


7) Solving puzzles with only one solution, जैसे कि मेज़। (DFS को केवल सेट किए गए मार्ग में वर्तमान मार्ग पर नोड्स सहित भूलभुलैया के सभी समाधान खोजने के लिए अनुकूलित किया जा सकता है।)

Post a Comment

0 Comments

Close Menu