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

Revision as of 21:49, 18 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| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय जटिलता लागत देती है शीर्षों की संख्या एवं |ई| किनारों की संख्या आव्यूह अभ्यावेदन में, प्रविष्टियाँ किनारे का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे सम्मिलित नहीं हैं उनकी लागत ∞ मानी जाती है।

	Adjacency list	Adjacency matrix	Incidence matrix
Store graph	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
Add vertex	$O(1)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
Add edge	$O(1)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
Remove vertex	$O(\|E\|)$	$O(\|V\|^{2})$	$O(\|V\|\cdot \|E\|)$
Remove edge	$O(\|V\|)$	$O(1)$	$O(\|V\|\cdot \|E\|)$
Are vertices x and y adjacent (assuming that their storage positions are known)?	$O(\|V\|)$	$O(1)$	$O(\|E\|)$
Remarks	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|² के समीप है, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत देखने में सक्षम होना चाहिए।^[5]^[6]

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

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

साझा स्मृति

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

वितरित स्मृति

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

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

1डी विभाजन: प्रत्येक प्रोसेसर को मिलता है $n/p$ शीर्ष एवं संगत आउटगोइंग किनारे। इसे आसन्न आव्यूह के पंक्ति-वार या स्तंभ-वार अपघटन के रूप में समझा जा सकता है। इस प्रतिनिधित्व पर काम करने वाले एल्गोरिदम के लिए, इसके लिए ऑल-टू-ऑल संचार चरण की भी आवश्यकता होती है ${\mathcal {O}}(m)$ संदेश बफ़र आकार, क्योंकि प्रत्येक पीई में संभावित रूप से हर दूसरे पीई के लिए आउटगोइंग किनारे होते हैं।^[11] 2डी विभाजन: प्रत्येक प्रोसेसर को आसन्न आव्यूह का सबआव्यूह मिलता है। मान लें कि प्रोसेसर आयत में संरेखित हैं $p=p_{r}\times p_{c}$ , कहाँ $p_{r}$ एवं $p_{c}$ क्रमशः प्रत्येक पंक्ति एवं स्तंभ में प्रसंस्करण तत्वों की मात्रा है। फिर प्रत्येक प्रोसेसर को आयाम के आसन्न आव्यूह का सबआव्यूह मिलता है $(n/p_{r})\times (n/p_{c})$ . इसे आव्यूह में बिसात पैटर्न के रूप में देखा जा सकता है।^[11]इसलिए, प्रत्येक प्रसंस्करण इकाई में केवल ही पंक्ति एवं स्तंभ में पीई के लिए आउटगोइंग किनारे हो सकते हैं। यह प्रत्येक पीई के लिए संचार भागीदारों की संख्या को सीमित करता है $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 7: / Line 7: @@
 ==संचालन==
-ग्राफ़ डेटा संरचना 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|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 तक संबद्ध मान सेट करता है।
-संरचनाएं जो मूल्यों को किनारों से जोड़ती हैं, आमतौर पर यह भी प्रदान करती हैं:<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 पर सेट करता है।
 ==ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ==
 ; [[निकटवर्ती सूची]]<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"
@@ Line 72: / Line 72: @@
 | 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>
@@ Line 84: / Line 84: @@
 वितरित मेमोरी मॉडल में, सामान्य दृष्टिकोण शीर्ष सेट को [[ग्राफ़ विभाजन]] करना है <math>V</math> ग्राफ़ के अंदर <math>p</math> सेट <math>V_0, \dots, V_{p-1}</math>. यहाँ, <math>p</math> उपलब्ध प्रसंस्करण तत्वों (पीई) की मात्रा है। वर्टेक्स सेट विभाजन को मिलान सूचकांक के साथ पीई में वितरित किया जाता है, इसके अलावा संबंधित किनारों पर भी। प्रत्येक पीई का अपना [[सबग्राफ (ग्राफ सिद्धांत)]] प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। [[संदेश पासिंग इंटरफ़ेस]] जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के मालिक पीई की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के दौरान, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।<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> संदेश बफ़र आकार, क्योंकि प्रत्येक पीई में संभावित रूप से हर दूसरे पीई के लिए आउटगोइंग किनारे होते हैं।<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>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>(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> संभव वाले.
+</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>

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

Revision as of 21:49, 18 July 2023

Contents

संचालन

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