उन्नत डेटा संरचनाएँ। भाग एक: दिशात्मक एसाइक्लिक ग्राफ

सभी को नमस्कार! अगले सप्ताह, डेवलपर्स कोर्स के लिए एल्गोरिदम के नए समूह में कक्षाएं शुरू हो जाएंगी। इस संबंध में, हम आपके साथ एक बहुत छोटी, बल्कि दिलचस्प सामग्री का अनुवाद साझा कर रहे हैं।

---

मैं डेटा संरचना के साथ लेखों की इस श्रृंखला को शुरू करना चाहता था जिसे हम सभी डेवलपर्स से परिचित हैं, लेकिन यह संभव है कि हम यह भी नहीं जानते कि यह कैसे काम करता है।

“दिशात्मक चक्रीय ग्राफ? यह कभी नहीं सुना। ऐसा मत सोचो कि तुम मेरे बारे में सब कुछ जानते हो! ”, आप कह सकते हैं, लेकिन यह ऐसा ग्राफ है जो संस्करण नियंत्रण को संभव बनाता है। हाँ, गिट एक चक्रीय ग्राफ है। इस लेख में, मैं आपके साथ डायरेक्टेड एसाइक्लिक ग्राफ्स (डीएजी) के ज्ञान को साझा करूंगा, और फिर आपको दिखाऊंगा कि कैसे लिखना है।

DAG क्या है?

तो इसका क्या मतलब है? DAG एक यूनिडायरेक्शनल ग्राफ है जहाँ किसी भी तत्व को बच्चा नहीं माना जा सकता है। हम में से कई लोग लिंक्ड लिस्ट, ट्री और ग्राफ से परिचित हैं। DAG तीसरे के कार्यान्वयन में पहले और दूसरे के समान है।


यह एक पेड़ की तरह दिखता है, लेकिन काफी नहीं

अपने सबसे न्यूनतम रूप में, DAG के 4 घटक हैं:

1. नोड्स। वे डेटा स्टोर करते हैं।
2. दिशात्मक किनारा : तीर जो एक दिशा में इंगित करता है (जो इस डेटा संरचना को अन्य के विपरीत बनाता है)।
3. माता-पिता के बिना एक "महान" पूर्वज नोड । (मजेदार तथ्य: ज्यादातर पूर्वज पेड़ वास्तव में चक्रीय रेखांकन निर्देशित होते हैं, पेड़ नहीं, क्योंकि कभी-कभी "चचेरे भाई दूसरे से शादी करते हैं)"
4. पत्तियां। या बिना बच्चे के नोड्स।

आइए हमारा निर्देशित एसाइक्लिक ग्राफ लिखें

अब कोड लिखते हैं। सबसे पहले, दो गुणों के साथ एक निर्माता बनाएं और इसे डीएजी कहें।

function DAG() { this.nodes = []; this.vertices = {}; } 

नोड्स जोड़ने के लिए एक विधि बनाएं। देखिये मैंने यहाँ क्या किया?

 DAG.prototype.add = function(node) { if (!node) { return; } if (this.vertices[node]) { return this.vertices[node]; } const vertex = { node: node, incoming: {}, incomingNodes: [], hasOutgoing: false, value: null }; this.vertices[node] = vertex; this.nodes.push(node); return vertex; }; 

यह कैसे काम करता है? vertex ऑब्जेक्ट वह जगह है जहां सभी जादू होता है। हम एक नोड जोड़ते हैं, आने वाली नोड्स के साथ एक ऑब्जेक्ट, और उनके सभी नामों के साथ एक सरणी, प्रकार बूलियन का एक चर जो संकेत देता है कि नोड कुछ या नहीं और इसके मूल्य को इंगित करता है। हम बाद में इस पर आगे बढ़ेंगे।

अब कुछ किनारों को जोड़ते हैं और नोड्स को एक साथ जोड़ते हैं। इससे पहले कि हम ऐसा कर सकें, हमें एक सहायक फ़ंक्शन बनाना होगा जो यह जाँच करे कि हमने इस नोड का दौरा किया है या नहीं। चलो उसकी visit बुलाओ।

 function visit(vertex, fn, visited, path) { const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) { visited = {}; } if (!path) { path = []; } if (visited.hasOwnProperty(name)) { return; } path.push(name); visited[name] = true; for (i = 0; i < len; i++) { visit(vertices[names[i]], fn, visited, path); } fn(vertex, path); path.pop(); } 

निम्नलिखित होता है:

 DAG.prototype.addEdge = function(fromName, toName) { if (!fromName || !toName || fromName === toName) { return; } const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) { return; } function checkCycle(vertex, path) { if (vertex.name === toName) { throw new Error(“Theres a cycle foo!!!!!“)); } } visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); }; 

यह श्रद्धांजलि देने का समय है

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

पढ़ने के लिए धन्यवाद!