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

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

इसलिए, यदि इनपुट इस तरह है

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

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

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

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

उदाहरण

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

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)]