यह पता लगाने के लिए कार्यक्रम कि क्या एक एज पायथन में न्यूनतम फैले हुए पेड़ का हिस्सा है

मान लीजिए कि हमारे पास 'किनारों' नाम का एक 2D मैट्रिक्स है, जो एक अप्रत्यक्ष ग्राफ का प्रतिनिधित्व करता है। मैट्रिक्स 'किनारों' में प्रत्येक आइटम एक किनारे का प्रतिनिधित्व करता है और फॉर्म (यू, वी, डब्ल्यू) का है। इसका मतलब है कि नोड्स यू और वी जुड़े हुए हैं और किनारे का वजन डब्ल्यू है। हमारे पास पूर्णांक ए और बी भी हैं, जो एक किनारे (ए, बी) का प्रतिनिधित्व करते हैं। हमें यह पता लगाना होगा कि क्या किनारा (ए, बी) न्यूनतम फैले हुए पेड़ का हिस्सा है।

नोट - ग्राफ को जोड़ा जाना है और किनारे (ए, बी) ग्राफ में मौजूद है।

तो, अगर इनपुट किनारों की तरह है =

[[0, 2, 100],
[1, 2, 200],
[1, 3, 100],
[2, 3, 300]],
a = 0
b = 2,

तो आउटपुट ट्रू होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

  • अगर a, b के समान है, तो

    • सही लौटें

  • अगर किनारे खाली हैं, तो

    • झूठी वापसी

  • किनारों में प्रत्येक 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 हटाएं

      • अगर findPath(किनारों, new_a, b) गैर-शून्य है, तो

        • सही लौटें

      • किनारों के अंत में x डालें

    • झूठी वापसी

अब मुख्य कार्य से, निम्न कार्य करें -

• वजन :=इनपुट ऐरे 'किनारों' से एज x का एज वेट, अगर

  • ((x[0] a के समान है और x[1] b के समान है) या(x[1] a के समान है और x[0] b के समान है))

• किनारों :=[किनारे x इनपुट सरणी किनारों से अगर x[2] <वजन]

• रिटर्न नॉट फाइंडपाथ (किनारों, ए, बी)

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

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