रूबी के साथ व्यावहारिक ग्राफ थ्योरी में महारत

यह "व्यावहारिक कंप्यूटर विज्ञान" श्रृंखला में अगली किस्त है, जहां आप सीखेंगे कि क्लासिक कंप्यूटर विज्ञान अवधारणाओं को रूबी का उपयोग करके वास्तविक समस्याओं को हल करने के लिए कैसे लागू किया जाए।

आज हम ग्राफ थ्योरी के बारे में बात करने जा रहे हैं।

आपने बाइनरी ट्री के बारे में सुना होगा, वे ऐसे दिखते हैं:

बात यह है कि एक बाइनरी ट्री ग्राफ का सिर्फ एक विशेष संस्करण है, इसलिए इससे आपको अंदाजा होना चाहिए कि ग्राफ कितने व्यापक हैं।

आइए ग्राफ थ्योरी के बुनियादी सिद्धांतों के अवलोकन से शुरू करें, फिर हम कुछ व्यावहारिक उपयोग देखेंगे और रूबी में इसे कैसे लागू करें!

ग्राफ बुनियादी सिद्धांत

एक ग्राफ दो तत्वों से बना होता है:

• नोड्स (या वर्टेक्स)
• एजेस

एक नोड ग्राफ में एक तत्व का प्रतिनिधित्व करता है, जैसे एक मानचित्र का प्रतिनिधित्व करने वाले ग्राफ में एक शहर या एक सड़क। जबकि एजेस नोड्स के बीच कनेक्शन का प्रतिनिधित्व करते हैं।

यदि आप कंप्यूटर विज्ञान या गणित की किताब देखते हैं तो आप एक ग्राफ को इस सूत्र द्वारा परिभाषित देखेंगे: G(V, E)।

जहां G का अर्थ ग्राफ है, V वर्टेक्स का समुच्चय है और E एजेस का समुच्चय है।

ग्राफ डायरेक्टेड या अनडायरेक्टेड हो सकते हैं। इसका अर्थ है कि आप केवल एक दिशा में जा सकते हैं (डायरेक्टेड ग्राफ) या दोनों दिशाओं में (अनडायरेक्टेड ग्राफ)।

सबसे लोकप्रिय प्रकार का ग्राफ डायरेक्टेड एसाइक्लिक ग्राफ (DAG) है। एसाइक्लिक का अर्थ है कि कोई लूप नहीं हैं, बैकट्रैक करने का कोई तरीका नहीं है।

ग्राफ के उपयोग

अब जब हमने बुनियादी सिद्धांतों का अवलोकन देखा है, तो आइए ग्राफ के कुछ सामान्य उपयोग देखें।

ग्राफ का उपयोग करके आप चीजें कर सकते हैं जैसे:

• दो स्थानों के बीच सबसे छोटा (या सबसे लंबा) रास्ता खोजें
• जांचें कि दो चीजें एक-दूसरे से संबंधित हैं या नहीं
• एक अनुशंसा इंजन बनाएं
• निर्भरताओं का विश्लेषण करें

एक अन्य उदाहरण में गंतव्य के लिए सर्वोत्तम मार्ग ढूंढना शामिल है (GPS डिवाइस सोचें)।

ग्राफ को कैसे लागू और उपयोग करें

आप अपना खुद का ग्राफ कार्यान्वयन लिख सकते हैं, लेकिन इस लेख के लिए हम RGL जेम पर टिके रहेंगे जो पहले से ही हमारे लिए एक लागू करता है।

RGL का उपयोग करके एक बुनियादी ग्राफ बनाने के लिए:

 require 'rgl/adjacency' graph = RGL::DirectedAdjacencyGraph.new graph.add_edge 1,2 graph.add_edge 3,4 graph.add_edge 1,4 graph.add_edge 4,3 

यह कोड निम्नलिखित ग्राफ उत्पन्न करता है:

आप अपने ग्राफ का ग्राफिकल प्रतिनिधित्व इस तरह प्राप्त कर सकते हैं:

 require 'rgl/dot' graph.print_dotted_on 

फिर उस मेथड के आउटपुट को एक साइट पर कॉपी करें जो डॉट भाषा को प्रोसेस कर सकती है। जैसे यह वाला।

