पायथन में न्यूनतम लागत वाले शहरों को जोड़ना

मान लीजिए कि 1 से N तक N शहरों की संख्या है। हमारे पास कनेक्शन हैं, जहां प्रत्येक कनेक्शन [i] [शहर 1, शहर 2, लागत] है, यह शहर 1 और शहर 2 को एक साथ जोड़ने की लागत का प्रतिनिधित्व करता है . हमें न्यूनतम लागत का पता लगाना होगा ताकि शहरों की प्रत्येक जोड़ी के लिए, कनेक्शन का एक मार्ग मौजूद हो (संभवतः लंबाई 1 का) जो उन दो शहरों को एक साथ जोड़ता है। लागत उपयोग की गई कनेक्शन लागतों का योग है। यदि कार्य असंभव है, तो -1 लौटें।

तो अगर ग्राफ इस तरह है -

फिर आउटपुट 6 होगा, किन्हीं दो शहरों को चुनने से सभी शहर जुड़ जाएंगे, इसलिए हम न्यूनतम 2, [1, 5]

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

• खोज () नामक विधि को परिभाषित करें, इसमें x लगेगा

• अगर माता-पिता [x] -1 है, तो x लौटाएं

• माता-पिता [x]:=ढूंढें (माता-पिता [x])

• माता-पिता को लौटाएं[x]

• यूनियन () नामक एक और विधि बनाएं, इसमें x और y लगेंगे

• parent_x:=ढूंढें(x), parent_y:=ढूंढें(y)

• अगर parent_x =parent_y, तो वापस आएं, नहीं तो पैरेंट[parent_y] :=parent_x

• मुख्य विधि से, यह n और conn लेगा

• माता-पिता:=आकार n की एक सरणी और इसे -1 से भरें, सेट करें:=n - 1, लागत:=0

• c :=कॉन की क्रमबद्ध सूची, लागत के आधार पर इसे छाँटें

• मैं :=0

• जबकि मैं <सी की लंबाई और असंबद्ध 0 नहीं है

  • x :=c[i, 0] और y :=c[i, 1]

  • यदि खोज (x) खोज (y) के समान नहीं है, तो 1 से असंबद्ध घटाएं, c[i, 2] द्वारा लागत बढ़ाएं, और संघ (x, y) करें

  • 1 से बढ़ाएँ

• वापसी लागत जब असंबद्ध 0 है, अन्यथा वापसी -1

उदाहरण (पायथन)

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

class Solution(object):
   def find(self, x):
      if self.parent[x] == -1:
         return x
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]
   def union(self,x,y):
      parent_x = self.find(x)
      parent_y = self.find(y)
      if parent_x == parent_y:
         return
      self.parent[parent_y] = parent_x
   def minimumCost(self, n, connections):
      self.parent = [ -1 for i in range(n+1)]
      disjoint = n-1
      cost = 0
      c = sorted(connections,key=lambda v:v[2])
      i = 0
      while i<len(c) and disjoint:
         x = c[i][0]
         y = c[i][1]
         if self.find(x)!=self.find(y):
            disjoint-=1
            cost+=c[i][2]
            self.union(x,y)
            i+=1
         return cost if not disjoint else -1
ob = Solution()
print(ob.minimumCost(3, [[1,2,5], [1,3,6], [2,3,1]]))

इनपुट

3
[[1,2,5],[1,3,6],[2,3,1]]

आउटपुट

-1