ग्राफ़ (सार डेटा प्रकार): Difference between revisions

Latest revision as of 19:32, 21 July 2023

तीन शीर्ष (ग्राफ सिद्धांत) (नीले वृत्त) एवं तीन शीर्ष (ग्राफ सिद्धांत) (काले तीर) के साथ निर्देशित ग्राफ है।

कंप्यूटर विज्ञान में, ग्राफ अमूर्त डेटा प्रकार है जिसका उद्देश्य गणित के अंदर ग्राफ सिद्धांत के क्षेत्र से अप्रत्यक्ष ग्राफ एवं निर्देशित ग्राफ अवधारणाओं को प्रस्तावित करना है।

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

ग्राफ़ डेटा संरचना प्रत्येक शीर्ष से कुछ शीर्ष मान को जैसे कि प्रतीकात्मक लेबल या संख्यात्मक विशेषता (लागत, क्षमता, लंबाई, आदि) भी जोड़ सकती है।

संचालन

ग्राफ़ डेटा संरचना G द्वारा प्रदान किए गए बुनियादी संचालन में सामान्यतः सम्मिलित हैं:^[1]

adjacent(G, x, y): परीक्षण करता है कि शीर्ष x से शीर्ष y तक कोई किनारा है या नहीं;
neighbors(G, x): सभी शीर्षों y को इस प्रकार सूचीबद्ध करता है कि शीर्ष x से शीर्ष y तक किनारा हो;
add_vertex(G, x): शीर्ष x जोड़ता है, यदि वह वहां नहीं है;
remove_vertex(G, x): शीर्ष x को निकाल देता है, यदि वह वहां है;
add_edge(G, x, y, z): शीर्ष x से शीर्ष y तक किनारा z जोड़ता है, यदि यह वहां नहीं है;
remove_edge(G, x, y): शीर्ष को शीर्ष x से शीर्ष y तक निकाल देता है, यदि वह वहां है;
get_vertex_value(G, x): शीर्ष x से संबद्ध मान लौटाता है;
set_vertex_value(G, x, v): शीर्ष x से v तक संबद्ध मान निश्चित करता है।

संरचनाएं जो मूल्यों को किनारों से जोड़ती हैं, सामान्यतः यह भी प्रदान करती हैं:^[1]* get_edge_value(G, x, y): शीर्ष (x, y) से जुड़ा मान लौटाता है;

set_edge_value(G, x, y, v): शीर्ष (x, y) से जुड़े मान को v पर निश्चित करता है।

ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ

निकटवर्ती सूची^[2]: शीर्षों को रिकॉर्ड या ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, एवं प्रत्येक शीर्ष आसन्न शीर्षों की सूची संग्रहीत करता है। यह डेटा संरचना शीर्षों पर अतिरिक्त डेटा के भंडारण की अनुमति देती है। यदि किनारों को ऑब्जेक्ट के रूप में भी संग्रहीत किया जाता है, तो अतिरिक्त डेटा संग्रहीत किया जा सकता है, इस स्थिति में प्रत्येक शीर्ष अपने घटना किनारों को संग्रहीत करता है एवं प्रत्येक किनारा अपने घटना शीर्षों को संग्रहीत करता है।
सहखंडज आव्यूह^[3]: द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ स्रोत शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ गंतव्य शीर्षों का प्रतिनिधित्व करते हैं। किनारों एवं शीर्षों पर डेटा को बाहरी रूप से संग्रहीत किया जाना चाहिए। प्रत्येक जोड़ी शीर्षों के मध्य केवल शीर्ष की लागत संग्रहीत की जा सकती है।
घटना आव्यूह^[4]: द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ पंक्ति में शीर्ष एवं स्तंभ में शीर्ष के मध्य घटना संबंध को प्रदर्शित करती हैं।

निम्न तालिका |V| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय समष्टिता लागत देती है शीर्षों की संख्या एवं |ई| किनारों की संख्या आव्यूह अभ्यावेदन में, प्रविष्टियाँ शीर्ष का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे सम्मिलित नहीं हैं उनकी लागत ∞ मानी जाती है।

	निकटवर्ती सूची	संलग्नता आव्यूह	घटना आव्यूह
