कोडिंग साक्षात्कार की तैयारी · पाठ

Kahn's Algorithm से Topological Sort

उन tasks को क्रम दें जो दूसरों पर निर्भर हैं

पाठ 1, कुल 4 में से13 चरण

Kahn's Algorithm से Topological Sort, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

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

एक टोपोलॉजिकल क्रम निर्देशित ग्राफ के प्रत्येक नोड को इस तरह सूचीबद्ध करता है कि हर एज पहले वाले नोड से बाद वाले नोड की ओर जाए। इसे उन कार्यों को उनकी आवश्यकता वाले कार्यों से पहले रखने जैसा समझिए।

केवल DAG मान्य हैं

यह केवल DAG, यानी निर्देशित अचक्रीय ग्राफ, पर काम करता है। यदि कोई चक्र मौजूद हो, तो ऐसा कोई मान्य क्रम नहीं हो सकता जो हर निर्भरता को संतुष्ट करे।

इनडिग्री का विचार

काह्न की कलनविधि इनडिग्री पर आधारित है: किसी नोड की ओर आने वाले एजों की संख्या। शून्य इनडिग्री वाले नोड की कोई अधूरी निर्भरता नहीं होती।

हर इनडिग्री गिनें

पहले चरण में सभी एजों पर जाएँ और गिनें कि प्रत्येक नोड कितनी बार गंतव्य बनता है। इससे हर नोड की इनडिग्री मिल जाती है।

indeg = [0] * n
for u in range(n):
    for v in adj[u]:
        indeg[v] += 1

तैयार कतार में शुरुआत के नोड डालें

शून्य इनडिग्री वाला हर नोड तुरंत तैयार है, इसलिए शुरुआत करने के लिए उन सभी को एक कतार में डालें।

from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)

एक नोड पर कार्य करें

तैयार नोड को pop करें और अपने क्रम में append करें। अब यह सुरक्षित है, क्योंकि कोई भी शेष नोड इस पर निर्भर नहीं है।

u = q.popleft()
order.append(u)

उसके पड़ोसियों को मुक्त करें

हर पड़ोसी की इनडिग्री एक घटाएँ। जब किसी पड़ोसी की इनडिग्री शून्य हो जाए, तो वह तैयार होकर कतार में शामिल हो जाता है।

for v in adj[u]:
    indeg[v] -= 1
    if indeg[v] == 0:
        q.append(v)

कतार खाली होने तक दोहराएँ

कतार खाली होने तक नोड को लगातार pop करके पड़ोसियों को मुक्त करते रहें। हर चरण में एक सुरक्षित नोड जुड़ता जाता है, जब तक सभी नोड रखे न जा चुके हों।

बिना अतिरिक्त लागत चक्र खोजें

यदि आपके अंतिम क्रम में n से कम नोड हैं, तो किसी चक्र ने बाकी नोडों को रोक रखा है। काह्न की कलनविधि बिना अतिरिक्त लागत के चक्र का पता लगा देती है।

if len(order) < n:
    print('cycle exists')

चलने का समय

हर नोड और एज को एक बार देखा जाता है, इसलिए काह्न की कलनविधि O(V + E) समय में चलती है। यह लाखों एज वाले ग्राफों के लिए भी उपयोगी है।

कई मान्य क्रम

जब एक साथ कई नोड तैयार हों, तो उनमें से कोई भी अगला चुना जा सकता है। इसलिए किसी DAG के अक्सर कई मान्य टोपोलॉजिकल क्रम होते हैं, केवल एक नहीं।

त्वरित जाँच

आप काह्न की कलनविधि पूरी करते हैं, लेकिन क्रम में n से कम नोड हैं। इसका क्या अर्थ है?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: काह्न की कलनविधि

इनडिग्री गिनें, शून्य इनडिग्री वाले नोडों को कतार में डालें, एक नोड को pop करें, पड़ोसियों की इनडिग्री घटाएँ और दोहराएँ। यही O(V+E) में किया गया साफ़ टोपोलॉजिकल क्रमण है। 🚀

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

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

क्या “Kahn's Algorithm से Topological Sort” पाठ निःशुल्क है?

हाँ—“Kahn's Algorithm से Topological Sort” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Kahn's Algorithm से Topological Sort” में मैं क्या सीखूँगा?

उन tasks को क्रम दें जो दूसरों पर निर्भर हैं आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।

“Kahn's Algorithm से Topological Sort” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