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

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

इसलिए यदि ग्राफ इस तरह है -

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

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

• find() नामक मेथड परिभाषित करें, यह x लेगा

• यदि parent[x] -1 है, तो x लौटाएं

• parent[x] := find(parent[x])

• parent[x] लौटाएं

• union() नामक एक और मेथड बनाएं, यह x और y लेगा

• parent_x := find(x), parent_y := find(y)

• यदि parent_x = parent_y, तो लौटाएं, अन्यथा parent[parent_y] := parent_x

• मुख्य मेथड से, यह n और conn लेगा

• parent := आकार n का एक ऐरे और इसे -1 से भरें, disjoint := n - 1 सेट करें, cost := 0

• c := कनेक्शन्स की सॉर्ट की गई लिस्ट, इसे लागत के आधार पर सॉर्ट करें

• i := 0

• जब तक i < c की लंबाई और disjoint 0 नहीं है

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

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

  • i को 1 से बढ़ाएं

• लागत लौटाएं जब disjoint 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
इनपुट
3 [[1,2,5],[1,3,6],[2,3,1]]
आउटपुट
-1