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

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

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

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

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

संचालन

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

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

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

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

साझा स्मृति

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

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

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

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

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