पायथन - ग्राफ़ एल्गोरिदम

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

गहराई पहले ट्रैवर्सल:

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

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

जब उपरोक्त कोड निष्पादित किया जाता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है -

a b d e c

चौड़ाई पहला ट्रैवर्सल

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

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

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

जब उपरोक्त कोड निष्पादित किया जाता है, तो यह निम्नलिखित परिणाम उत्पन्न करता है -

a c b d e