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

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

	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 1: / Line 1: @@
 {{Short description|Abstract data type in computer science}}
-[[File:Directed.svg|160px|thumb|तीन वर्टेक्स (ग्राफ सिद्धांत) (नीले वृत्त) और तीन किनारे (ग्राफ सिद्धांत) (काले तीर) के साथ एक [[निर्देशित ग्राफ]]।]][[कंप्यूटर विज्ञान]] में, ग्राफ एक [[अमूर्त डेटा प्रकार]] है जिसका उद्देश्य गणित के भीतर [[ग्राफ सिद्धांत]] के क्षेत्र से ग्राफ (अलग गणित) और निर्देशित ग्राफ अवधारणाओं को लागू करना है।
+[[File:Directed.svg|160px|thumb|तीन वर्टेक्स (ग्राफ सिद्धांत) (नीले वृत्त) एवं तीन किनारे (ग्राफ सिद्धांत) (काले तीर) के साथ एक [[निर्देशित ग्राफ]]।]][[कंप्यूटर विज्ञान]] में, '''ग्राफ''' [[अमूर्त डेटा प्रकार]] है जिसका उद्देश्य गणित के अंदर [[ग्राफ सिद्धांत]] के क्षेत्र से ग्राफ (भिन्न गणित) एवं निर्देशित ग्राफ अवधारणाओं को प्रस्तावित करना है।
-एक ग्राफ़ डेटा संरचना में ''शीर्षों'' (जिसे ''नोड'' या ''बिंदु'' भी कहा जाता है) का एक परिमित (और संभवतः परिवर्तनशील) [[सेट (कंप्यूटर विज्ञान)]] होता है, साथ में इन शीर्षों के अव्यवस्थित जोड़े का एक सेट होता है। एक अप्रत्यक्ष ग्राफ़ के लिए या एक निर्देशित ग्राफ़ के लिए क्रमित युग्मों का एक सेट। इन जोड़ियों को ''किनारों'' (जिन्हें ''लिंक'' या ''लाइनें'' भी कहा जाता है) के रूप में जाना जाता है, और एक निर्देशित ग्राफ के लिए इन्हें ''किनारों'' के रूप में भी जाना जाता है, लेकिन कभी-कभी ''तीर'' या '' 'आर्क्स''। शीर्ष ग्राफ़ संरचना का हिस्सा हो सकते हैं, या पूर्णांक सूचकांकों या [[संदर्भ (कंप्यूटर विज्ञान)]] द्वारा दर्शाई गई बाहरी इकाइयाँ हो सकती हैं।
+एक ग्राफ़ डेटा संरचना में ''शीर्षों'' (जिसे ''नोड'' या ''बिंदु'' भी कहा जाता है) का एक परिमित (एवं संभवतः परिवर्तनशील) [[सेट (कंप्यूटर विज्ञान)]] होता है, साथ में इन शीर्षों के अव्यवस्थित जोड़े का एक सेट होता है। एक अप्रत्यक्ष ग्राफ़ के लिए या एक निर्देशित ग्राफ़ के लिए क्रमित युग्मों का एक सेट। इन जोड़ियों को ''किनारों'' (जिन्हें ''लिंक'' या ''लाइनें'' भी कहा जाता है) के रूप में जाना जाता है, एवं एक निर्देशित ग्राफ के लिए इन्हें ''किनारों'' के रूप में भी जाना जाता है, लेकिन कभी-कभी ''तीर'' या '' 'आर्क्स''। शीर्ष ग्राफ़ संरचना का हिस्सा हो सकते हैं, या पूर्णांक सूचकांकों या [[संदर्भ (कंप्यूटर विज्ञान)]] द्वारा दर्शाई गई बाहरी इकाइयाँ हो सकती हैं।
 एक ग्राफ़ डेटा संरचना प्रत्येक किनारे से कुछ ''किनारे मान'' को भी जोड़ सकती है, जैसे कि एक प्रतीकात्मक लेबल या एक संख्यात्मक विशेषता (लागत, क्षमता, लंबाई, आदि)।
