बीएफएस बाइनरी ट्री जो पायथन में स्टैक को लागू करता है

Question 1

मैं स्टैक (कतार नहीं!) का उपयोग करके पायथन में बाइनरी पेड़ के बीएफएस (चौड़ाई-पहली खोज) को लागू करने की तलाश में हूं।

class Stack:
    def __init__(self):
        self.data = []
        
    def Empty(self):
        return self.data == []

    def Push(self, x):
        self.data.append(x)

    def Pop(self):
        return self.data.pop()

    def Peek(self):
        return self.data[len(self.data)-1]

    def Size(self):
        return len(self.data)


class Node:
    def __init__(self, data, left, right):
        self.data = data
        self.l_node = left
        self.r_node = right


class Tree:
    def __init__(self):
        self.root= None

    def bfs_stack(self, node):
        pass


t = Tree()
t.root = Node("1")
t.root.l_node = Node("2")
t.root.l_node.l_node = Node("4")
t.root.l_node.r_node = Node("5")
t.root.l_node.r_node.l_node = Node("8")
t.root.r_node = Node("3")
t.root.r_node.l_node = Node("6")
t.root.r_node.r_node = Node("7")
t.root.r_node.r_node.l_node = Node("9")
t.root.r_node.r_node.l_node.l_node = Node("11")
t.root.r_node.r_node.r_node = Node("10")

मैंने काम करने के लिए स्टैक() वर्ग बनाया है। मैंने रिकर्सन और स्टैक पुशिंग को गठबंधन करने की कोशिश की लेकिन मैं विचारों से बाहर हूं।

कतार कार्यान्वयन बहुत आसान है लेकिन मेरे लिए स्टैक() कार्यान्वयन होना महत्वपूर्ण है।

python stack binary-tree breadth-first-search tree-traversal

1

user14987279 12 जिंदा 2021, 04:25

Answer

एल्गोरिदमिक रूप से, एक बीएफएस कतार संचालन से जुड़ा हुआ है और डीएफएस स्टैक संचालन से जुड़ा हुआ है।

यदि आपके पास केवल ढेर हैं, तो आप दो ढेर में से एक कतार की तरह कुछ बना सकते हैं।

स्टैक एक FILO (फर्स्ट-इन, लास्ट-आउट) ऑर्डर को लागू करते हैं, जबकि क्यू FIFO (फर्स्ट-इन, फर्स्ट-आउट) को लागू करते हैं।

यदि आप तीन नंबर, 1,2,3 को एक स्टैक में रखते हैं, और उन्हें बाहर निकालते हैं, तो आप 3,2,1 के साथ आते हैं।

यदि आप एक कतार के साथ ऐसा ही करते हैं, तो वे 1,2,3 के रूप में सामने आएंगे।

अब मान लीजिए कि हम स्टैक ए में 1,2,3 डालते हैं, उन्हें 3,2,1 के रूप में निकालते हैं, और उन्हें स्टैक बी में डालते हैं। उन्हें स्टैक बी से बाहर निकालने से उन्हें 1,2,3 के रूप में प्राप्त होगा, जिसका अर्थ है कि जा रहा है दो ढेर के माध्यम से एक कतार के माध्यम से जाने जैसा दिखता है।

अब यह तर्क अपने आप काम करता है यदि आपके पास पूरा अनुक्रम है और सब कुछ एक ही बार में इनपुट करें और फिर इसे बाहर निकालें। लेकिन बीएफएस/डीएफएस खोज के लिए यह सच नहीं है, आप कुछ चीजें इनपुट करते हैं, फिर अधिक इनपुट करने से पहले उन्हें बाहर निकाल देते हैं।

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

stack_a = Stack()
stack_b = Stack()

stack_b.Push(t.root)
while len(stack_a)+len(stack_b)>0:
    if len(stack_b) >0:
        current_node = stack_b.Pop()
    else:
        while len(stack_a)> 0:
            stack_b.Push(stack_a.Pop())
        current_node = stack_b.Pop()
    process(current_node) # this gets called on nodes in BFS order
    for neighbor in [current_node.l_node, current_node.r_node]:
        stack_a.Push(neighbor)
        #can generalize this to non-binary graphs by iterating through all unvisited neighbors
        #for cyclical graphs, must track processed nodes to ensure nodes don't get processed more than once

1

Matt Miguel 12 जिंदा 2021, 06:18

Question 2