View source for ग्राफ़ (सार डेटा प्रकार)

{{Short description|Abstract data type in computer science}}
[[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>
* {{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|add_edge(''G'', ''x'', ''y'', ''z'')}}: शीर्ष x से शीर्ष y तक किनारा z जोड़ता है, यदि यह वहां नहीं है;
* {{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) से जुड़ा मान लौटाता है;
* {{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}}, Exercise 22.1-7, p.&nbsp;531.</ref>
: द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ पंक्ति में शीर्ष एवं स्तंभ में शीर्ष के मध्य घटना संबंध को प्रदर्शित करती हैं।

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

{| class="wikitable"
|-
!
! scope="col" | निकटवर्ती सूची
! scope="col" | संलग्नता आव्यूह
! scope="col" | घटना आव्यूह
|-
! 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}} | शीर्ष जोड़ें
| <math>O(1)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! scope="row" {{rh2|align=left}} | किनारा जोड़ें
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! 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}} | किनारा हटाओ
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|V|\cdot|E|)</math>
|-
! scope="row" {{rh2|align=left}} | क्या शीर्ष x एवं y आसन्न हैं (यह मानते हुए कि उनकी भंडारण स्थिति ज्ञात है)?
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|E|)</math>
|-
! scope="row" {{rh2|align=left}} | टिप्पणियां
| शीर्षों एवं किनारों को हटाने में धीमी गति रखें, क्योंकि इसे सभी शीर्षों या किनारों को ढूंढने की आवश्यकता होती है
| शीर्ष को जोड़ने या हटाने की गति धीमी है, क्योंकि मैट्रिक्स का आकार बदलना/कॉपी करना आवश्यक है
| शीर्षों एवं किनारों को जोड़ने या हटाने में धीमी गति से, क्योंकि मैट्रिक्स का आकार कॉपी करना आवश्यक है
|}
सामान्यतः [[विरल ग्राफ]] के प्रतिनिधित्व के लिए आसन्नता सूचियों को प्राथमिकता दी जाती है, अपितु ग्राफ़ सघन होने पर आसन्नता आव्यूह को प्राथमिकता दी जाती है; अर्थात् किनारों की संख्या |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=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> उपलब्ध प्रसंस्करण तत्वों (PE) की मात्रा है। शीर्ष सेट विभाजन को मिलान सूचकांक के साथ PE में, इसके अतिरिक्त संबंधित किनारों पर भी वितरित किया जाता है। प्रत्येक PE का स्वयं का [[सबग्राफ (ग्राफ सिद्धांत)|सबग्राफ]] प्रतिनिधित्व होता है, जहां दूसरे विभाजन में समापन बिंदु वाले किनारों पर विशेष ध्यान देने की आवश्यकता होती है। [[संदेश पासिंग इंटरफ़ेस]] जैसे मानक संचार इंटरफेस के लिए, अन्य समापन बिंदु के मालिक PE की आईडी पहचान योग्य होनी चाहिए। वितरित ग्राफ एल्गोरिदम में गणना के समय, इन किनारों के साथ जानकारी पारित करने से संचार का तात्पर्य होता है।<ref name=Sanders2019/>

ग्राफ़ विभाजन को सावधानीपूर्वक करने की आवश्यकता है - कम संचार एवं समान आकार के विभाजन के मध्य समझौता है<ref>{{cite web |title=ग्राफ़ का समानांतर प्रसंस्करण|url=https://www.graphengine.io/downloads/papers/ParallelProcessingOfGraphs.pdf}}</ref>  किन्तु ग्राफ़ को विभाजित करना एनपी-हार्ड समस्या है, इसलिए उनकी गणना करना संभव नहीं है। इसके अतिरिक्त, निम्नलिखित अनुमानों का उपयोग किया जाता है।

1डी विभाजन: प्रत्येक प्रोसेसर को <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> एवं <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> संभव वाले संख्या को सीमित करता है।

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

[[ यंत्र अधिगम | यंत्र अधिगम]], सोशल नेटवर्क विश्लेषण एवं अन्य क्षेत्रों में खरबों किनारों वाले ग्राफ़ पाए जाते हैं। 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" />


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

==संदर्भ==
{{reflist}}


==बाहरी संबंध==
{{Commons category}}
*[http://www.boost.org/libs/graph Boost Graph Library: a powerful C++ graph library] s.a. [[Boost (C++ libraries)]]
*[https://networkx.org/ Networkx: a Python graph library]
*[http://www.graphmatcher.com GraphMatcher] a java program to align directed/undirected graphs.
*[http://graphblas.org GraphBLAS] A specification for a library interface for operations on graphs, with a particular focus on sparse graphs.
 
{{Graph representations}}
{{Data structures}}

{{DEFAULTSORT:Graph (Abstract Data Type)}}[[Category: ग्राफ सिद्धांत]] [[Category: ग्राफ़ डेटा संरचनाएँ| ग्राफ़ डेटा संरचनाएँ]] [[Category: सार डेटा प्रकार]] [[Category: रेखांकन]] [[Category: हाइपरग्राफ]] 



[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]