रखे गए
रखे जाने के इंतज़ार में
जाँचे गए एज

  • मौजूदा
  • मुक्त या विज़िट हो रहे
  • रखे गए
  • साइकिल

टोपोलॉजिकल सॉर्ट के बारे में और

टोपोलॉजिकल सॉर्ट

जूतों से पहले मोज़े, दीवारों से पहले नींव, किसी कोर्स से पहले वह कोर्स जिसकी उसे ज़रूरत है। टोपोलॉजिकल सॉर्ट एकतरफ़ा एज वाले ग्राफ़ के नोड को एक पंक्ति में रखता है जिसमें हर एज आगे की ओर जाता है। काह्न एल्गोरिदम या DFS तरीका चुनें और चरण दर चरण क्रम को बढ़ते देखें, और फिर एक साइकिल जोड़कर देखें कि तब कोई क्रम क्यों संभव नहीं। क्रम को बढ़ते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। हर एज एकतरफ़ा है, जैसा उसका तीर दिखाता है: इसे “यह उससे पहले आता है” समझें। तरीका चुनें: काह्न एल्गोरिदम पहले उन नोड को रखता है जिनमें कोई आने वाला एज नहीं है, और हर नोड पर लिखी संख्या बताती है कि उसके कितने आने वाले एज अभी बाकी हैं; DFS तरीका हर नोड को तब सबसे आगे रखता है जब उसके बाद आने वाला सब कुछ रखा जा चुका हो। ग्राफ़ के नीचे की पंक्ति अब तक का क्रम है। हर तरीका साइकिल कैसे पकड़ता है, यह देखने के लिए “साइकिल जोड़ें” पर टिक करें। “नया ग्राफ़” दूसरा ग्राफ़ बनाता है; उसमें कितने नोड और एज हों, यह चुनें। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।

यह कैसे काम करता है

  1. काह्न एल्गोरिदम या DFS तरीका चुनें।
  2. “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
  3. ग्राफ़ के नीचे क्रम को बढ़ते देखें। हर तरीका साइकिल कैसे पकड़ता है, यह देखने के लिए “साइकिल जोड़ें” पर टिक करें।

काह्न एल्गोरिदम

हर नोड के लिए गिनें कि कितने एज उसकी ओर आते हैं। जिस नोड में कोई नहीं, वह किसी पर निर्भर नहीं, इसलिए वह पहले आ सकता है। ऐसा एक नोड रखें, और उसके जाने वाले एज हटा दें: जिन नोड की ओर वे जाते थे, उनमें अब एक आने वाला एज कम है, और कुछ शून्य पर पहुँचकर मुक्त हो सकते हैं। मुक्त नोड तब तक रखते रहें जब तक कोई न बचे। अगर कुछ नोड कभी मुक्त नहीं हुए, तो वे एक साइकिल में एक-दूसरे का इंतज़ार कर रहे हैं, और कोई टोपोलॉजिकल क्रम नहीं है।

DFS तरीका

हर बिना विज़िट किए नोड से डेप्थ-फ़र्स्ट सर्च चलाएँ। कोई नोड तब पूरा होता है जब उससे पहुँचने लायक सब कुछ पूरा हो चुका हो, इसलिए जो कुछ उसके बाद आना चाहिए वह पहले ही रखा जा चुका है। हर पूरे हुए नोड को क्रम में सबसे आगे रखें, और क्रम सही निकलता है। अगर सर्च किसी एज से ऐसे नोड तक जाए जिसके अंदर वह अभी है, तो वह एज साइकिल पूरी करता है, और फिर से कोई क्रम नहीं है।

अक्सर पूछे जाने वाले प्रश्न

टोपोलॉजिकल सॉर्ट क्या है?

डायरेक्टेड ग्राफ़ के नोड का ऐसा क्रम जिसमें हर एज पहले वाले नोड से बाद वाले नोड की ओर जाता है। अगर एज का मतलब “पहले आना ज़रूरी है” हो, तो यह वह क्रम है जिसमें सारे काम किए जा सकते हैं।

टोपोलॉजिकल क्रम कब मौजूद होता है?

ठीक तब जब ग्राफ़ में कोई डायरेक्टेड साइकिल न हो: यानी वह डायरेक्टेड एसाइक्लिक ग्राफ़, या DAG हो। साइकिल होने पर उस पर का हर नोड खुद से पहले आना चाहिए।

क्या टोपोलॉजिकल क्रम एक ही होता है?

आम तौर पर नहीं। जब भी दो नोड एज की किसी श्रृंखला से जुड़े न हों, तो कोई भी पहले आ सकता है, इसलिए एक ग्राफ़ के कई सही क्रम हो सकते हैं। काह्न एल्गोरिदम और DFS तरीका अक्सर अलग-अलग क्रम देते हैं।

टोपोलॉजिकल सॉर्ट कितना तेज़ है?

दोनों तरीके हर नोड और हर एज को तय बार ही देखते हैं, इसलिए काम नोड की संख्या और एज की संख्या के जोड़ के साथ बढ़ता है।

क्या मेरा ग्राफ़ कहीं भेजा जाता है?

नहीं। ग्राफ़ आपके ब्राउज़र में ही बनता और सॉर्ट होता है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