在Python中找到图中所有顶点中最小成本的和的程序

假设有一个有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 [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中的每个项目，请执行以下操作
  • u：= item[0]
  • v：= item[1]
  • w：= item[2]
  • 在edges的末尾插入（u-1，v-1，w）
• 按边权重排序列表edges
• par: =大小为n + 1且初始化为-1的新列表
• r_edge:=一个新的列表
• 对于每个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)]

输出

2696