पायथन में सभी कोने के बीच एक ग्राफ के भीतर न्यूनतम लागत का योग जानने के लिए कार्यक्रम

मान लीजिए कि n शीर्षों और m किनारों वाला एक भारित आलेख है। किनारों का भार 2 की घात में होता है। ग्राफ़ के किसी भी शीर्ष से किसी भी शीर्ष तक पहुँचा जा सकता है, और यात्रा की लागत ग्राफ़ में सभी किनारे भारों का जोड़ होगी। हमें प्रत्येक जोड़े के बीच न्यूनतम लागत का योग निर्धारित करना होगा।

तो, अगर इनपुट पसंद है

और शीर्षों की संख्या (n) =6; तो आउटपुट 2696 होगा।

सभी दूरियों का योग 2696 है।

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

एक फ़ंक्शन परिभाषित करें par_finder() । यह मैं ले जाएगा, बराबर
- यदि पार[i] -1 के समान है, तो
  - वापसी मैं
- res:=par_finder(par[i], par)
- बराबर[i] :=रेस
- रिटर्न रेस
एक फंक्शन हेल्पर () को परिभाषित करें। यह ले जाएगा i, par, w, G, n
- बच्चा:=1
- जी में प्रत्येक आइटम के लिए[i], करें
  - यदि आइटम [0] बराबर के समान है, तो
    - अगले पुनरावृत्ति के लिए जाएं
  - अन्यथा,
    - बच्चा:=बच्चा + सहायक (आइटम [0], मैं, आइटम [1], जी, एन)
  - यदि बराबर -1 के समान नहीं है, तो
    - उत्तर:=उत्तर + बच्चा * (एन - बच्चा) *(1 * 2^डब्ल्यू)
  - बच्चा लौटाएं
G :=n + 1 अन्य सूचियों वाली एक नई सूची
किनारों:=एक नई सूची
सड़कों में प्रत्येक आइटम के लिए, करें
- यू:=आइटम [0]
- v:=आइटम[1]
- w:=आइटम[2]
- किनारों के अंत में (u-1, v-1, w) डालें
सूची के किनारों को किनारे के वज़न के अनुसार क्रमित करें
par :=आकार n + 1 की एक नई सूची -1 के साथ आरंभ की गई
r_edge :=एक नई सूची
किनारों में प्रत्येक i के लिए, करें
- यदि par_finder(i[0], par) par_finder(i[1], par) के समान है, तो
  - अगले पुनरावृत्ति के लिए जाएं
- अन्यथा,
  - r_edge के अंत में i डालें
  - जी के अंत में जोड़ी (i[1],i[2]) डालें[i[0]]
  - जोड़ी डालें (i[0],i[2])
  - par[par_finder(i[0], par)] :=par_finder(i[1], par)
उत्तर:=0
सहायक(0, -1, 0, जी, एन)
वापसी उत्तर

उदाहरण

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

def par_finder(i, par) :
    if par[i] == -1 :
         return i
    res = par_finder(par[i], par)
    par[i] = res
    return res

def helper(i, par, w, G, n) :
    global ans
    child = 1
    for item in G[i] :
        if item[0] == par :
            continue
        else :
            child += helper(item[0],i,item[1], G, n)
    if par != -1 :
        ans += child * (n - child) * (1 << w)
    return child

def solve(n, roads):
    global ans
    G = [[] for i in range(n + 1)]
    edges = []
    for item in roads :
        u,v,w = map(int, item)
        edges.append((u-1, v-1, w))
    edges = sorted(edges,key = lambda item : item[2])
    par = [-1 for i in range(n + 1)]
    r_edge = []
    for i in edges :
        if par_finder(i[0], par) == par_finder(i[1], par) :
            continue
        else :
            r_edge.append(i)
            G[i[0]].append((i[1],i[2]))
            G[i[1]].append((i[0],i[2]))
            par[par_finder(i[0], par)] = par_finder(i[1], par)
    ans = 0      
    helper(0, -1, 0, G, n)
    return ans

print(solve(6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]))

इनपुट

6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]