कोसाराजू का एल्गोरिदम: मजबूती से जुड़े घटकों के लिए गाइड

TL;DR: कोसाराजू का एल्गोरिदम एक निर्देशित में मजबूती से जुड़े घटकों को ढूंढता है दो गहराई-प्रथम-खोज पासों का उपयोग करके ग्राफ़। पहले समाप्ति समय को कम करके शीर्षों को रिकॉर्ड करें, प्रत्येक किनारे को स्थानांतरित करें, फिर उसी क्रम में स्थानांतरित ग्राफ़ का पता लगाएं। रनटाइम O(V + E) है और ट्रांसपोज़ संग्रहीत होने पर सहायक भंडारण O(V + E) है।

कोसाराजू का एल्गोरिदम क्या है?

कोसाराजू का एल्गोरिदम एक निर्देशित ग्राफ को दृढ़ता से जुड़े घटकों या एससीसी में विभाजित करता है। एक एससीसी के अंदर, प्रत्येक शीर्ष हर दूसरे शीर्ष तक पहुंच सकता है। प्रत्येक एससीसी को एक नोड में अनुबंधित करने से एक निर्देशित एसाइक्लिक ग्राफ उत्पन्न होता है, जो घटकों को निर्भरता विश्लेषण, प्रोग्राम ग्राफ, रीचैबिलिटी और ग्राफ संक्षेपण के लिए उपयोगी बनाता है।

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

टू-पास एल्गोरिदम कैसे काम करता है?

1. एक विज़िट किया गया सेट और एक खाली फिनिश-ऑर्डर सूची बनाएं।
2. मूल ग्राफ़ में प्रत्येक न देखे गए शीर्ष से गहराई-पहली खोज चलाएँ।
3. प्रत्येक शीर्ष को उसके सभी निवर्तमान पड़ोसियों के समाप्त होने के बाद जोड़ें।
4. प्रत्येक निर्देशित किनारे को उलट कर स्थानान्तरण का निर्माण करें।
5. विज़िट किया गया सेट साफ़ करें.
6. शीर्षों को विपरीत समाप्ति क्रम में संसाधित करें।
7. ट्रांसपोज़्ड ग्राफ़ में प्रत्येक डीएफएस पेड़ एक मजबूती से जुड़ा हुआ घटक है।

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

फिनिश ऑर्डर को उलटने से SCCs क्यों मिलते हैं?

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

उस घटक को हटाने से अगले असाइन न किए गए घटक के लिए वही तर्क सामने आता है। यह वह प्रमाण विचार है जो साक्षात्कारकर्ता आमतौर पर चाहते हैं: फिनिश ऑर्डर सुरक्षित रूप से घटकों का चयन करता है, और ट्रांसपोज़िशन दूसरे पास को गलत आउटगोइंग सीमा को पार करने से रोकता है। आपको एक लंबे औपचारिक प्रमाण को पुन: प्रस्तुत करने की आवश्यकता नहीं है, लेकिन आपको दोनों भूमिकाओं की व्याख्या करनी चाहिए।

समय और स्थान की जटिलताएँ क्या हैं?

प्रत्येक गहराई-प्रथम-खोज पास प्रत्येक शीर्ष पर जाता है और प्रत्येक किनारे की एक बार जांच करता है, और स्थानान्तरण का निर्माण करने में भी रैखिक समय लगता है। इसलिए कुल समय O(V + E) है। ग्राफ़ और ट्रांसपोज़ दोनों के लिए आसन्न सूचियों के साथ, भंडारण ओ (वी + ई) है, साथ ही विज़िट की गई स्थिति, फिनिश ऑर्डर और रिकर्सन या एक स्पष्ट स्टैक के लिए ओ (वी) है।

बहुत गहरे ग्राफ़ के लिए, पुनरावर्ती डीएफएस किसी भाषा की कॉल-स्टैक सीमा को पार कर सकता है। पुनरावृत्त स्टैक का उल्लेख करना स्पर्शोन्मुख सीमा को बदले बिना उत्पादन जागरूकता को दर्शाता है।

साक्षात्कार के लिए आपको कौन सा छद्म कोड जानना चाहिए?

फिनिश_ऑर्डर = []
विज़िट किया गया = सेट()

ग्राफ़ में शीर्ष के लिए:
    यदि शीर्ष विज़िट में नहीं है:
        dfs_finish(वर्टेक्स, ग्राफ़, विज़िट, फिनिश_ऑर्डर)

