当前位置：极客教程 > Python 实例 > Python 程序 > 在Python中找到图中所有顶点中最小成本的和的程序

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

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

假设有一个有n个顶点和m条边的带权图。边权重是2的幂。可以从图中的任何顶点到达任何顶点，旅行的成本将是图中所有边权重的加和。我们将不得不确定每对顶点之间最小成本的总和。

如果输入如下所示

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

并且顶点数（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)]))
Python

输入

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

输出

2696
Python

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

登录

找回密码？

注册