स्टोर ग्राफ़	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
शीर्ष जोड़ें	$O(1)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
किनारा जोड़ें	$O(1)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
शीर्ष हटाएँ	$O(\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
किनारा हटाएँ	$O(\|V\|)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
क्या शीर्ष x एवं y आसन्न हैं (यह मानते हुए कि उनकी भंडारण स्थिति ज्ञात है)?	$O(\|V\|)$	$O(1)$	$O(\|E\|)$
टिप्पणियां	शीर्षों एवं किनारों को हटाने में धीमी गति रखें, क्योंकि इसे सभी शीर्षों या किनारों को ढूंढने की आवश्यकता होती है	शीर्ष को जोड़ने या हटाने की गति धीमी है, क्योंकि मैट्रिक्स का आकार परिवर्तित/कॉपी करना आवश्यक है	शीर्षों एवं किनारों को जोड़ने या हटाने में धीमी गति से, क्योंकि मैट्रिक्स का आकार कॉपी करना आवश्यक है

सामान्यतः विरल ग्राफ के प्रतिनिधित्व के लिए आसन्नता सूचियों को प्राथमिकता दी जाती है, अपितु ग्राफ़ सघन होने पर आसन्नता आव्यूह को प्राथमिकता दी जाती है; अर्थात् किनारों की संख्या |E| वर्ग शीर्षों की संख्या |V|² के समीप है, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत देखने में सक्षम होना चाहिए।^[5]^[6]

समानान्तर निरूपण

ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों डेटा-संचालित गणना, असंरचित समस्याएं, व्यर्थ स्थानीयता एवं गणना अनुपात तक उच्च डेटा पहुंच का सामना करना पड़ता है।^[7]^[8] समानांतर आकृति के लिए उपयोग किया जाने वाला ग्राफ़ प्रतिनिधित्व उन चुनौतियों का सामना करने में महत्वपूर्ण भूमिका निभाता है। व्यर्थ उपाय से चयन किए गए प्रतिनिधित्व एल्गोरिदम की संचार लागत को अनावश्यक रूप से बढ़ा सकते हैं, जिससे इसकी स्केलेबिलिटी कम हो जाती है। निम्नलिखित में, भाग एवं वितरित मेमोरी आकृति पर विचार किया जाता है।

शेयर्ड मेमोरी

शेयर्ड मेमोरी प्रारूप के विषय में, समानांतर प्रसंस्करण के लिए उपयोग किए जाने वाले ग्राफ़ प्रतिनिधित्व अनुक्रमिक विषय के समान हैं,^[9] चूंकि ग्राफ़ प्रतिनिधित्व (उदाहरण के लिए आसन्न सूची) तक समानांतर पढ़ने-योग्य पहुंच शेयर्ड मेमोरी में कुशल है।

वितरित मेमोरी

वितरित मेमोरी प्रारूप में, सामान्य दृष्टिकोण ग्राफ के शीर्ष सेट $V$ के अंदर $p$ सेट को $V_{0},\dots ,V_{p-1}$ का ग्राफ़ विभाजन करना है। यहाँ, $p$ उपलब्ध प्रसंस्करण तत्वों (PE) की मात्रा है। शीर्ष सेट विभाजन को मिलान सूचकांक के साथ PE में, इसके अतिरिक्त संबंधित किनारों पर भी वितरित किया जाता है। प्रत्येक PE का स्वयं का सबग्राफ प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। संदेश पासिंग इंटरफ़ेस जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के अधिकारिक PE की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के समय, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।^[9]

ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य भागीदारी है^[10] किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है।

1डी विभाजन: प्रत्येक प्रोसेसर को $n/p$ शीर्ष एवं संगत आउटगोइंग शीर्ष मिलता है। इसे आसन्न आव्यूह के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर कार्य करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है, ${\mathcal {O}}(m)$ संदेश बफ़र आकार, क्योंकि प्रत्येक PE में संभावित रूप से हर दूसरे PE के लिए आउटगोइंग शीर्ष होते हैं।^[11]2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत $p=p_{r}\times p_{c}$ में संरेखित हैं, जहाँ $p_{r}$ एवं $p_{c}$ क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को $(n/p_{r})\times (n/p_{c})$ आयाम के आसन्न आव्यूह का सबआव्यूह मिलता है। इसे आव्यूह में बिसात प्रतिमान के रूप में देखा जा सकता है।^[11]इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल ही पंक्ति एवं स्तंभ में PE के लिए आउटगोइंग शीर्ष हो सकते हैं। यह प्रत्येक PE के लिए संचार भागीदारों की $p_{r}+p_{c}-1$ से बाहर $p=p_{r}\times p_{c}$ संभव वाले संख्या को सीमित करता है।

संकुचित अभ्यावेदन

यंत्र अधिगम, सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। I/O एवं मेमोरी आवश्यकताओं को कम करने के लिए डेटा संकुचित ग्राफ़ प्रतिनिधित्व विकसित किया गया है। हफ़मैन कोडिंग जैसी सामान्य प्रौद्योगिकी प्रस्तावित हैं, किन्तु दक्षता बढ़ाने के लिए आसन्न सूची या आसन्न आव्यूह को विशिष्ट विधियों से संसाधित किया जा सकता है।^[12]

ग्राफ़ ट्रैवर्सल रणनीतियाँ

प्रथम चौड़ाई शोध

चौड़ाई-प्रथम शोध (बीएफएस) ट्रैवर्सल दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की शोध के लिए किया जाता है। यह ट्रैवर्सल प्रौद्योगिकी व्यक्तिगत नोड का चयन करती है, फिर समय में उसके प्रत्येक पड़ोसी को ज्ञात करती है। यह अतिरिक्त शीर्षों का निरीक्षण करना निरंतर रखता है एवं उन्हें पूर्ण करने के पश्चात निकटवर्ती शीर्षों के लिए प्रक्रिया को दोहराता है।^[13]

गहराई प्रथम शोध

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

^[13]

यह भी देखें

ग्राफ़ वॉकिंग रणनीतियों पर अधिक जानकारी के लिए ग्राफ ट्रैवर्सल
ग्राफ़ (डेटा संरचना) दृढ़ता के लिए ग्राफ़ डेटाबेस
ग्राफ़ के नियम आधारित परिवर्तनों के लिए ग्राफ़ पुनर्लेखन (ग्राफ़ डेटा संरचनाएं)
ग्राफ़ खींचने के लिए सॉफ़्टवेयर, प्रणाली एवं प्रणाली प्रदाताओं के लिए ग्राफ पुनर्लेखन सॉफ़्टवेयर

संदर्भ

↑ ^1.0 ^1.1 See, e.g. Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see Mehlhorn, K.; Näher, S. (1999). "Chapter 6: Graphs and their data structures". LEDA: A platform for combinatorial and geometric computing (PDF). Cambridge University Press. pp. 240–282.
↑ Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.
↑ Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363.
↑ Cormen et al. (2001), Exercise 22.1-7, p. 531.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531. ISBN 0-262-03293-7.
↑ Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". एल्गोरिथम डिज़ाइन और अनुप्रयोग. Wiley. pp. 355–364. ISBN 978-1-118-33591-8.
↑ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013). ग्राफ़ विभाजन और ग्राफ़ क्लस्टरिंग. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
↑ Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (March 2007). "समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.
↑ ^9.0 ^9.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. ISBN 978-3-030-25208-3.
↑ "ग्राफ़ का समानांतर प्रसंस्करण" (PDF).
↑ ^11.0 ^11.1 Buluç, A.; Madduri, Kamesh (2011). "Applications". वितरित मेमोरी सिस्टम पर समानांतर चौड़ाई-पहली खोज. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. doi:10.1145/2063384.2063471. ISBN 978-1-4503-0771-0. S2CID 6540738.
↑ Besta, Maciej; Hoefler, Torsten (27 April 2019). "दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण". arXiv:1806.01799 [cs.DS].
↑ ^13.0 ^13.1 Purti (July–September 2018). "ग्राफ ट्रैवर्सल और उसके अनुप्रयोग" (PDF). International Journal of Research and Analytical Reviews. 5 (3): 2.

बाहरी संबंध

Boost Graph Library: a powerful C++ graph library s.a. Boost (C++ libraries)
Networkx: a Python graph library
GraphMatcher a java program to align directed/undirected graphs.
GraphBLAS A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.

[gt-ops-1] 1.0 ^1.1 See, e.g. Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see Mehlhorn, K.; Näher, S. (1999). "Chapter 6: Graphs and their data structures". LEDA: A platform for combinatorial and geometric computing (PDF). Cambridge University Press. pp. 240–282.

[2] Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.

[3] Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363.

[4] Cormen et al. (2001), Exercise 22.1-7, p. 531.

[clrs-5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 22.1: Representations of graphs". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 527–531. ISBN 0-262-03293-7.

[gt-6] Goodrich, Michael T.; Tamassia, Roberto (2015). "Section 13.1: Graph terminology and representations". एल्गोरिथम डिज़ाइन और अनुप्रयोग. Wiley. pp. 355–364. ISBN 978-1-118-33591-8.

[Bader2013-7] Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013). ग्राफ़ विभाजन और ग्राफ़ क्लस्टरिंग. Contemporary Mathematics. Vol. 588. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.