वैकल्पिक रूप से, आप छवि को स्थानीय रूप से उत्पन्न करने के लिए अपने मशीन पर Graphviz इंस्टॉल कर सकते हैं।

अब जब हमारे पास एक ग्राफ है, तो हम इसके बारे में जानकारी प्राप्त करने के लिए इसे पार करना चाह सकते हैं।

आपके ग्राफ को खोजने के लिए दो बुनियादी एल्गोरिदम हैं:

• ब्रेडथ-फर्स्ट सर्च (BFS)
• डेप्थ-फर्स्ट सर्च (DFS)

BFS में आपको पहले निकटतम नोड्स मिलते हैं और DFS में आप हर नोड के लिए जितना संभव हो उतना गहरा जाते हैं। इन एल्गोरिदम को स्टैक डेटा संरचना का उपयोग करके लागू किया जा सकता है।

RGL जेम पहले से ही उन एल्गोरिदम को आपके लिए लागू करता है:

 require 'rgl/traversal' graph.bfs_iterator.to_a # [1, 2, 4, 3] graph.dfs_iterator.to_a # [1, 4, 3, 2] 

ग्राफ को फिर से देखें और इन एल्गोरिदम द्वारा किए गए पथ का अपनी आंखों से पालन करें (या यदि आप चाहें तो उंगली का भी उपयोग कर सकते हैं)। इससे आपको यह समझने में मदद मिलेगी कि क्या हो रहा है।

वेटेड ग्राफ्स

हम वेट्स के रूप में ग्राफ में अधिक जानकारी जोड़ सकते हैं ताकि यह अधिक उपयोगी हो सके।

वेट्स एजेस को दिए जाते हैं, जो दो नोड्स के बीच के पथ हैं (जिन्हें "वर्टेक्स" के रूप में भी जाना जाता है)। ये वेट्स एक बिंदु से दूसरे बिंदु पर जाने की लागत का प्रतिनिधित्व करते हैं।

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

या यदि हमारे पास एक कंप्यूटर नेटवर्क है, तो वेट्स यह दर्शा सकते हैं कि किसी निश्चित नेटवर्क तक पहुंचने में कितने हॉप्स लगते हैं।

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

वेटेड ग्राफ के लिए यहां एक कोड उदाहरण है:

 graph = RGL::DirectedAdjacencyGraph.new graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle" edge_weights = { ["New York", "Los Angeles"] => 2445, ["Los Angeles", "Chicago"] => 2015, ["Los Angeles", "Houston"] => 1547, ["Chicago", "Houston"] => 939, ["Seattle", "Los Angeles"] => 1548 } edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) } 

अब हम एक बिंदु से दूसरे बिंदु तक सबसे छोटा रास्ता खोज सकते हैं। और यह बिल्कुल अगले खंड का विषय है!

सबसे छोटा रास्ता ढूंढना

ग्राफ के अंदर सबसे छोटा रास्ता खोजने के लिए एक लोकप्रिय एल्गोरिदम "डिज्क्स्ट्रा का सबसे छोटा रास्ता" एल्गोरिदम है।

एक वेटेड ग्राफ दिया गया है, हम इस प्रश्न को हल करने के लिए डिज्क्स्ट्रा के एल्गोरिदम का उपयोग कर सकते हैं:

"बिंदु A से बिंदु B तक पहुंचने का सबसे तेज़ तरीका क्या है?"

यहां RGL जेम का उपयोग करके एक कोड उदाहरण है:

 p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston") # ["New York", "Los Angeles", "Houston"] 

यह हमें ग्राफ में उपलब्ध जानकारी का उपयोग करके न्यूयॉर्क से ह्यूस्टन तक का सबसे छोटा रास्ता बताता है।

सारांश

आपने सीखा कि ग्राफ डेटा संरचना क्या है और RGL जेम के साथ इसका उपयोग कैसे करें।

आपने ग्राफ के साथ काम करने के लिए सामान्य एल्गोरिदम के बारे में भी सीखा, जैसे DFS, BFS और डिज्क्स्ट्रा का।

यदि आपको यह उपयोगी लगा तो इस पोस्ट को शेयर करना न भूलें ताकि अधिक लोग इसका आनंद ले सकें 🙂