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

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

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

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

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

संचालन

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

• 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 तक संबद्ध मान निश्चित करता है।

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

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

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

निकटवर्ती सूची

शीर्षों को रिकॉर्ड या ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, एवं प्रत्येक शीर्ष आसन्न शीर्षों की सूची संग्रहीत करता है। यह डेटा संरचना शीर्षों पर अतिरिक्त डेटा के भंडारण की अनुमति देती है। यदि किनारों को ऑब्जेक्ट के रूप में भी संग्रहीत किया जाता है, तो अतिरिक्त डेटा संग्रहीत किया जा सकता है, इस स्थिति में प्रत्येक शीर्ष अपने घटना किनारों को संग्रहीत करता है एवं प्रत्येक किनारा अपने घटना शीर्षों को संग्रहीत करता है।

सहखंडज आव्यूह

द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ स्रोत शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ गंतव्य शीर्षों का प्रतिनिधित्व करते हैं। किनारों एवं शीर्षों पर डेटा को बाहरी रूप से संग्रहीत किया जाना चाहिए। प्रत्येक जोड़ी शीर्षों के मध्य केवल शीर्ष की लागत संग्रहीत की जा सकती है।

घटना आव्यूह

द्वि-आयामी आव्यूह, जिसमें पंक्तियाँ शीर्षों का प्रतिनिधित्व करती हैं एवं स्तंभ किनारों का प्रतिनिधित्व करते हैं। प्रविष्टियाँ पंक्ति में शीर्ष एवं स्तंभ में शीर्ष के मध्य घटना संबंध को प्रदर्शित करती हैं।

निम्न तालिका |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|² के समीप है, या यदि दो शीर्षों को जोड़ने वाला कोई किनारा है तो किसी को तुरंत देखने में सक्षम होना चाहिए।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

बाहरी संबंध

• 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.