[8] Lumsdaine, Andrew; Gregor, Douglas; Hendrickson, Bruce; Berry, Jonathan (March 2007). "समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.

[Sanders2019-9] 9.0 ^9.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer International Publishing. ISBN 978-3-030-25208-3.

[10] "ग्राफ़ का समानांतर प्रसंस्करण" (PDF).

[Buluc2011-11] 11.0 ^11.1 Buluç, A.; Madduri, Kamesh (2011). "Applications". वितरित मेमोरी सिस्टम पर समानांतर चौड़ाई-पहली खोज. 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. doi:10.1145/2063384.2063471. ISBN 978-1-4503-0771-0. S2CID 6540738.

[12] Besta, Maciej; Hoefler, Torsten (27 April 2019). "दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण". arXiv:1806.01799 [cs.DS].

[Purti-13] 13.0 ^13.1 Purti (July–September 2018). "ग्राफ ट्रैवर्सल और उसके अनुप्रयोग" (PDF). International Journal of Research and Analytical Reviews. 5 (3): 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 1: / Line 1: @@
 {{Short description|Abstract data type in computer science}}
-[[File:Directed.svg|160px|thumb|तीन वर्टेक्स (ग्राफ सिद्धांत) (नीले वृत्त) और तीन किनारे (ग्राफ सिद्धांत) (काले तीर) के साथ एक [[निर्देशित ग्राफ]]।]][[कंप्यूटर विज्ञान]] में, ग्राफ एक [[अमूर्त डेटा प्रकार]] है जिसका उद्देश्य गणित के भीतर [[ग्राफ सिद्धांत]] के क्षेत्र से ग्राफ (अलग गणित) और निर्देशित ग्राफ अवधारणाओं को लागू करना है।
+[[File:Directed.svg|160px|thumb|तीन शीर्ष (ग्राफ सिद्धांत) (नीले वृत्त) एवं तीन शीर्ष (ग्राफ सिद्धांत) (काले तीर) के साथ [[निर्देशित ग्राफ]] है।]][[कंप्यूटर विज्ञान]] में, '''ग्राफ''' [[अमूर्त डेटा प्रकार]] है जिसका उद्देश्य गणित के अंदर [[ग्राफ सिद्धांत]] के क्षेत्र से अप्रत्यक्ष ग्राफ एवं निर्देशित ग्राफ अवधारणाओं को प्रस्तावित करना है।
-एक ग्राफ़ डेटा संरचना में ''शीर्षों'' (जिसे ''नोड'' या ''बिंदु'' भी कहा जाता है) का एक परिमित (और संभवतः परिवर्तनशील) [[सेट (कंप्यूटर विज्ञान)]] होता है, साथ में इन शीर्षों के अव्यवस्थित जोड़े का एक सेट होता है। एक अप्रत्यक्ष ग्राफ़ के लिए या एक निर्देशित ग्राफ़ के लिए क्रमित युग्मों का एक सेट। इन जोड़ियों को ''किनारों'' (जिन्हें ''लिंक'' या ''लाइनें'' भी कहा जाता है) के रूप में जाना जाता है, और एक निर्देशित ग्राफ के लिए इन्हें ''किनारों'' के रूप में भी जाना जाता है, लेकिन कभी-कभी ''तीर'' या '' 'आर्क्स''। शीर्ष ग्राफ़ संरचना का हिस्सा हो सकते हैं, या पूर्णांक सूचकांकों या [[संदर्भ (कंप्यूटर विज्ञान)]] द्वारा दर्शाई गई बाहरी इकाइयाँ हो सकती हैं।
+ग्राफ़ डेटा संरचना में ''शीर्षों''  का परिमित (एवं संभवतः परिवर्तनशील) [[सेट (कंप्यूटर विज्ञान)|समुच्चय]] होता है, (जिसे ''नोड''  या ''बिंदु'' भी कहा जाता है) साथ में अप्रत्यक्ष ग्राफ़ के लिए इन शीर्षों के अव्यवस्थित जोड़े का समुच्चय या निर्देशित ग्राफ़ के लिए क्रमित युग्मों का समुच्चय है। इन जोड़ियों को ''किनारों''  के रूप में जाना जाता है (जिन्हें ''लिंक''  या रेखाएं भी कहा जाता है) , एवं निर्देशित ग्राफ के लिए इन्हें ''किनारों''  के रूप में भी जाना जाता है, किन्तु कभी-कभी तीर या ''आर्क्स के''  रूप में भी जाना जाता है। शीर्ष ग्राफ़ संरचना का भाग हो सकते हैं, या पूर्णांक सूचकांकों या [[संदर्भ (कंप्यूटर विज्ञान)|संदर्भ]] द्वारा प्रदर्शित की गई बाहरी इकाइयाँ हो सकती हैं।
-एक ग्राफ़ डेटा संरचना प्रत्येक किनारे से कुछ ''किनारे मान'' को भी जोड़ सकती है, जैसे कि एक प्रतीकात्मक लेबल या एक संख्यात्मक विशेषता (लागत, क्षमता, लंबाई, आदि)।
+ग्राफ़ डेटा संरचना प्रत्येक शीर्ष से कुछ ''शीर्ष मान''  को जैसे कि प्रतीकात्मक लेबल या संख्यात्मक विशेषता (लागत, क्षमता, लंबाई, आदि) भी जोड़ सकती है।
 ==संचालन==
