गोलांग में ग्राफ़ डेटा संरचना को कैसे कार्यान्वित करें

सॉफ़्टवेयर उद्योग में ग्राफ़-संबंधी समस्याएँ अक्सर आपके सामने आएंगी। चाहे तकनीकी साक्षात्कार में हो या ग्राफ़ का उपयोग करने वाले एप्लिकेशन बनाते समय।

ग्राफ़ मौलिक डेटा संरचनाएं हैं जिनका उपयोग सामाजिक नेटवर्क और परिवहन प्रणालियों से लेकर अनुशंसा इंजन और नेटवर्क विश्लेषण तक विभिन्न अनुप्रयोगों में किया जाता है।

ग्राफ़ क्या है, और आप गो में ग्राफ़ कैसे लागू कर सकते हैं?

ग्राफ़ क्या है?

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

एक ग्राफ़ इनमें से एक है डेटा संरचनाएँ जो आपको पता होनी चाहिए एक प्रोग्रामर के रूप में. ग्राफ़ वास्तविक दुनिया के विभिन्न परिदृश्यों को मॉडल करने और उनका विश्लेषण करने के लिए एक शक्तिशाली और लचीला तरीका प्रदान करते हैं, और यह उन्हें कंप्यूटर विज्ञान में एक मौलिक और मुख्य डेटा संरचना बनाता है।

सॉफ़्टवेयर जगत में उपयोग किए जाने वाले समस्या-समाधान एल्गोरिदम की एक विस्तृत विविधता ग्राफ़ पर आधारित है। इसमें आप ग्राफ़ में गहराई से उतर सकते हैं ग्राफ़ डेटा संरचना के लिए मार्गदर्शिका.

गोलांग में एक ग्राफ़ लागू करना

अधिकांश बार डेटा संरचना को स्वयं लागू करने के लिए, आपको इसे लागू करने की आवश्यकता होती है ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग (ओओपी) अवधारणाएँ, लेकिन गो में ओओपी लागू करना यह बिल्कुल वैसा नहीं है जैसा कि जावा और C++ जैसी अन्य भाषाओं में है।

ओओपी अवधारणाओं को लागू करने के लिए गो संरचनाओं, प्रकारों और इंटरफेस का उपयोग करता है, और ग्राफ़ डेटा संरचना और इसकी विधियों को लागू करने के लिए आपको इन सभी की आवश्यकता होती है।

एक ग्राफ़ में नोड्स (या शीर्ष) और किनारे होते हैं। नोड ग्राफ़ में एक इकाई या तत्व है। नोड का एक उदाहरण नेटवर्क पर एक उपकरण या सोशल नेटवर्क पर एक व्यक्ति है। जबकि एक किनारा दो नोड्स के बीच एक कनेक्शन या संबंध है।

गो में एक ग्राफ़ लागू करने के लिए, आपको सबसे पहले एक नोड संरचना को परिभाषित करना होगा जिसकी संपत्ति उसके पड़ोसी होगी। एक नोड के पड़ोसी अन्य नोड होते हैं जो सीधे नोड से जुड़े होते हैं।

निर्देशित ग्राफ़ में, किनारों की दिशाएँ होती हैं इसलिए केवल वे नोड्स जिन्हें कोई दिया गया नोड इंगित करता है, उसके पड़ोसी माने जाते हैं। जबकि अप्रत्यक्ष ग्राफ़ में, सभी नोड जो एक नोड के साथ एक किनारा साझा करते हैं, उसके पड़ोसी होते हैं।

निम्नलिखित कोड दर्शाता है कि कैसे नोड संरचना दिखती है:

type Node struct {
 Neighbors []*Node
}

इस लेख में, फोकस एक अप्रत्यक्ष ग्राफ़ पर होगा। हालाँकि, बेहतर स्पष्टता प्रदान करने के लिए, यहाँ क्या है नोड निर्देशित ग्राफ़ की संरचना इस प्रकार दिख सकती है:

type Node struct {
 OutNeighbors []*Node // outgoing edges
 InNeighbors []*Node // incoming edges
}

इस परिभाषा के साथ, पड़ोसी से बाहर स्लाइस उन नोड्स को संग्रहीत करेगा जिनमें वर्तमान नोड से आउटगोइंग किनारे हैं, और पड़ोसियों में स्लाइस उन नोड्स को संग्रहीत करेगा जिनसे वर्तमान नोड में आने वाले किनारे हैं।

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

निम्नलिखित कोड दिखाता है ग्राफ़ संरचना:

type Graph struct {
 nodes map[int]*Node
}

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

नए ग्राफ़ को आरंभ करने के लिए कंस्ट्रक्टर के रूप में कार्य करने के लिए आपको एक फ़ंक्शन की आवश्यकता है। यह आसन्न सूची के लिए मेमोरी आवंटित करेगा और आपको ग्राफ़ में नोड्स जोड़ने की अनुमति देगा। नीचे दिया गया कोड कंस्ट्रक्टर की परिभाषा है ग्राफ़ कक्षा:

funcNewGraph() *Graph {
return &Graph{
 nodes: make(map[int]*Node),
 }
}

अब आप ग्राफ़ पर विभिन्न प्रकार के ऑपरेशन करने के तरीकों को परिभाषित कर सकते हैं। ऐसे कई ऑपरेशन हैं जो आप ग्राफ़ पर कर सकते हैं, नोड्स जोड़ने से लेकर नोड्स के बीच किनारों का निर्माण, नोड्स की खोज, और बहुत कुछ।

