पायथन में एज के न्यूनतम स्पैनिंग ट्री का हिस्सा होने की जांच करने का प्रोग्राम

मान लीजिए हमारे पास 'edges' नामक एक 2D मैट्रिक्स है, जो एक अविभाजित ग्राफ का प्रतिनिधित्व करता है। मैट्रिक्स 'edges' में प्रत्येक आइटम एक एज दर्शाता है और (u, v, w) के रूप में है। इसका अर्थ है नोड्स u और v जुड़े हुए हैं और एज का वजन w है। हमारे पास पूर्णांक a और b भी हैं, जो एक एज (a,b) को दर्शाते हैं। हमें जांचना है कि एज (a, b) न्यूनतम स्पैनिंग ट्री का हिस्सा है या नहीं।

नोट - ग्राफ जुड़ा हुआ होना चाहिए और एज (a, b) ग्राफ में मौजूद होना चाहिए।

इसलिए, यदि इनपुट edges = [[0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300]], a = 0, b = 2 जैसा है, तो आउटपुट True होगा।

हल करने के चरण

• findPath() फ़ंक्शन परिभाषित करें। यह edges, a, b लेगा

  • यदि a, b के समान है, तो True लौटाएं

  • यदि edges खाली है, तो False लौटाएं

  • edges में प्रत्येक x के लिए, करें

    • यदि x[2], -1 के समान है, तो इटरेशन जारी रखें

    • new_a := -1

    • यदि x[0], a के समान है, तो new_a := x[1]

    • अन्यथा जब x[1], a के समान है, तो new_a := x[0]

    • यदि new_a, -1 के समान नहीं है, तो

      • x को edges से हटाएं

      • यदि findPath(edges, new_a, b) शून्येतर है, तो True लौटाएं

      • x को edges के अंत में डालें

  • False लौटाएं

• अब मुख्य फ़ंक्शन से, निम्नलिखित करें:

  • weight := इनपुट ऐरे 'edges' से एज x का वजन, यदि ((x[0], a और x[1], b के समान है) या (x[1], a और x[0], b के समान है))

  • edges := [इनपुट ऐरे edges से एज x यदि x[2] < weight]

  • not findPath(edges, a, b) लौटाएं

उदाहरण

class Solution:
    def findPath(self, edges, a, b):
        if a == b:
            return True
        if not edges:
            return False
        for x in edges:
            if x[2] == -1:
                continue
            new_a = -1
            if x[0] == a:
                new_a = x[1]
            elif x[1] == a:
                new_a = x[0]
            if new_a != -1:
                edges.remove(x)
                if self.findPath(edges, new_a, b):
                    return True
                edges.append(x)
        return False
    def solve(self, edges, a, b):
        weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[2]
        edges = [x for x in edges if x[2] < weight]
        return not self.findPath(edges, a, b)

ob = Solution()
print(ob.solve([
    [0, 2, 100],
    [1, 2, 200],
    [1, 3, 100],
    [2, 3, 300]
], 0, 2))

इनपुट

[[0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300]], 0, 2

आउटपुट

True