सामयिक छँटाई

टोपोलॉजिकल सॉर्ट (टोपोलॉजिकल सॉर्ट) - ग्राफ़ पर मुख्य एल्गोरिदम में से एक, जिसका उपयोग कई और अधिक जटिल समस्याओं को हल करने के लिए किया जाता है।

एक ग्राफ के टोपोलॉजिकल सॉर्टिंग का कार्य निम्नानुसार है: इसके शीर्ष पर एक रैखिक क्रम को इंगित करें जैसे कि कोई भी किनारा एक शीर्ष से कम संख्या के साथ एक शीर्ष से एक शीर्ष पर जाता है। जाहिर है, अगर ग्राफ में चक्र है, तो यह आदेश मौजूद नहीं है।

एक उन्मुख नेटवर्क (या सिर्फ एक नेटवर्क) को एक रूपरेखा-मुक्त उन्मुख ग्राफ कहा जाता है। इस तरह के कार्यों में, केवल परिमित नेटवर्क पर विचार किया जाता है।

Orted एक उन्मुख अनारक्षित ग्राफ का उदाहरण जिसमें टोपोलॉजिकल सॉर्टिंग लागू है

यह उस आकृति से देखा जा सकता है कि ग्राफ को क्रमबद्ध नहीं किया गया है, क्योंकि संख्या 4 के साथ शीर्ष से किनारे कम संख्या ( 2 ) के साथ शीर्ष पर जाता है।

टोपोलॉजिकल सॉर्टिंग के कई तरीके हैं - सबसे प्रसिद्ध से:

• Demucron का एल्गोरिथम
• कई स्तरों के रूप में ग्राफ का प्रतिनिधित्व करने के लिए छँटाई विधि
• गहराई ट्रैवर्सल का उपयोग करके टोपोलॉजिकल सॉर्टिंग विधि

मैं बाद वाले पर ध्यान केंद्रित करूंगा, क्योंकि यह सबसे लोकप्रिय, दृश्य और लागू करने में आसान है।

एल्गोरिथ्म का सार

डेप्थ-फर्स्ट सर्च या डेप्थ-फर्स्ट सर्च (शॉर्ट के लिए डीएफएस ) ग्राफ ट्रैवर्सल तरीकों में से एक है। खोज एल्गोरिथ्म को निम्नानुसार वर्णित किया गया है: प्रत्येक शीर्ष के लिए जो पारित नहीं हुआ है, सभी आसन्न कोने ढूंढना आवश्यक है जो पारित नहीं हुए हैं और उनके लिए खोज दोहराते हैं।

आप Habré पर एक लेख में गहराई से खोज के बारे में अधिक पढ़ सकते हैं।

हम गहराई में ट्रैवर्सल शुरू करते हैं, और जब शीर्ष को संसाधित किया जाता है, तो हम इसे स्टैक पर धक्का देते हैं। दौरे के अंत में, चोटियों को ढेर से बाहर गहराई में ले जाया जाता है। स्टैक से खींचने के क्रम में नए नंबर असाइन किए गए हैं।

रंग: 3 रंगों का उपयोग गहराई से चलने के दौरान किया जाता है। प्रारंभ में, सभी चोटियां सफेद हैं। जब शीर्ष की खोज की जाती है, तो इसे ग्रे रंग दें। जब इससे जुड़ी सभी चोटियों की सूची देखी जाती है, तो हम इसे काले रंग में रंग देते हैं।

मुझे लगता है कि एक उदाहरण का उपयोग करके इस एल्गोरिथ्म पर विचार करना आसान होगा:





↑ हमारे पास एक नॉन-कॉन्टूर ओरिएंटेड ग्राफ है। प्रारंभ में, सभी कोने सफेद हैं, और स्टैक खाली है। चलिए शीर्ष नंबर 1 से गहराई से चलना शुरू करते हैं।



↑ हम शीर्ष नंबर पर जाते हैं 1. हम इसे ग्रे रंग में रंगते हैं।



Tex शीर्ष क्रमांक 1 से शीर्ष क्रम संख्या 4 तक एक धार है। शीर्ष क्रमांक 4 पर जाएं और इसे ग्रे रंग दें।



Tex शीर्ष क्रमांक 4 से शिखर संख्या 2 तक एक धार है। शीर्ष क्रमांक 2 पर जाएं और इसे ग्रे रंग दें।



Not शीर्ष क्रमांक 2 से ऐसे कोई किनारे नहीं हैं जो काले रंग के कोने तक नहीं जाते हैं। वापस वर्टेक्स नंबर पर जाएं। ब्लैक में वर्टेक्स नंबर 2 पेंट करें और इसे स्टैक पर रखें।



Tex शीर्ष क्रमांक 4 से शीर्ष क्रम संख्या 3 तक एक धार है। शीर्ष 3 पर जाएं और इसे ग्रे रंग दें।



↑ शीर्ष क्रमांक 3 से ऐसे कोई किनारे नहीं हैं जो काली चोटियों पर नहीं जाते हैं। वापस वर्टेक्स नंबर पर जाएं 4. वर्टेक्स नंबर 3 को काले रंग से पेंट करें और इसे स्टैक पर रखें।



↑ शीर्ष क्रमांक 4 से ऐसे कोई किनारे नहीं हैं जो काली चोटियों पर नहीं जाते हैं। वापस वर्टेक्स नंबर पर जाएं। ब्लैक में वर्टेक्स नंबर 4 पेंट करें और इसे स्टैक पर रखें।



Do शीर्ष क्रमांक 1 से ऐसे कोई किनारे नहीं हैं जो काले कोने तक नहीं जाते हैं। हम इसे काले रंग से पेंट करते हैं और इसे ढेर पर रख देते हैं। बिंदुओं का ट्रावेल पूरा हो गया है।



The बदले में, हम स्टैक से सभी कोने प्राप्त करते हैं और उन्हें क्रमशः 1, 2, 3, 4 नंबर आवंटित करते हैं। टोपोलॉजिकल सॉर्टिंग एल्गोरिथ्म पूरा हो गया है। गिनती छांटी जाती है।

आवेदन

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



कार्यान्वयन के लिए - यहां आप कोड की 22 लाइनें पा सकते हैं जो इस एल्गोरिदम को लागू करते हैं (सब कुछ सावधानीपूर्वक टिप्पणी की गई है)