ट्रांसपोज़ = रिवर्स_ऑल_एज (ग्राफ़)
विज़िट किया गया.स्पष्ट()
घटक = []

विपरीत दिशा में शीर्ष के लिए (finish_order):
    यदि शीर्ष विज़िट में नहीं है:
        घटक = []
        dfs_collect(वर्टेक्स, ट्रांसपोज़, विज़िट, घटक)
        घटक.जोड़ें(घटक)

dfs_finish में, पड़ोसियों से मिलने के बाद शीर्ष जोड़ें। dfs_collect में, खोजे जाने पर शीर्ष जोड़ें। उन दोनों जिम्मेदारियों को अलग रखें; पहले पास में प्रीऑर्डर का उपयोग करना एक सामान्य त्रुटि है।

कौन सी गलतियाँ आमतौर पर कोसाराजू कार्यान्वयन को बाधित करती हैं?

सबसे आम गलतियाँ फिनिश ऑर्डर के बजाय डिस्कवरी ऑर्डर को रिकॉर्ड करना, दूसरे पास के लिए ऑर्डर को उलटना भूल जाना, केवल कुछ किनारों को उलटना, विज़िट की गई स्थिति को साफ़ किए बिना पुन: उपयोग करना, और अलग या डिस्कनेक्ट किए गए कोने को छोड़ देना है। एक और गलती एक अप्रत्यक्ष ग्राफ़ को ऐसे मानना ​​है जैसे कि एससीसी उसी तरह से सार्थक थे; जुड़े हुए घटक वहां सरल अवधारणा हैं।

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

कोसाराजू की तुलना टार्जन के एल्गोरिदम से कैसे की जाती है?

दोनों एल्गोरिदम O(V + E) में SCCs ढूंढते हैं। कोसाराजू दो डीएफएस पास का उपयोग करता है और आमतौर पर एक ट्रांसपोज़्ड ग्राफ़ संग्रहीत करता है, जो तर्क और कार्यान्वयन को सरल बना सकता है। टार्जन डिस्कवरी इंडेक्स, लो-लिंक वैल्यू और स्टैक के साथ एक डीएफएस का उपयोग करता है; यह स्पष्ट स्थानान्तरण से बचता है लेकिन सही ढंग से बनाए रखने के लिए इसमें अधिक स्थिति होती है।

एक साक्षात्कार में, वह एल्गोरिदम चुनें जिसे आप विश्वसनीय रूप से समझा और कार्यान्वित कर सकते हैं जब तक कि बाधाएं किसी के पक्ष में न हों। यदि साक्षात्कारकर्ता एक पास या कोई ट्रांसपोज़ नहीं मांगता है, तो टार्जन बेहतर फिट हो सकता है। यदि स्पष्टता और प्रत्यक्ष प्रमाण प्राथमिकताएं हैं, तो कोसाराजू अक्सर एक उत्कृष्ट विकल्प होता है।

AI ग्राफ़-एल्गोरिदम अभ्यास को जिम्मेदारी से कैसे समर्थन कर सकता है?

AI छोटे प्रतिउदाहरण उत्पन्न कर सकता है, DFS स्थिति का पता लगा सकता है, कार्यान्वयन की तुलना कर सकता है और एक जटिलता स्पष्टीकरण को चुनौती दे सकता है। कोडिंग सहायता ऑर्डर या विज़िट-स्टेट बग का पता लगाने में मदद कर सकती है, जबकि ट्रांसक्रिप्ट समीक्षा यह दिखा सकती है कि आपने प्रमाण विचार को स्पष्ट रूप से समझाया है या नहीं।

हमेशा कम से कम एक ग्राफ स्वयं बनाएं और ट्रेस करें, परीक्षण चलाएं और उत्पन्न दावों को सत्यापित करें। मूल्यांकन नियमों का पालन करें और निषिद्ध सहायता का उपयोग न करें। YesToTheOffer कोडिंग तैयारी, अनुमत वास्तविक समय तर्क, निजी नोट्स और साक्षात्कार के बाद की समीक्षा का समर्थन करता है।

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

अभ्यास को दोहराने योग्य प्रणाली में बदलें

एक साक्ष्य-आधारित अभ्यास योजना बनाएं, जहां अनुमति हो वहां जिम्मेदार समर्थन का उपयोग करें, और बातचीत ताजा होने पर उसकी समीक्षा करें।