एक प्रभावी प्रोग्रामर को डेटा संरचनाओं और एल्गोरिदम की ठोस समझ की आवश्यकता होती है। तकनीकी साक्षात्कार अक्सर आपकी समस्या-समाधान और महत्वपूर्ण सोच कौशल का परीक्षण करेंगे।
प्रोग्रामिंग में रेखांकन कई महत्वपूर्ण डेटा संरचनाओं में से एक है। ज्यादातर मामलों में, ग्राफ को समझना और ग्राफ-आधारित समस्याओं को हल करना आसान नहीं होता है।
ग्राफ क्या है और इसके बारे में आपको क्या जानने की जरूरत है?
एक ग्राफ क्या है?
ग्राफ़ एक गैर-रेखीय डेटा संरचना है जिसमें किनारों के साथ नोड्स (या कोने) होते हैं जो उन्हें जोड़ते हैं। सभी पेड़ ग्राफ़ के उपप्रकार हैं, लेकिन सभी ग्राफ़ पेड़ नहीं हैं, और ग्राफ़ डेटा संरचना है जिससे पेड़ों की उत्पत्ति हुई है।
हालांकि आप कर सकते हैं जावास्क्रिप्ट में डेटा संरचनाओं का निर्माण और अन्य भाषाओं में, आप एक ग्राफ को विभिन्न तरीकों से लागू कर सकते हैं। सबसे लोकप्रिय दृष्टिकोण हैं किनारे की सूचियाँ, आसन्न सूचियाँ, तथा आसन्न मैट्रिसेस.
रेखांकन का प्रतिनिधित्व करने के लिए खान अकादमी गाइड ग्राफ़ को निरूपित करने के तरीके के बारे में सीखने के लिए एक बेहतरीन संसाधन है।
कई अलग-अलग प्रकार के ग्राफ हैं। एक सामान्य अंतर के बीच है
निर्देशित तथा अनिर्दिष्ट रेखांकन; ये कोडिंग चुनौतियों और वास्तविक जीवन के उपयोगों में बहुत कुछ सामने आते हैं।रेखांकन के प्रकार
- निर्देशित ग्राफ: एक ग्राफ जिसमें सभी किनारों की एक दिशा होती है, जिसे भी कहा जाता है डिग्राफ
- अप्रत्यक्ष ग्राफ: एक अप्रत्यक्ष ग्राफ को दो-तरफा ग्राफ के रूप में भी जाना जाता है। अप्रत्यक्ष रेखांकन में, किनारों की दिशा मायने नहीं रखती है, और ट्रैवर्सल किसी भी दिशा में जा सकता है।
- भारित ग्राफ: भारित ग्राफ़ एक ऐसा ग्राफ़ होता है जिसके नोड्स और किनारों का एक संबद्ध मान होता है। ज्यादातर मामलों में, यह मान उस नोड या किनारे की खोज की लागत का प्रतिनिधित्व करता है।
- परिमित ग्राफ: एक ग्राफ जिसमें नोड्स और किनारों की एक सीमित संख्या होती है।
- अनंत ग्राफ: एक ग्राफ जिसमें अनंत मात्रा में नोड्स और किनारे होते हैं।
- तुच्छ ग्राफ: एक ग्राफ जिसमें सिर्फ एक नोड होता है और कोई किनारा नहीं होता है।
- सरल ग्राफ: जब केवल एक किनारा एक ग्राफ के नोड्स के प्रत्येक जोड़े को जोड़ता है, तो इसे एक साधारण ग्राफ कहा जाता है।
- शून्य ग्राफ: एक अशक्त ग्राफ एक ऐसा ग्राफ होता है जिसमें इसके नोड्स को जोड़ने वाला कोई किनारा नहीं होता है।
- मल्टीग्राफ: एक मल्टीग्राफ में, कम से कम एक जोड़ी नोड्स में एक से अधिक किनारे होते हैं जो उन्हें जोड़ते हैं। मल्टीग्राफ में, सेल्फ-लूप नहीं होते हैं।
- पूरा ग्राफ: एक पूर्ण ग्राफ एक ग्राफ है जिसमें प्रत्येक नोड ग्राफ में हर दूसरे नोड से जुड़ता है। इसे के रूप में भी जाना जाता है पूरा ग्राफ.
- छद्म ग्राफ: एक ग्राफ़ जिसमें अन्य ग्राफ़ किनारों से अलग एक स्व-लूप होता है, एक छद्म ग्राफ़ कहलाता है।
- नियमित ग्राफ: एक नियमित ग्राफ एक ऐसा ग्राफ होता है जहां सभी नोड्स की डिग्री समान होती है; यानी हर नोड में पड़ोसियों की संख्या समान होती है।
- जुड़ा हुआ ग्राफ: एक कनेक्टेड ग्राफ़ बस कोई भी ग्राफ़ होता है जिसमें कोई भी दो नोड जुड़ते हैं; यानी ग्राफ के प्रत्येक दो नोड्स के बीच कम से कम एक पथ वाला ग्राफ।
- डिस्कनेक्ट किया गया ग्राफ: डिस्कनेक्ट किया गया ग्राफ़ कनेक्टेड ग्राफ़ का सीधा विपरीत होता है। डिस्कनेक्ट किए गए ग्राफ़ में, ग्राफ़ के नोड्स को जोड़ने वाला कोई किनारा नहीं होता है, जैसे कि a शून्य ग्राफ।
- चक्रीय ग्राफ: एक चक्रीय ग्राफ एक ग्राफ होता है जिसमें कम से कम एक ग्राफ चक्र होता है (एक पथ जो समाप्त होता है जहां यह शुरू हुआ)।
- चक्रीय ग्राफ: एक चक्रीय ग्राफ एक ऐसा ग्राफ होता है जिसमें कोई चक्र नहीं होता है। इसे या तो निर्देशित या अप्रत्यक्ष किया जा सकता है।
- सबग्राफ: एक सबग्राफ एक व्युत्पन्न ग्राफ है। यह नोड्स और किनारों से बना एक ग्राफ है जो दूसरे ग्राफ के सबसेट हैं।
ए फंदा ग्राफ में एक किनारा होता है जो एक नोड से शुरू होता है और उसी नोड पर समाप्त होता है। इसलिए, ए आत्म पाश केवल एक ग्राफ नोड पर एक लूप है, जैसा कि एक छद्म ग्राफ में देखा गया है।
ग्राफ ट्रैवर्सल एल्गोरिदम
एक प्रकार की गैर-रेखीय डेटा संरचना होने के कारण, ग्राफ़ को ट्रेस करना काफी मुश्किल है। एक ग्राफ को पार करने का मतलब है कि किनारों के माध्यम से एक वैध पथ दिए गए प्रत्येक नोड से गुजरना और उसकी खोज करना। ग्राफ ट्रैवर्सल एल्गोरिदम मुख्य रूप से दो प्रकार के होते हैं।
- चौड़ाई-प्रथम खोज (बीएफएस): चौड़ाई-पहली खोज एक ग्राफ़ ट्रैवर्सल एल्गोरिथम है जो ग्राफ़ नोड पर जाता है और अपने किसी भी चाइल्ड नोड पर जाने से पहले अपने पड़ोसियों की खोज करता है। यद्यपि आप किसी भी चयनित नोड से ग्राफ़ को ट्रेस करना प्रारंभ कर सकते हैं, रूट नोड आमतौर पर पसंदीदा शुरुआती बिंदु है।
- गहराई-पहली खोज (डीएफएस): यह दूसरा प्रमुख ग्राफ ट्रैवर्सल एल्गोरिथम है। यह एक ग्राफ़ नोड पर जाता है और अगले नोड पर जाने से पहले अपने चाइल्ड नोड्स या शाखाओं की पड़ताल करता है - यानी, विस्तृत होने से पहले पहले गहराई में जाना।
जितनी जल्दी हो सके दो नोड्स के बीच पथ खोजने के लिए चौड़ाई-पहली खोज अनुशंसित एल्गोरिदम है, विशेष रूप से सबसे छोटा पथ।
जब आप ग्राफ़ के प्रत्येक नोड पर जाना चाहते हैं, तो गहराई-पहली खोज की अधिकतर अनुशंसा की जाती है। दोनों ट्रैवर्सल एल्गोरिदम किसी भी मामले में ठीक काम करते हैं, लेकिन चयनित परिदृश्यों में एक सरल और दूसरे की तुलना में अधिक अनुकूलित हो सकता है।
एक सरल उदाहरण दोनों एल्गोरिदम को बेहतर ढंग से समझने में मदद कर सकता है। एक देश के राज्यों को एक ग्राफ के रूप में सोचें और यह जाँचने का प्रयास करें कि क्या दो राज्य, एक्स तथा यू, जुड़े हुए हैं। एक गहन-पहली खोज लगभग देश भर में एक पथ पर जा सकती है बिना यह जाने कि यू से सिर्फ 2 राज्य दूर है एक्स.
चौड़ाई-पहली खोज का लाभ यह है कि यह अगले नोड पर जाने से पहले जितना संभव हो सके वर्तमान नोड से निकटता बनाए रखता है। यह के बीच संबंध ढूंढेगा एक्स तथा यू थोड़े समय में पूरे देश का पता लगाए बिना।
इन दो एल्गोरिदम के बीच एक और बड़ा अंतर यह है कि उन्हें कोड में कैसे लागू किया जाता है। चौड़ाई-पहली खोज है a पुनरावृत्त एल्गोरिथ्म और a. का उपयोग करता है कतार, जबकि गहराई-पहली खोज को आमतौर पर a. के रूप में लागू किया जाता है पुनरावर्ती एल्गोरिदम जो इसका लाभ उठाता है ढेर.
नीचे कुछ छद्म कोड है जो दोनों एल्गोरिदम के कार्यान्वयन को प्रदर्शित करता है।
पहले चौड़ाई खोजो
बीएफएस (ग्राफ जी, ग्राफनोड रूट) {
होने देना क्यू बी नया कतार// रूट को विज़िट के रूप में चिह्नित करें
रूट.विजिटेड = सच// कतार में रूट जोड़ें
क्यू.एनक्यूई(जड़)
जबकि (क्यू नहीं है खाली) {
होने देना वर्तमान q.dequeue हो () // कतार में सामने वाले तत्व को हटा दें
के लिए (पड़ोसी जी में वर्तमान के एन) {
यदि (एन हैनहीं अभी तक दौरा किया) {
// कतार में जोड़ें - ताकि आप इसके पड़ोसियों का भी पता लगा सकें
क्यू.एनक्यूई(एन)
n. का दौरा किया = सच
}
}
}
}
गहराई-पहली खोज
डीएफएस (ग्राफ जी, ग्राफनोड रूट) {
// मुख्य मामला
यदि (रूट is शून्य) वापसी// रूट को विज़िट के रूप में चिह्नित करें
रूट.विजिटेड = सच
के लिए (पड़ोसी n की जड़ में G)
यदि (एन हैनहीं अभी तक दौरा किया)
डीएफएस (जी, एन) // पुनरावर्ती कॉल
}
कुछ अन्य ग्राफ-ट्रैवर्सल एल्गोरिदम चौड़ाई-प्रथम और गहराई-प्रथम खोजों से प्राप्त होते हैं। सबसे लोकप्रिय हैं:
- द्विदिश खोज: यह एल्गोरिथ्म दो नोड्स के बीच सबसे छोटा रास्ता खोजने का एक अनुकूलित तरीका है। यह दो चौड़ाई-पहली खोजों का उपयोग करता है जो पथ होने पर टकराते हैं।
- टोपोलॉजिकल सॉर्ट: इसका उपयोग में किया जाता है निर्देशित रेखांकन वांछित क्रम में नोड्स को सॉर्ट करने के लिए। आप अप्रत्यक्ष ग्राफ़ या चक्र वाले ग्राफ़ पर टोपोलॉजिकल सॉर्ट लागू नहीं कर सकते।
- दिज्क्स्ट्रा का एल्गोरिथ्म: यह भी एक प्रकार का BFS है। इसका उपयोग a. में दो नोड्स के बीच सबसे छोटा रास्ता खोजने के लिए भी किया जाता है भारित निर्देशित ग्राफ, जिसमें चक्र हो सकते हैं या नहीं।
ग्राफ़ पर आधारित सामान्य साक्षात्कार प्रश्न
रेखांकन महत्वपूर्ण में से हैं डेटा संरचनाएं हर प्रोग्रामर को पता होनी चाहिए. तकनीकी साक्षात्कार में अक्सर इस विषय पर प्रश्न आते हैं, और आप विषय से संबंधित कुछ क्लासिक समस्याओं का सामना कर सकते हैं। इनमें "टाउन जज", "आइलैंड्स की संख्या", और "ट्रैवलिंग सेल्समैन" समस्याएं शामिल हैं।
ये कई लोकप्रिय ग्राफ-आधारित साक्षात्कार समस्याओं में से कुछ हैं। आप इन्हें आजमा सकते हैं लेटकोड, हैकररैंक, या गीक्सफ़ोरगीक्स.
ग्राफ डेटा संरचनाओं और एल्गोरिदम को समझना
ग्राफ़ केवल तकनीकी साक्षात्कार के लिए उपयोगी नहीं हैं। उनके पास वास्तविक दुनिया के उपयोग के मामले भी हैं, जैसे कि in नेटवर्किंग, मानचित्र, तथा एयरलाइन सिस्टम मार्ग खोजने के लिए। इनका उपयोग कंप्यूटर सिस्टम के अंतर्निहित तर्क में भी किया जाता है।
डेटा को व्यवस्थित करने और जटिल समस्याओं की कल्पना करने में हमारी मदद करने के लिए ग्राफ़ उत्कृष्ट हैं। ग्राफ़ का उपयोग केवल तभी किया जाना चाहिए जब अंतरिक्ष जटिलता या स्मृति समस्याओं को रोकने के लिए बिल्कुल आवश्यक हो।