-ग्राफ़ डेटा संरचना G द्वारा प्रदान किए गए बुनियादी संचालन में आमतौर पर शामिल हैं:<ref name="gt-ops">See, e.g. {{harvtxt|Goodrich|Tamassia|2015}}, Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see {{cite book |last1=Mehlhorn |first1=K. |author1-link=Kurt Mehlhorn |last2=Näher |first2=S. |year=1999 |title=LEDA: A platform for combinatorial and geometric computing |contribution=Chapter 6: Graphs and their data structures |publisher=Cambridge University Press |pages=240–282 |url=https://people.mpi-inf.mpg.de/~mehlhorn/ftp/LEDAbook/Graphs.pdf}}</ref>
+ग्राफ़ डेटा संरचना G द्वारा प्रदान किए गए बुनियादी संचालन में सामान्यतः सम्मिलित हैं:<ref name="gt-ops">See, e.g. {{harvtxt|Goodrich|Tamassia|2015}}, Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see {{cite book |last1=Mehlhorn |first1=K. |author1-link=Kurt Mehlhorn |last2=Näher |first2=S. |year=1999 |title=LEDA: A platform for combinatorial and geometric computing |contribution=Chapter 6: Graphs and their data structures |publisher=Cambridge University Press |pages=240–282 |url=https://people.mpi-inf.mpg.de/~mehlhorn/ftp/LEDAbook/Graphs.pdf}}</ref>
 * {{mono|adjacent(''G'', ''x'', ''y'')}}: परीक्षण करता है कि शीर्ष x से शीर्ष y तक कोई किनारा है या नहीं;
-* {{mono|neighbors(''G'', ''x'')}}: सभी शीर्षों y को इस प्रकार सूचीबद्ध करता है कि शीर्ष x से शीर्ष y तक एक किनारा हो;
+* {{mono|neighbors(''G'', ''x'')}}: सभी शीर्षों y को इस प्रकार सूचीबद्ध करता है कि शीर्ष x से शीर्ष y तक किनारा हो;
 * {{mono|add_vertex(''G'', ''x'')}}: शीर्ष x जोड़ता है, यदि वह वहां नहीं है;
-* {{mono|remove_vertex(''G'', ''x'')}}: शीर्ष x को हटा देता है, यदि वह वहां है;
+* {{mono|remove_vertex(''G'', ''x'')}}: शीर्ष x को निकाल देता है, यदि वह वहां है;
 * {{mono|add_edge(''G'', ''x'', ''y'', ''z'')}}: शीर्ष x से शीर्ष y तक किनारा z जोड़ता है, यदि यह वहां नहीं है;
-* {{mono|remove_edge(''G'', ''x'', ''y'')}}: किनारे को शीर्ष x से शीर्ष y तक हटा देता है, यदि वह वहां है;
+* {{mono|remove_edge(''G'', ''x'', ''y'')}}: शीर्ष को शीर्ष x से शीर्ष y तक निकाल देता है, यदि वह वहां है;
 * {{mono|get_vertex_value(''G'', ''x'')}}: शीर्ष x से संबद्ध मान लौटाता है;
-* {{mono|set_vertex_value(''G'', ''x'', ''v'')}}: शीर्ष x से v तक संबद्ध मान सेट करता है।
+* {{mono|set_vertex_value(''G'', ''x'', ''v'')}}: शीर्ष x से v तक संबद्ध मान निश्चित करता है।
-संरचनाएं जो मूल्यों को किनारों से जोड़ती हैं, आमतौर पर यह भी प्रदान करती हैं:<ref name="gt-ops"/>* {{mono|get_edge_value(''G'', ''x'', ''y'')}}: किनारे (x, y) से जुड़ा मान लौटाता है;
+संरचनाएं जो मूल्यों को किनारों से जोड़ती हैं, सामान्यतः यह भी प्रदान करती हैं:<ref name="gt-ops"/>* {{mono|get_edge_value(''G'', ''x'', ''y'')}}: शीर्ष (x, y) से जुड़ा मान लौटाता है;
-* {{mono|set_edge_value(''G'', ''x'', ''y'', ''v'')}}: किनारे (x, y) से जुड़े मान को v पर सेट करता है।
+* {{mono|set_edge_value(''G'', ''x'', ''y'', ''v'')}}: शीर्ष (x, y) से जुड़े मान को v पर निश्चित करता है।
 ==ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ==
 ; [[निकटवर्ती सूची]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 528–529; {{harvtxt|Goodrich|Tamassia|2015}}, pp. 361-362.</ref>
-: शीर्षों को रिकॉर्ड या ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्रत्येक शीर्ष आसन्न शीर्षों की एक [[सूची (कंप्यूटिंग)]] संग्रहीत करता है। यह डेटा संरचना शीर्षों पर अतिरिक्त डेटा के भंडारण की अनुमति देती है। यदि किनारों को ऑब्जेक्ट के रूप में भी संग्रहीत किया जाता है, तो अतिरिक्त डेटा संग्रहीत किया जा सकता है, इस स्थिति में प्रत्येक शीर्ष अपने घटना किनारों को संग्रहीत करता है और प्रत्येक किनारा अपने घटना शीर्षों को संग्रहीत करता है।
+: शीर्षों को रिकॉर्ड या ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, एवं प्रत्येक शीर्ष आसन्न शीर्षों की [[सूची (कंप्यूटिंग)|सूची]] संग्रहीत करता है। यह डेटा संरचना शीर्षों पर अतिरिक्त डेटा के भंडारण की अनुमति देती है। यदि किनारों को ऑब्जेक्ट के रूप में भी संग्रहीत किया जाता है, तो अतिरिक्त डेटा संग्रहीत किया जा सकता है, इस स्थिति में प्रत्येक शीर्ष अपने घटना किनारों को संग्रहीत करता है एवं प्रत्येक किनारा अपने घटना शीर्षों को संग्रहीत करता है।
-; [[सहखंडज मैट्रिक्स]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529–530; {{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;363.</ref>
+; [[सहखंडज मैट्रिक्स|सहखंडज आव्यूह]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, pp. 529–530; {{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;363.</ref>
-: एक द्वि-आयामी मैट्रिक्स, जिसमें पंक्तियाँ स्रोत शीर्षों का प्रतिनिधित्व करती हैं और स्तंभ गंतव्य शीर्षों का प्रतिनिधित्व करते हैं। किनारों और शीर्षों पर डेटा को बाहरी रूप से संग्रहीत किया जाना चाहिए। प्रत्येक जोड़ी शीर्षों के बीच केवल एक किनारे की लागत संग्रहीत की जा सकती है।
+: द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ स्रोत शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ गंतव्य शीर्षों का प्रतिनिधित्व करते हैं। किनारों एवं शीर्षों पर डेटा को बाहरी रूप से संग्रहीत किया जाना चाहिए। प्रत्येक जोड़ी शीर्षों के मध्य केवल शीर्ष की लागत संग्रहीत की जा सकती है।
-; [[घटना मैट्रिक्स]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p.&nbsp;531.</ref>
+; [[घटना मैट्रिक्स|घटना आव्यूह]]<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 22.1-7, p.&nbsp;531.</ref>
-: एक द्वि-आयामी मैट्रिक्स, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं और स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ एक पंक्ति में शीर्ष और एक स्तंभ में किनारे के बीच घटना संबंध को दर्शाती हैं।
+: द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ पंक्ति में शीर्ष एवं स्तंभ में शीर्ष के मध्य घटना संबंध को प्रदर्शित करती हैं।
-निम्न तालिका |V| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय जटिलता लागत देती है शीर्षों की संख्या और |ई| किनारों की संख्या.{{Citation needed|reason=Reliable source needed for the entire table below.|date=November 2011}} मैट्रिक्स अभ्यावेदन में, प्रविष्टियाँ एक किनारे का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे मौजूद नहीं हैं उनकी लागत ∞ मानी जाती है।
+निम्न तालिका |V| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय समष्टिता लागत देती है शीर्षों की संख्या एवं |ई| किनारों की संख्या आव्यूह अभ्यावेदन में, प्रविष्टियाँ शीर्ष का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे सम्मिलित नहीं हैं उनकी लागत ∞ मानी जाती है।
 {| class="wikitable"
 |-
 !
-! scope="col" | Adjacency list
+! scope="col" | निकटवर्ती सूची
-! scope="col" | Adjacency matrix
+! scope="col" | संलग्नता आव्यूह
-! scope="col" | Incidence matrix
+! scope="col" | घटना आव्यूह
 |-
-! scope="row" {{rh2|align=left}} | Store graph
+! scope="row" {{rh2|align=left}} | स्टोर ग्राफ़
 | <math>O(|V|+|E|)</math>
 | <math>O(|V|^2)</math>
 | <math>O(|V|\cdot|E|)</math>
 |-
-! scope="row" {{rh2|align=left}} | Add vertex
+! scope="row" {{rh2|align=left}} | शीर्ष जोड़ें
 | <math>O(1)</math>
 | <math>O(|V|^2)</math>
 | <math>O(|V|\cdot|E|)</math>
 |-
-! scope="row" {{rh2|align=left}} | Add edge
+! scope="row" {{rh2|align=left}} | किनारा जोड़ें
 | <math>O(1)</math>
 | <math>O(1)</math>
 | <math>O(|V|\cdot|E|)</math>
 |-
-! scope="row" {{rh2|align=left}} | Remove vertex
+! scope="row" {{rh2|align=left}} | शीर्ष हटाएँ
 | <math>O(|E|)</math>
 | <math>O(|V|^2)</math>
 | <math>O(|V|\cdot|E|)</math>
 |-
-! scope="row" {{rh2|align=left}} | Remove edge
+! scope="row" {{rh2|align=left}} | किनारा हटाएँ
 | <math>O(|V|)</math>
 | <math>O(1)</math>
 | <math>O(|V|\cdot|E|)</math>
 |-
-! scope="row" {{rh2|align=left}} | Are vertices ''x'' and ''y'' adjacent (assuming that their storage positions are known)?
+! scope="row" {{rh2|align=left}} | क्या शीर्ष x एवं y आसन्न हैं (यह मानते हुए कि उनकी भंडारण स्थिति ज्ञात है)?
 | <math>O(|V|)</math>
 | <math>O(1)</math>
 | <math>O(|E|)</math>
 |-
-! scope="row" {{rh2|align=left}} | Remarks
+! scope="row" {{rh2|align=left}} | टिप्पणियां
-| Slow to remove vertices and edges, because it needs to find all vertices or edges
+| शीर्षों एवं किनारों को हटाने में धीमी गति रखें, क्योंकि इसे सभी शीर्षों या किनारों को ढूंढने की आवश्यकता होती है
-| Slow to add or remove vertices, because matrix must be resized/copied
+| शीर्ष को जोड़ने या हटाने की गति धीमी है, क्योंकि मैट्रिक्स का आकार परिवर्तित/कॉपी करना आवश्यक है
-| Slow to add or remove vertices and edges, because matrix must be resized/copied
+| शीर्षों एवं किनारों को जोड़ने या हटाने में धीमी गति से, क्योंकि मैट्रिक्स का आकार कॉपी करना आवश्यक है
 |}
-आमतौर पर [[विरल ग्राफ]]़ के प्रतिनिधित्व के लिए आसन्नता सूचियों को प्राथमिकता दी जाती है, जबकि ग्राफ़ सघन होने पर आसन्नता मैट्रिक्स को प्राथमिकता दी जाती है; अर्थात् किनारों की संख्या |E| वर्ग शीर्षों की संख्या के करीब है, |V|<sup>2</sup>, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत ऊपर देखने में सक्षम होना चाहिए।<ref name=clrs>{{cite book |last1=Cormen|first1=Thomas H.  |author-link1=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author-link2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author-link3=Ronald L. Rivest |last4=Stein |first4=Clifford |author-link4=Clifford Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |chapter=Section 22.1: Representations of graphs |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |pages=527–531}}</ref><ref name=gt>{{cite book |last1=Goodrich |first1=Michael T. |author1-link=Michael T. Goodrich |last2=Tamassia |first2=Roberto |author2-link=Roberto Tamassia |year=2015 |title=एल्गोरिथम डिज़ाइन और अनुप्रयोग|contribution=Section 13.1: Graph terminology and representations |publisher=Wiley |isbn=978-1-118-33591-8 |pages=355–364}}</ref>
+सामान्यतः [[विरल ग्राफ]] के प्रतिनिधित्व के लिए आसन्नता सूचियों को प्राथमिकता दी जाती है, अपितु ग्राफ़ सघन होने पर आसन्नता आव्यूह को प्राथमिकता दी जाती है; अर्थात् किनारों की संख्या |E| वर्ग शीर्षों की संख्या |V|<sup>2</sup> के समीप है, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत देखने में सक्षम होना चाहिए।<ref name=clrs>{{cite book |last1=Cormen|first1=Thomas H.  |author-link1=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author-link2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author-link3=Ronald L. Rivest |last4=Stein |first4=Clifford |author-link4=Clifford Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |chapter=Section 22.1: Representations of graphs |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |pages=527–531}}</ref><ref name=gt>{{cite book |last1=Goodrich |first1=Michael T. |author1-link=Michael T. Goodrich |last2=Tamassia |first2=Roberto |author2-link=Roberto Tamassia |year=2015 |title=एल्गोरिथम डिज़ाइन और अनुप्रयोग|contribution=Section 13.1: Graph terminology and representations |publisher=Wiley |isbn=978-1-118-33591-8 |pages=355–364}}</ref>
 ==समानान्तर निरूपण==
-ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों का सामना करना पड़ता है: डेटा-संचालित गणना, असंरचित समस्याएं, खराब स्थानीयता और गणना अनुपात तक उच्च डेटा पहुंच।<ref name=Bader2013>{{cite book |last1=Bader |first1=David |last2=Meyerhenke |first2=Henning |last3=Sanders |first3=Peter |last4=Wagner |first4=Dorothea |date=January 2013 |title=ग्राफ़ विभाजन और ग्राफ़ क्लस्टरिंग|series=Contemporary Mathematics |publisher=American Mathematical Society |volume=588 |isbn=978-0-8218-9038-7 |doi=10.1090/conm/588/11709 |url=https://www.ams.org/conm/588/}}</ref><ref>{{cite journal |last1=Lumsdaine |first1=Andrew |last2=Gregor |first2=Douglas |last3=Hendrickson |first3=Bruce |last4=Berry |first4=Jonathan |date=March 2007 |title=समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ|journal=Parallel Processing Letters |issn=0129-6264 |doi=10.1142/s0129626407002843 |volume=17 |issue=1 |pages=5–20}}</ref> समानांतर आर्किटेक्चर के लिए उपयोग किया जाने वाला ग्राफ़ प्रतिनिधित्व उन चुनौतियों का सामना करने में महत्वपूर्ण भूमिका निभाता है। खराब तरीके से चुने गए प्रतिनिधित्व एल्गोरिदम की संचार लागत को अनावश्यक रूप से बढ़ा सकते हैं, जिससे इसकी [[ scalability ]] कम हो जाएगी। निम्नलिखित में, साझा और वितरित मेमोरी आर्किटेक्चर पर विचार किया जाता है।
+ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों डेटा-संचालित गणना, असंरचित समस्याएं, व्यर्थ स्थानीयता एवं गणना अनुपात तक उच्च डेटा पहुंच का सामना करना पड़ता है।<ref name=Bader2013>{{cite book |last1=Bader |first1=David |last2=Meyerhenke |first2=Henning |last3=Sanders |first3=Peter |last4=Wagner |first4=Dorothea |date=January 2013 |title=ग्राफ़ विभाजन और ग्राफ़ क्लस्टरिंग|series=Contemporary Mathematics |publisher=American Mathematical Society |volume=588 |isbn=978-0-8218-9038-7 |doi=10.1090/conm/588/11709 |url=https://www.ams.org/conm/588/}}</ref><ref>{{cite journal |last1=Lumsdaine |first1=Andrew |last2=Gregor |first2=Douglas |last3=Hendrickson |first3=Bruce |last4=Berry |first4=Jonathan |date=March 2007 |title=समानांतर ग्राफ़ प्रसंस्करण में चुनौतियाँ|journal=Parallel Processing Letters |issn=0129-6264 |doi=10.1142/s0129626407002843 |volume=17 |issue=1 |pages=5–20}}</ref> समानांतर आकृति के लिए उपयोग किया जाने वाला ग्राफ़ प्रतिनिधित्व उन चुनौतियों का सामना करने में महत्वपूर्ण भूमिका निभाता है। व्यर्थ उपाय से चयन किए गए प्रतिनिधित्व एल्गोरिदम की संचार लागत को अनावश्यक रूप से बढ़ा सकते हैं, जिससे इसकी [[ scalability | स्केलेबिलिटी]] कम हो जाती है। निम्नलिखित में, भाग एवं वितरित मेमोरी आकृति पर विचार किया जाता है।
-=== साझा स्मृति ===
+=== शेयर्ड मेमोरी ===
-साझा मेमोरी मॉडल के मामले में, समानांतर प्रसंस्करण के लिए उपयोग किए जाने वाले ग्राफ़ प्रतिनिधित्व अनुक्रमिक मामले के समान हैं,<ref name=Sanders2019>{{cite book |last1=Sanders |first1=Peter |last2=Mehlhorn |first2=Kurt |last3=Dietzfelbinger |first3=Martin |last4=Dementiev |first4=Roman |date=2019 |title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox |publisher=Springer International Publishing |isbn=978-3-030-25208-3 |url=https://www.springer.com/gp/book/9783030252083}}</ref> चूंकि ग्राफ़ प्रतिनिधित्व (उदाहरण के लिए एक आसन्न सूची) तक समानांतर पढ़ने-योग्य पहुंच साझा मेमोरी में कुशल है।
+शेयर्ड मेमोरी प्रारूप के विषय में, समानांतर प्रसंस्करण के लिए उपयोग किए जाने वाले ग्राफ़ प्रतिनिधित्व अनुक्रमिक विषय के समान हैं,<ref name=Sanders2019>{{cite book |last1=Sanders |first1=Peter |last2=Mehlhorn |first2=Kurt |last3=Dietzfelbinger |first3=Martin |last4=Dementiev |first4=Roman |date=2019 |title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox |publisher=Springer International Publishing |isbn=978-3-030-25208-3 |url=https://www.springer.com/gp/book/9783030252083}}</ref> चूंकि ग्राफ़ प्रतिनिधित्व (उदाहरण के लिए आसन्न सूची) तक समानांतर पढ़ने-योग्य पहुंच शेयर्ड मेमोरी में कुशल है।
-=== [[वितरित स्मृति]] ===
+=== [[वितरित स्मृति|वितरित मेमोरी]] ===
-वितरित मेमोरी मॉडल में, सामान्य दृष्टिकोण शीर्ष सेट को [[ग्राफ़ विभाजन]] करना है <math>V</math> ग्राफ़ के अंदर <math>p</math> सेट <math>V_0, \dots, V_{p-1}</math>. यहाँ, <math>p</math> उपलब्ध प्रसंस्करण तत्वों (पीई) की मात्रा है। वर्टेक्स सेट विभाजन को मिलान सूचकांक के साथ पीई में वितरित किया जाता है, इसके अलावा संबंधित किनारों पर भी। प्रत्येक पीई का अपना [[सबग्राफ (ग्राफ सिद्धांत)]] प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। [[संदेश पासिंग इंटरफ़ेस]] जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के मालिक पीई की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के दौरान, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।<ref name=Sanders2019/>
+वितरित मेमोरी प्रारूप में, सामान्य दृष्टिकोण ग्राफ के शीर्ष सेट <math>V</math> के अंदर <math>p</math> सेट को <math>V_0, \dots, V_{p-1}</math>का [[ग्राफ़ विभाजन]] करना है। यहाँ, <math>p</math> उपलब्ध प्रसंस्करण तत्वों (PE) की मात्रा है। शीर्ष सेट विभाजन को मिलान सूचकांक के साथ PE में, इसके अतिरिक्त संबंधित किनारों पर भी वितरित किया जाता है। प्रत्येक PE का स्वयं का [[सबग्राफ (ग्राफ सिद्धांत)|सबग्राफ]] प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। [[संदेश पासिंग इंटरफ़ेस]] जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के अधिकारिक PE की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के समय, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।<ref name=Sanders2019/>
-ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार और समान आकार के विभाजन के बीच एक समझौता है<ref>{{cite web |title=ग्राफ़ का समानांतर प्रसंस्करण|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf}}</ref> लेकिन ग्राफ़ को विभाजित करना एक एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके बजाय, निम्नलिखित अनुमानों का उपयोग किया जाता है।
+ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य भागीदारी है<ref>{{cite web |title=ग्राफ़ का समानांतर प्रसंस्करण|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf}}</ref>  किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है।
-डी विभाजन: प्रत्येक प्रोसेसर को मिलता है <math>n/p</math> शीर्ष और संगत आउटगोइंग किनारे। इसे आसन्न मैट्रिक्स के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर काम करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है <math>\mathcal{O}(m)</math> संदेश बफ़र आकार, क्योंकि प्रत्येक पीई में संभावित रूप से हर दूसरे पीई के लिए आउटगोइंग किनारे होते हैं।<ref name=Buluc2011>{{cite conference |last1=Buluç |first1=A. |last2=Madduri |first2=Kamesh |date=2011 |title=वितरित मेमोरी सिस्टम पर समानांतर चौड़ाई-पहली खोज|conference=2011 International Conference for High Performance Computing, Networking, Storage and Analysis |section=Applications |doi=10.1145/2063384.2063471 |s2cid=6540738 |number=65 |isbn=978-1-4503-0771-0}}</ref>
+डी विभाजन: प्रत्येक प्रोसेसर को <math>n/p</math> शीर्ष एवं संगत आउटगोइंग शीर्ष मिलता है। इसे आसन्न आव्यूह के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर कार्य करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है, <math>\mathcal{O}(m)</math> संदेश बफ़र आकार, क्योंकि प्रत्येक PE में संभावित रूप से हर दूसरे PE के लिए आउटगोइंग शीर्ष होते हैं।<ref name=Buluc2011>{{cite conference |last1=Buluç |first1=A. |last2=Madduri |first2=Kamesh |date=2011 |title=वितरित मेमोरी सिस्टम पर समानांतर चौड़ाई-पहली खोज|conference=2011 International Conference for High Performance Computing, Networking, Storage and Analysis |section=Applications |doi=10.1145/2063384.2063471 |s2cid=6540738 |number=65 |isbn=978-1-4503-0771-0}}</ref>2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत  <math>p = p_r \times p_c</math> में संरेखित हैं, जहाँ <math>p_r
-डी विभाजन: प्रत्येक प्रोसेसर को आसन्न मैट्रिक्स का एक सबमैट्रिक्स मिलता है। मान लें कि प्रोसेसर एक आयत में संरेखित हैं <math>p = p_r \times p_c</math>, कहाँ <math>p_r
+</math> एवं <math>p_c
-</math> और <math>p_c
+</math> क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को <math>(n/p_r)\times(n/p_c)</math> आयाम के आसन्न आव्यूह का [[सबमैट्रिक्स|सबआव्यूह]] मिलता है। इसे आव्यूह में [[ बिसात |बिसात]] प्रतिमान के रूप में देखा जा सकता है।<ref name=Buluc2011/>इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल ही पंक्ति एवं स्तंभ में PE के लिए आउटगोइंग शीर्ष हो सकते हैं। यह प्रत्येक PE के लिए संचार भागीदारों की <math>p_r + p_c - 1</math> से बाहर <math>p = p_r \times p_c</math> संभव वाले संख्या को सीमित करता है।
-</math> क्रमशः प्रत्येक पंक्ति और स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को आयाम के आसन्न मैट्रिक्स का एक [[सबमैट्रिक्स]] मिलता है <math>(n/p_r)\times(n/p_c)</math>. इसे मैट्रिक्स में [[ बिसात ]] पैटर्न के रूप में देखा जा सकता है।<ref name=Buluc2011/>इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल एक ही पंक्ति और स्तंभ में पीई के लिए आउटगोइंग किनारे हो सकते हैं। यह प्रत्येक पीई के लिए संचार भागीदारों की संख्या को सीमित करता है <math>p_r + p_c - 1</math> से बाहर <math>p = p_r \times p_c</math> संभव वाले.
 ==संकुचित अभ्यावेदन==
-[[ यंत्र अधिगम ]], सोशल नेटवर्क विश्लेषण और अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। I/O और मेमोरी आवश्यकताओं को कम करने के लिए डेटा संपीड़न ग्राफ़ प्रतिनिधित्व विकसित किया गया है। [[हफ़मैन कोडिंग]] जैसी सामान्य तकनीकें लागू हैं, लेकिन दक्षता बढ़ाने के लिए आसन्न सूची या आसन्न मैट्रिक्स को विशिष्ट तरीकों से संसाधित किया जा सकता है।<ref>{{cite arXiv |last1=Besta |first1=Maciej |last2=Hoefler |first2=Torsten |date=27 April 2019 |title=दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण|class=cs.DS |eprint=1806.01799}}</ref>
+[[ यंत्र अधिगम | यंत्र अधिगम]], सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। I/O एवं मेमोरी आवश्यकताओं को कम करने के लिए डेटा संकुचित ग्राफ़ प्रतिनिधित्व विकसित किया गया है। [[हफ़मैन कोडिंग]] जैसी सामान्य प्रौद्योगिकी प्रस्तावित हैं, किन्तु दक्षता बढ़ाने के लिए आसन्न सूची या आसन्न आव्यूह को विशिष्ट विधियों से संसाधित किया जा सकता है।<ref>{{cite arXiv |last1=Besta |first1=Maciej |last2=Hoefler |first2=Torsten |date=27 April 2019 |title=दोषरहित ग्राफ संपीड़न और अंतरिक्ष-कुशल ग्राफ प्रतिनिधित्व का सर्वेक्षण और वर्गीकरण|class=cs.DS |eprint=1806.01799}}</ref>
 == ग्राफ़ ट्रैवर्सल रणनीतियाँ ==
-=== चौड़ाई पहली खोज ===
+=== प्रथम चौड़ाई शोध ===
-चौड़ाई-प्रथम खोज (बीएफएस) ट्रैवर्सल एक दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की खोज के लिए किया जाता है। यह ट्रैवर्सल तकनीक एक व्यक्तिगत नोड चुनती है, फिर एक समय में उसके प्रत्येक पड़ोसी का पता लगाती है। यह अतिरिक्त शीर्षों का निरीक्षण करना जारी रखता है और उन्हें पूरा करने के बाद आस-पास के सभी शीर्षों के लिए प्रक्रिया को दोहराता है।<ref name="Purti">{{cite journal |author=Purti |date=July–September 2018 |title=ग्राफ ट्रैवर्सल और उसके अनुप्रयोग|journal=International Journal of Research and Analytical Reviews |volume=5 |issue=3 |page=2 |url=http://ijrar.com/upload_issue/ijrar_issue_1836.pdf}}</ref>
+चौड़ाई-प्रथम शोध (बीएफएस) ट्रैवर्सल दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की शोध के लिए किया जाता है। यह ट्रैवर्सल प्रौद्योगिकी व्यक्तिगत नोड का चयन करती है, फिर समय में उसके प्रत्येक पड़ोसी को ज्ञात करती है। यह अतिरिक्त शीर्षों का निरीक्षण करना निरंतर रखता है एवं उन्हें पूर्ण करने के पश्चात निकटवर्ती शीर्षों के लिए प्रक्रिया को दोहराता है।<ref name="Purti">{{cite journal |author=Purti |date=July–September 2018 |title=ग्राफ ट्रैवर्सल और उसके अनुप्रयोग|journal=International Journal of Research and Analytical Reviews |volume=5 |issue=3 |page=2 |url=http://ijrar.com/upload_issue/ijrar_issue_1836.pdf}}</ref>
-=== गहराई पहली खोज ===
+=== गहराई प्रथम शोध ===
-गहराई-प्रथम खोज एल्गोरिदम के मामले में नए शीर्ष की खोज किसी भी बिंदु पर शुरू होती है। इस नए शीर्ष की जांच के बाद, चयनित शीर्ष की जांच जारी रहती है। जब सभी पहुंच योग्य शिखरों का गहन अन्वेषण कर लिया जाता है, तो खोज समाप्त हो जाती है। पुनरावर्ती तरीके से प्रस्तुत किए जाने पर यह खोज प्रक्रिया सबसे अच्छा काम करती है। डीएफएस एक ऐसी विधि का उपयोग करता है जो जब भी संभव हो ग्राफ़ का गहराई से अन्वेषण करता है। क्योंकि खोज कई स्रोतों से दोहराई जा सकती है, डीएफएस द्वारा बनाया गया पूर्ववर्ती सबग्राफ विभिन्न पेड़ों से बना हो सकता है।
+गहराई-प्रथम शोध एल्गोरिदम के विषय में नए शीर्ष की शोध किसी भी बिंदु पर प्रारम्भ होती है। इस नए शीर्ष की शोध के पश्चात, चयनित शीर्ष की शोध निरंतर रहती है। जब सभी पहुंच योग्य शिखरों का गहन अन्वेषण कर लिया जाता है, तो शोध समाप्त हो जाती है। पुनरावर्ती उपाय से प्रस्तुत किए जाने पर यह शोध प्रक्रिया उत्तम कार्य करती है। डीएफएस ऐसी विधि का उपयोग करता है जो जब भी संभव हो ग्राफ़ का गहराई से अन्वेषण करता है। क्योंकि शोध कई स्रोतों से दोहराई जा सकती है, डीएफएस द्वारा बनाया गया पूर्ववर्ती सबग्राफ विभिन्न पेड़ों से बना हो सकता है।
- <ref name="Purti" />
+<ref name="Purti" />
@@ Line 111: / Line 111: @@
 * ग्राफ़ (डेटा संरचना) दृढ़ता के लिए [[ग्राफ़ डेटाबेस]]
 * ग्राफ़ के नियम आधारित परिवर्तनों के लिए ग्राफ़ पुनर्लेखन (ग्राफ़ डेटा संरचनाएं)
-* ग्राफ़ खींचने के लिए सॉफ़्टवेयर, सिस्टम और सिस्टम प्रदाताओं के लिए [[ग्राफ पुनर्लेखन]] सॉफ़्टवेयर
+* ग्राफ़ खींचने के लिए सॉफ़्टवेयर, प्रणाली एवं प्रणाली प्रदाताओं के लिए [[ग्राफ पुनर्लेखन]] सॉफ़्टवेयर
 ==संदर्भ==
@@ Line 127: / Line 127: @@
 {{Data structures}}
-{{DEFAULTSORT:Graph (Abstract Data Type)}}[[Category: ग्राफ सिद्धांत]] [[Category: ग्राफ़ डेटा संरचनाएँ| ग्राफ़ डेटा संरचनाएँ]] [[Category: सार डेटा प्रकार]] [[Category: रेखांकन]] [[Category: हाइपरग्राफ]]
+{{DEFAULTSORT:Graph (Abstract Data Type)}}
-[[Category: Machine Translated Page]]
+[[Category:Collapse templates|Graph (Abstract Data Type)]]
-[[Category:Created On 10/07/2023]]
+[[Category:Commons category link from Wikidata|Graph (Abstract Data Type)]]
+[[Category:Created On 10/07/2023|Graph (Abstract Data Type)]]
+[[Category:Lua-based templates|Graph (Abstract Data Type)]]
+[[Category:Machine Translated Page|Graph (Abstract Data Type)]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Graph (Abstract Data Type)]]
+[[Category:Pages with script errors|Graph (Abstract Data Type)]]
+[[Category:Sidebars with styles needing conversion|Graph (Abstract Data Type)]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Graph (Abstract Data Type)]]
+[[Category:Templates generating microformats|Graph (Abstract Data Type)]]
+[[Category:Templates that add a tracking category|Graph (Abstract Data Type)]]
+[[Category:Templates that are not mobile friendly|Graph (Abstract Data Type)]]
+[[Category:Templates that generate short descriptions|Graph (Abstract Data Type)]]
+[[Category:Templates using TemplateData|Graph (Abstract Data Type)]]
+[[Category:Wikipedia metatemplates|Graph (Abstract Data Type)]]
+[[Category:ग्राफ सिद्धांत|Graph (Abstract Data Type)]]
+[[Category:ग्राफ़ डेटा संरचनाएँ| ग्राफ़ डेटा संरचनाएँ]]
+[[Category:रेखांकन|Graph (Abstract Data Type)]]
+[[Category:सार डेटा प्रकार|Graph (Abstract Data Type)]]
+[[Category:हाइपरग्राफ|Graph (Abstract Data Type)]]

v t e Graph representations
Data structures	Graph (abstract data type) Adjacency list Edge list Adjacency matrix Incidence matrix
XML-based formats	DGML DotML GEXF GraphML GXL XGMML
Text-based formats	DOT Graph Modelling Language (GML) LCF notation for cubic Hamiltonian graphs Newick format for trees Trivial Graph Format
Related concepts	Graph database Graph drawing Linked data

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

ग्राफ़ (सार डेटा प्रकार): Difference between revisions

Namespaces

More

Page actions

Latest revision as of 19:32, 21 July 2023

Contents

संचालन

ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