इस आलेख में, आप ग्राफ़ में नोड्स और किनारों को जोड़ने के साथ-साथ उन्हें हटाने के कार्यों का पता लगाएंगे। निम्नलिखित कोड चित्रण इन परिचालनों को करने के लिए कार्यों के कार्यान्वयन हैं।

ग्राफ़ में एक नोड जोड़ना

ग्राफ़ में एक नया नोड जोड़ने के लिए, आपको सम्मिलन फ़ंक्शन की आवश्यकता है जो इस तरह दिखता है:

func(g *Graph)AddNode(nodeID int) {
if _, exists := g.nodes[nodeID]; !exists {
 newNode := &Node{
 Neighbors: []*Node{},
 }
 g.nodes[nodeID] = newNode
 fmt.Println("New node added to graph")
 } else {
 fmt.Println("Node already exists!")
 }
}

नोड जोड़ें फ़ंक्शन ग्राफ़ पर एक नया नोड जोड़ता है जिसमें आईडी को एक पैरामीटर के रूप में पास किया जाता है। फ़ंक्शन यह जाँचता है कि ग्राफ़ में जोड़ने से पहले समान आईडी वाला नोड पहले से मौजूद है या नहीं।

ग्राफ़ में एक किनारा जोड़ना

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

ग्राफ़ पर दो नोड्स के बीच एक किनारा जोड़ने का कार्य यहां दिया गया है:

func(g *Graph)AddEdge(nodeID1, nodeID2 int) {
 node1 := g.nodes[nodeID1]
 node2 := g.nodes[nodeID2]
 node1.Neighbors = append(node1.Neighbors, node2)
 node2.Neighbors = append(node2.Neighbors, node1)
}

बहुत साधारण! एक अप्रत्यक्ष ग्राफ़ में किनारों को जोड़ना बस दोनों नोड्स को एक दूसरे का पड़ोसी बनाने की प्रक्रिया है। फ़ंक्शन को पास की गई आईडी द्वारा दोनों नोड्स मिलते हैं और उन दोनों को एक-दूसरे से जोड़ देता है पड़ोसियों टुकड़ा।

ग्राफ़ से एक किनारा हटाना

किसी ग्राफ़ से एक नोड को हटाने के लिए, आपको इसे उसके सभी पड़ोसियों की सूचियों से हटाना होगा ताकि यह सुनिश्चित हो सके कि कोई डेटा विसंगतियां नहीं हैं।

किसी नोड को उसके सभी पड़ोसियों से हटाने की प्रक्रिया किनारों को हटाने (या तोड़ने) की प्रक्रिया के समान है कनेक्शन) नोड्स के बीच, इसलिए आपको एक को परिभाषित करने से पहले किनारों को हटाने के लिए फ़ंक्शन को परिभाषित करना होगा नोड्स हटाएं.

का कार्यान्वयन नीचे दिया गया है हटाएँकिनारा समारोह:

func(g *Graph)removeEdge(node, neighbor *Node) {
 index := -1
for i, n := range node.Neighbors {
if n == neighbor {
 index = i
break
 }
 }
if index != -1 {
 node.Neighbors = 
append(node.Neighbors[:index], node.Neighbors[index+1:]...)
 }
}
func(g *Graph)RemoveEdge(node, neighbor *Node) {
 g.removeEdge(node, neighbor)
 g.removeEdge(neighbor, node)
 fmt.Println("Edge successfully removed")
}

हटाएँकिनारा फ़ंक्शन दो नोड्स को पैरामीटर के रूप में स्वीकार करता है और मुख्य नोड के पड़ोसियों की सूची में दूसरे (पड़ोसी) नोड के सूचकांक की खोज करता है। इसके बाद यह पड़ोसी को वहां से हटाने के लिए आगे बढ़ता है नोड. पड़ोसियों नामक तकनीक का उपयोग करना टुकड़ा काटना.

निष्कासन स्लाइस के तत्वों को निर्दिष्ट सूचकांक तक (लेकिन शामिल नहीं) और निर्दिष्ट सूचकांक के बाद के स्लाइस के तत्वों को ले जाकर और उन्हें संयोजित करके काम करता है। निर्दिष्ट सूचकांक पर तत्व को छोड़ना।

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

ग्राफ़ से एक नोड हटाना

एक बार जब आप किनारों को हटाने में सक्षम हो जाते हैं, तो आप नोड्स को भी हटा सकते हैं। ग्राफ़ से नोड्स हटाने का कार्य नीचे दिया गया है:

func(g *Graph)RemoveNode(nodeID int) {
 node, exists := g.nodes[nodeID]
if !exists {
 fmt.Println("Node doesn't exist")
return
 }
for _, neighbor := range node.Neighbors {
 g.RemoveEdge(node, neighbor)
 }
delete(g.nodes, nodeID)
 fmt.Println("Node deleted successfully")
}

फ़ंक्शन उस नोड की आईडी स्वीकार करता है जिसे आपको हटाना है। यह अपने सभी किनारों को हटाने से पहले जाँचता है कि नोड मौजूद है या नहीं। इसके बाद यह गो के इनबिल्ट का उपयोग करके ग्राफ़ से नोड को हटा देता है मिटाना समारोह।

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

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

सही डेटा संरचनाओं का उपयोग करके अनुकूलित सॉफ़्टवेयर बनाएं

गो पहले से ही कुशल सॉफ्टवेयर एप्लिकेशन विकसित करने के लिए एक बेहतरीन मंच प्रदान करता है, लेकिन जब आप अच्छे की उपेक्षा करते हैं विकास प्रथाओं के कारण, यह आपके एप्लिकेशन की वास्तुकला और प्रदर्शन के लिए विभिन्न समस्याएं पैदा कर सकता है।

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