@@ Line 22: / Line 22: @@
 ==ग्राफ़ प्रतिनिधित्व के लिए सामान्य डेटा संरचनाएँ==
 ; [[निकटवर्ती सूची]]<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}}, Exercise 22.1-7, p.&nbsp;531.</ref>
-: एक द्वि-आयामी मैट्रिक्स, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं और स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ एक पंक्ति में शीर्ष और एक स्तंभ में किनारे के बीच घटना संबंध को दर्शाती हैं।
+: एक द्वि-आयामी मैट्रिक्स, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ एक पंक्ति में शीर्ष एवं एक स्तंभ में किनारे के बीच घटना संबंध को दर्शाती हैं।
-निम्न तालिका |V| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय जटिलता लागत देती है शीर्षों की संख्या और |ई| किनारों की संख्या.{{Citation needed|reason=Reliable source needed for the entire table below.|date=November 2011}} मैट्रिक्स अभ्यावेदन में, प्रविष्टियाँ एक किनारे का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे मौजूद नहीं हैं उनकी लागत ∞ मानी जाती है।
+निम्न तालिका |V| के साथ, इनमें से प्रत्येक प्रतिनिधित्व के लिए, ग्राफ़ पर विभिन्न संचालन करने की समय जटिलता लागत देती है शीर्षों की संख्या एवं |ई| किनारों की संख्या.{{Citation needed|reason=Reliable source needed for the entire table below.|date=November 2011}} मैट्रिक्स अभ्यावेदन में, प्रविष्टियाँ एक किनारे का अनुसरण करने की लागत को एन्कोड करती हैं। जो किनारे मौजूद नहीं हैं उनकी लागत ∞ मानी जाती है।
 {| class="wikitable"
@@ Line 76: / Line 76: @@
 ==समानान्तर निरूपण==
-ग्राफ समस्याओं के समानांतरीकरण में महत्वपूर्ण चुनौतियों का सामना करना पड़ता है: डेटा-संचालित गणना, असंरचित समस्याएं, खराब स्थानीयता और गणना अनुपात तक उच्च डेटा पहुंच।<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 ]] कम हो जाएगी। निम्नलिखित में, साझा एवं वितरित मेमोरी आर्किटेक्चर पर विचार किया जाता है।
 === साझा स्मृति ===
@@ 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> और <math>p_c
+</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>
@@ Line 99: / Line 99: @@
 === चौड़ाई पहली खोज ===
-चौड़ाई-प्रथम खोज (बीएफएस) ट्रैवर्सल एक दृष्टिकोण है जिसका उपयोग किसी दिए गए ग्राफ़ में सभी नोड्स की खोज के लिए किया जाता है। यह ट्रैवर्सल तकनीक एक व्यक्तिगत नोड चुनती है, फिर एक समय में उसके प्रत्येक पड़ोसी का पता लगाती है। यह अतिरिक्त शीर्षों का निरीक्षण करना जारी रखता है और उन्हें पूरा करने के बाद आस-पास के सभी शीर्षों के लिए प्रक्रिया को दोहराता है।<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>
@@ Line 111: / Line 111: @@
 * ग्राफ़ (डेटा संरचना) दृढ़ता के लिए [[ग्राफ़ डेटाबेस]]
 * ग्राफ़ के नियम आधारित परिवर्तनों के लिए ग्राफ़ पुनर्लेखन (ग्राफ़ डेटा संरचनाएं)
-* ग्राफ़ खींचने के लिए सॉफ़्टवेयर, सिस्टम और सिस्टम प्रदाताओं के लिए [[ग्राफ पुनर्लेखन]] सॉफ़्टवेयर
+* ग्राफ़ खींचने के लिए सॉफ़्टवेयर, सिस्टम एवं सिस्टम प्रदाताओं के लिए [[ग्राफ पुनर्लेखन]] सॉफ़्टवेयर
 ==संदर्भ==

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:06, 18 July 2023

Contents

संचालन

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