精华内容
下载资源
问答
  • 最小生成树python实现)
    2021-10-28 22:40:50

    本文只展示最小生成树Kruskal算法的python实现,我会尽量将代码注释清楚,至于算法原理,自行理解。

    
    
    #构建边的类,有两个端点和权重属性
    class side:
        def __init__(self,u,v,w):
            self.u=u
            self.v=v
            self.w=w
    #获取输入的点,并为每一个点打上唯一的标签     
    n=int(input('请输入点的个数'))
    r=[]
    for i in range(n):
        r.append(i)
    #查找每一个点的源头标签,通过更新路径节点实现压缩查找    
    def ys(i):
        if r[i]==i:
            return i
        else: 
            r[i]=ys(r[i])#查找的过程中更新了路径节点,方便下次查找。
            return r[i]
    #判断两个节点是否共源头,即是否已经在同一棵树
    def pd(u,v):
        if ys(u)!=ys(v): r[ys(u)]=ys(v); return 1
        else: return 0
    #构造列表存储side类,获取输入并进行相应的存储
    s=[]   
    print('请输入起始点和权重(逗号隔开,q结束):')
    while True:
        z=input()
        if z.upper()=='Q':break
        else:
            a,b,c=eval(z)
            s.append(side(a,b,c))
    #将边按照权重属性排序    
    s=sorted(s,key=lambda t:t.w)
    sum=0#计算代价
    #从小到大遍历side如果不同源就计入最小生成树标识新新属性为1否则为0
    for i in range(len(s)):
        if(pd(s[i].u,s[i].v)):
            sum+=s[i].w
            s[i].__dict__['pj']=1
        else:
            s[i].__dict__['pj']=0
            
    print('最小代价:',sum)
    #按照‘pj'标识依次输出最小生成树的边
    print('最小生成树:')
    for i in range(len(s)):
        if s[i].pj==1:
        	print('{}->{}'.format(s[i].u,s[i].v),end=' ')
    
    
    更多相关内容
  • 电子科技大学通信网理论基础课程设计 1.代码实现Prim实现#4(基于堆) 2.代码实现Kruskal实现#2(基于UNION-FIND) 3.设计实验,针对多组相同实例,比较真实运行时间
  • 主要为大家详细介绍了python最小生成树kruskal与prim算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 遇到了一道题,一开始以为是简单的最小生成树做完发现一直WA,学习了一下发现是朱刘算法,整理一下笔记P4716 最小树形图题目背景这是一道模板题。题目描述给定包含 nnn 个结点, mmm 条有向边的一个图。试求一棵以...

    遇到了一道题,一开始以为是简单的最小生成树

    做完发现一直WA,学习了一下发现是朱刘算法,整理一下笔记

    P4716 最小树形图

    题目背景

    这是一道模板题。

    题目描述

    给定包含 nnn 个结点, mmm 条有向边的一个图。试求一棵以结点 rrr 为根的最小树形图,并输出最小树形图每条边的权值之和,如果没有以 rrr 为根的最小树形图,输出 −1-1−1。

    输入格式

    第一行包含三个整数 n,m,rn,m,rn,m,r,意义同题目所述。

    接下来 mmm 行,每行包含三个整数 u,v,wu,v,wu,v,w,表示图中存在一条从 uuu 指向 vvv 的权值为 www 的有向边。

    输出格式

    如果原图中存在以 rrr 为根的最小树形图,就输出最小树形图每条边的权值之和,否则输出 −1-1−1。

    输入输出样例

    输入 #1

    4 6 1

    1 2 3

    1 3 1

    4 1 2

    4 2 2

    3 2 1

    3 4 1

    输出 #1

    3

    输入 #2

    4 6 3

    1 2 3

    1 3 1

    4 1 2

    4 2 2

    3 2 1

    3 4 1

    输出 #2

    4

    输入 #3

    4 6 2

    1 2 3

    1 3 1

    4 1 2

    4 2 2

    3 2 1

    3 4 1

    输出 #3

    -1

    说明/提示

    样例 111 解释

    最小树形图中包含第 222, 555, 666 三条边,总权值为 1+1+1=31 + 1 + 1 = 31+1+1=3

    样例 222 解释

    最小树形图中包含第 333, 555, 666 三条边,总权值为 2+1+1=42 + 1 + 1 = 42+1+1=4

    样例 333 解释

    无法构成最小树形图,故输出 −1-1−1 。

    数据范围

    对于所有数据,1≤u,v≤n≤1001 \leq u, v \leq n \leq 1001≤u,v≤n≤100, 1≤m≤1041 \leq m \leq 10^41≤m≤104, 1≤w≤1061 \leq w \leq 10^61≤w≤106。

    最小树形图

    一个有向图,存在从某个点为根的,可以到达所有点的一个最小生成树,则它就是最小树形图。

    简单来说,就是有向图的最小生成树

    朱刘算法

    为什么需要?

    如果是无向图,用prim或者kruskal算法很简单

    但是如果是有向图,就会有一些问题

    举个例子

    第一行包含三个整数n,m,r,意义同题目所述。

    接下来m行,每行包含三个整数u, v, w,表示图中存在一从u指向V的权值为w的有向边。

    对于所有数据,1≤u,v≤n≤100,1≤m≤10^4,1≤w≤10^6。

    输入:

    3 4 1

    1 2 8

    1 3 8

    2 3 4

    3 2 3

    45a3be313deb576511e79ff45a2291ef.png

    图画出来大概是这样子的,如果用prim算法的话就会和点的顺序有关。可能是11,可能是12

    所以我们需要一个适用于有向图的算法

    算法介绍

    朱刘算法只有3步,然后不断循环。

    找到每个点的最小入边。既然是生成树,那么对于每个点来说,只要选一个权值最小的入边就可以了。

    贪心思想。因为如果不是最小入边,那么它肯定不是最小树形图的一条边,考虑它是没有意义的。

    找环。找环找的是最小入边构成的新图的环。如果没找到环,那么一棵树就已经形成了,

    因为树就是没有环的图。再因为边权都是最小的,因此此时最小树形图就已经出来了,停止循环。

    如果第2步中找到了环,那么这个环就可以缩成一个点。然后构造新图,更新边权。

    示意图大致如下:

    bcd5961c943fdb66ff458c8b3f6eeff7.png

    实现

    class Edge:

    def __init__(self, u, v, w):

    self.u = u

    self.v = v

    self.w = w

    def __str__(self):

    return str(self.u) + str(self.v) + str(self.w)

    def zhuliu(edges, n, m, root):

    res = 0

    while True:

    pre = [-1]*n

    visited = [-1] * n

    circle = []

    inderee = [INF] * n

    # 寻找最小入边

    inderee[root] = 0

    for i in range(m):

    if edges[i].u != edges[i].v and edges[i].w < inderee[edges[i].v]:

    pre[edges[i].v] = edges[i].u

    inderee[edges[i].v] = edges[i].w

    # 有孤立点,不存在最小树形图

    for i in range(n):

    if i != root and inderee[i] == INF:

    return -1

    # 找有向h环

    tn = 0 # 记录环的个数

    circle = [-1] * n

    for i in range(n):

    res += inderee[i]

    v = i

    # 向前遍历找环,中止情况有:

    # 1. 出现带有相同标记的点,成环

    # 2. 节点属于其他环,说明进了其他环

    # 3. 遍历到root了

    while visited[v] != i and circle[v] == -1 and v != root:

    visited[v] = i

    v = pre[v]

    # 如果成环了才会进下面的循环,把环内的点的circle进行标记

    if v != root and circle[v] == -1:

    while circle[v] != tn:

    circle[v] = tn

    v = pre[v]

    tn += 1

    # 如果没有环了,说明一定已经找到了

    if tn == 0:

    break

    # 否则把孤立点都看作自环看待

    for i in range(n):

    if circle[i] == -1:

    circle[i] = tn

    tn += 1

    # 进行缩点,把点号用环号替代

    for i in range(m):

    v = edges[i].v

    edges[i].u = circle[edges[i].u]

    edges[i].v = circle[edges[i].v]

    # 如果边不属于同一个环

    if edges[i].u != edges[i].v:

    edges[i].w -= inderee[v]

    n = tn

    root = circle[root]

    return res

    INF = 9999999999

    if __name__ == '__main__':

    n, m, root = list(map(int, input().split()))

    edges = []

    for i in range(m):

    u, v, w = list(map(int, input().split()))

    # 输入的点是1开始的,-1改为0开始的

    edges.append(Edge(u-1, v-1, w))

    print(zhuliu(edges, n, m, root-1),end = "")

    展开全文
  • 求连通图的最小生成树是数据结构中讨论的一个重要问题.但在现实生活中.经常遇到如何得到连通图的所有最小生成树.针对此问题.运用“破圈法”思想,对所给的图进行约化,在约化图的基础上,提出了求全部最小生成树...
  • 最小生成树:Kruskal算法及python实现

    千次阅读 2021-03-06 13:57:27
    最小生成树算法在机器学习中的应用 我最近在看数据聚类方面的论文,有篇文章用改进的MST算法实现稀疏数据集的自动聚类,这种思路让我眼前一亮。该文的主要思路是将多维向量视为空间中的点,向量之间的距离看作边长...

    本人数学专业本科,研究生读的计算机,方向是深度学习相关的,在平时上课和自己自学,看论文都是深度学习和机器学习相关的。打算毕业之后从事机器学习相关工作,但是不知道学完Dl,ML的相关算法之后,还需不需要学习传统的数据结构,比如二叉树,图,队列,栈什么的,还有必要学习算法导论里的算法吗?如果都学的话,那感觉时间不够,而且这些难度都挺大的。有没有前辈来指点一二呢?

    这是今天逛知乎时看到的一个提问“学习机器学习深度学习之后,还需要掌握传统算法和数据结构吗?”。相信很多机器学习的初学者都会有类似的疑问,特别是半路出家的学习者。为什么这么说呢?因为计算机科班出身的学生,在本科期间都系统地学习过数据结构和算法,他们肯定不会提出这样的问题,他们在学习的过程中会真切感受到这些知识的巨大作用。

    最小生成树算法在机器学习中的应用

    我最近在看数据聚类方面的论文,有篇文章用改进的MST算法实现稀疏数据集的自动聚类,这种思路让我眼前一亮。该文的主要思路是将多维向量视为空间中的点,向量之间的距离看作边长,将距离小于设定阈值的数据用最小生成树连接起来实现数据集的聚类。最小生成树(MST)虽然是图论中的概念,但是在机器学习领域却有着意想不到的效果。

    0167754cf5ff8ed6c2a55c1d149ee274.png

    在上篇文章中,我们介绍了Prim算法的基本思路和python实现。当然除了Prim算法之外,还有很多其它的算法,比如本文将要介绍的Kruskal算法。与Prim算法一样,Kruskal算法也是贪心算法的一种,它的核心思想是:将边按照长度从小到大排序,并依次添加到MST中,但要确保不在MST中形成环路。

    Kruskal算法

    Kruskal算法与Prim算法有着明显的不同。Prim算法初始化两个集合分别保存MST节点和剩余节点,寻找连接两个集合的最小边,并将边添加到MST中。在整个过程中,边的添加始终是链式的,MST像树一样从根节点慢慢生长。而Kruskal算法只关心边的长度,很可能是多棵子树各子生长,最后组合成一棵完整的树。Kruskal算法的步骤如下:

    数据初始化:最小生成树MST为空集,边的集合E={,……},三元组中的P,,代表边的两个端点,W代表边的长度;添加边:按照由小到大的顺序,将边依次添加到MST中,如果新增加的边导致最小生成树出现环路,则删除这条边;循环执行第2步,直到MST中边的数量等于N-1(N是节点的总数)。

    4b6d9944e4b6da71cb9711c0e1e08200.png

    与Prim算法相比,Kruskal算法的描述要简单得多,它的核心在于判断新增加的边是否构成环路。本文的思路是为每个节点增加一个根节点属性,如果新增边的两个端点的根节点相同,说明他们已经在一个相同的子树中,增加该边肯定会出现环路,因此予以舍弃。

    python实现

    在数据初始化阶段,除了构建边长矩阵之外,还要构建一个包含所有边的数组。为了判断两个点的根节点是否相同,我们还要准备一个数组保存所有点的根节点。下图是数据初始化的完整代码,代码中使用了生成器generator、过滤器filter、combinations()函数、sorted()函数,非常pythonic。

    cfb91490fef01274a7d30dc65a5dd1d4.png

    判断新增的边是否会产生闭环是该算法的难点所在。通常的思路是判断两个点在新增边之前是否连通,这种算法的时间复杂度很高,查询效率较低。本文的思路是记录每个点的根节点信息,每当增加边成功,就把点的根节点修改为P点的根节点。当需要增加边时,只需要判断M和N的根节点是否相同就可以了。

    cb6aec4d27d345d5508b23b5d3eb47bb.png

    上图的代码已经非常简洁了,配合注释应该很容易理解。当然如果想让代码更加“面向对象”,可以定义两个类:边Edge和节点Node,端点、边长、根节点这些变量都可以当作属性封装到类中,这样会使代码更加清晰易懂。

    总结

    程序员绝对是世界上最聪明的一群人,在他们的大脑中存储了大量的设计模式、算法和数据结构,这些知识不仅可以用于应付本职工作,还可以在生活中发挥指导作用。流传于世的算法是无数高智商前辈先贤的智慧结晶,蕴涵了丰富的人生哲学。编程算法在你的生活中有哪些成功的应用案例,期待大家留言交流讨论。

    展开全文
  • Python详细实现普里姆算法 Python详细实现最小生成树

    普里姆算法概述

    • 先看一个应用场景:
      (1)修路问题:
      在这里插入图片描述
      (2)正确的思路:
      在这里插入图片描述

    最小生成树

    • 最小生成树:
      在这里插入图片描述
    • 图例解析:

    在这里插入图片描述

    普里姆算法

    • 介绍:
      在这里插入图片描述
    • 算法核心
      在这里插入图片描述
    • 图解:
      (1)分析:
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      (2)看上图知,它成功避开了长的路径(权值大的)

    Python实现普里姆算法

    # 创建最小生成树:村庄图
    class MinTree(object):
        # 创建图的邻接矩阵
        def create_graph(self, graph, vertex: int, data: [], weight: []):
            """
            :param graph:图对象
            :param vertex:图对应的顶点个数
            :param data:图的各个顶点的值
            :param weight:图的邻接矩阵
            """
            for i in range(vertex):  # 顶点
                graph.data[i] = data[i]
                for j in range(vertex):
                    graph.weight[i][j] = weight[i][j]
    
        # 显示图的方法
        def show_graph(self, graph):
            for link in graph.weight:
                print(link)
    
        # 编写prim算法,得到最小生成树
        def prim_algorithm(self, graph, v: int):
            """
            :param graph: 图对象
            :param v: 表示从图的第几个顶点开始生成,如:"A"->0 ,'B'->1...
            :return:
            """
            # visited[]标记结点(顶点)是否被访问过
            visited = [0] * graph.vertex  # 默认都是0,表示没有访问过
            visited[v] = 1  # 把当前这个结点标记为已访问过
            # h1和h2记录两个顶点的下标
            h1 = -1
            h2 = -1
            min_weight = 10000  # 将min_weight初始成一个大数,后面再遍历过程中,会被替换
            for k in range(1, graph.vertex):  # 因为有 graph.vertex顶点,普里姆算法结束后,有graph.vertex - 1条边
                # 确定每一次生成的子图,和哪个结点的距离最近
                for i in range(graph.vertex):  # i 表示被访问过的结点
                    for j in range(graph.vertex):  # j 表示还没有被访问过的结点
                        if visited[i] == 1 and visited[j] == 0 and graph.weight[i][j] < min_weight:
                            # 替换 min_weight(寻找已经被访问过的结点和未被访问过的结点
                            min_weight = graph.weight[i][j]
                            h1 = i
                            h2 = j
                # 找到一条边是最小的
                print('边 %s -> %s 权值: %d ' % (graph.data[h1], graph.data[h2], min_weight))
                # 将当前这个结点标记为已经访问
                visited[h2] = 1
                # min_weight重新设置为最大值
                min_weight = 10000
    
    
    class MGraph(object):
        def __init__(self, vertex):
            self.vertex = vertex  # 表示图的结点个数
            self.data = vertex * [0]  # 存放结点数据
            self.weight = [[0 for row in range(vertex)] for col in range(vertex)]  # 存放边,就是我们的邻接矩阵
    
    
    if __name__ == '__main__':
        vertex_data = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
        # 为了便于测试,直接传入weight,10000表示大数,表示两个点不联通
        weights = [[10000, 5, 7, 10000, 10000, 10000, 2],
                   [5, 10000, 10000, 9, 10000, 10000, 3],
                   [7, 10000, 10000, 10000, 8, 10000, 10000],
                   [10000, 9, 10000, 10000, 10000, 4, 10000],
                   [10000, 10000, 8, 10000, 10000, 5, 4],
                   [10000, 10000, 10000, 4, 5, 10000, 6],
                   [2, 3, 10000, 10000, 4, 6, 10000]]
        g = MGraph(len(vertex_data))
        tree = MinTree()
        tree.create_graph(g, len(vertex_data), vertex_data, weights)
        tree.show_graph(g)
        tree.prim_algorithm(g, 0)
        # tree.prim_algorithm(g, 1) 换个出发点测试下
    '''输出结果
    [10000, 5, 7, 10000, 10000, 10000, 2]
    [5, 10000, 10000, 9, 10000, 10000, 3]
    [7, 10000, 10000, 10000, 8, 10000, 10000]
    [10000, 9, 10000, 10000, 10000, 4, 10000]
    [10000, 10000, 8, 10000, 10000, 5, 4]
    [10000, 10000, 10000, 4, 5, 10000, 6]
    [2, 3, 10000, 10000, 4, 6, 10000]
    边 A -> G 权值: 2 
    边 G -> B 权值: 3 
    边 G -> E 权值: 4 
    边 E -> F 权值: 5 
    边 F -> D 权值: 4 
    边 A -> C 权值: 7 
    '''
    
    展开全文
  • Python——数据结构——图——最小生成树
  • num,edges) 关键数据结构 需要一个静态链表parent来表示生成树(树的双亲表示法) 需要一个dist数组表示当前生成树距离各个顶点的距离 parent = {} dist = {} 初始化 然后有一个非常关键的步骤是dist和parent的初始化...
  • Prim算法计算最小生成树(无向图&邻接矩阵)——C语言实现。
  • TLE3个点的代码,没办法,python循环太慢了。 #克鲁斯卡尔 global n,m global side global parent def find(x): while parent[x]!=-1: x=parent[x] return x def kruskal(): ans=0 #找到n-1条边就退出循环 ...
  • Python实现最小生成树(Prim算法)

    万次阅读 2019-04-27 11:04:06
    使用链表构建图,利用递归、栈实现Prim算法求取最小生成树。 或许实现的结果与最小生成树的定义有区别,下面代码的结果是:穷举所有的节点,获取从任何顶点出发的一条最小权重的路径。(此代码是博主自己实现,可能...
  • 首先要明白,复杂网络任意子节点的网络最短距离是最小生成树的一种,但和传统意义上的prim或kruskal算法求解最小生成树的方法略微不同。 传统意义上的prim或kruskal算法,选择的是遍历该网络图/树形图中的所有节点...
  • 最小生成树 一个有 n 个结点的带权无向图,在满足所有顶点都连接的前提下使得所有的边的权总和最小,即为最小生成树(Minimum Spanning Tree MST)。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求...
  • 最小生成树算法(python实现)

    万次阅读 2018-11-26 12:30:57
    Kruskal算法是一种构造最小生成树的简单算法,其中的思想比较简单。基本思想 设G=(V,E)是一个网络,其中|V|=n。Kruskal算法构造最小生成树的过程是: 初始时取包含G中所有n个顶点但没有任何边的孤立点子图T=(V,{})...
  • 1. 最小生成树最小生成树即为图中权值最小的生成树(生成树中所有边权重之和)。 例如对于无向图: 来说最小生成树就是: 1.1 最小生成树算法 最小生成树的算法主要有两个: Kruskal 算法 Prim 算法 1.1.1 ...
  • Python 实现Prim最小生成树算法

    万次阅读 2018-07-31 22:34:16
    最小生成树(MST):对于带权无向图所有的生成树中,代价最小的生成树称为图的最小生成树。 Prim算法:假设N=(V,E) 是具有n个顶点的连通图,设U是最小生成树中顶点的集合,设TE是最小生成树中边的集合;  初始,U...
  • 文章目录 库的版本号 最小生成树的知识点 PRIM算法 Kruskal算法 库的版本号 列了这个是因为在学习过程中,会有很多文章,可能时间稍微久点了,用起来因为版本迭代,函数可能发生了变化,但你也不确实到底是什么问题...
  • 最小生成树--Kruskal算法(Python

    千次阅读 2019-03-24 15:30:28
    如果是带权值的无向图,那么权值之和最小的生成树,我们就称之为最小生成树(MST, Minimum Spanning Tree)。 **1、Kruskal算法描述** Kruskal算法是基于贪心的思想得到的。首先把所有的边按照权值从小到大排列,...
  • Python实现并查集与最小生成树Kruskal算法
  • 最小生成树--Prim算法(Python

    千次阅读 2019-03-29 16:21:11
    1、Prim算法原理   Prim算法在找当前最近顶点时...  下面给出一个无向图G=(V,E),我们使用Prim算法来找它的最小生成树。   第一步,我们先随意选择一个顶点作为起始点(起始点的选取不会影响最小生成树...
  • prim算法(最小生成树) python实现

    千次阅读 2018-11-23 16:20:14
    # 最小生成树python实现 def prim(graph): n = len(graph) costs = [99999 for _ in range(n)] # 父结点到该结点的边权值 costs[0] = 0 parents = [-1 for _ in range(n)] visited = [False for _ in range(n)]...
  • Python数据结构最小生成树

    千次阅读 2019-10-26 09:58:03
    其实应用最小生成树能够很好的解决这类问题。即给定一幅加权无向图,找到它的一颗最小生成树。此类算法主要应用是电路元器件的设计,航空航线规划,电站电力分配,图像分析等领域。 最小生成树   图的生成树是它的...
  • 1、生成树和最小生成树 1.1 生成树 连通的无圈图称为树,就是不包含循环的回路的连通图。 对于无向连通图,生成树(Spanning tree)是原图的极小连通子图,它包含原图中的所有 n 个顶点,并且有保持图连通的最少的边...
  • 最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。 给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。 由V中的全部n个顶点和E中n-1条边构成的无向...
  • Python详细实现克鲁斯卡尔算法 Python详细实现最小生成树
  • 最小生成树python,prim

    2018-12-15 10:54:26
    普里姆算法的基本思想:普里姆算法是一种构造最小生成树的算法,它是按逐个将顶点连通的方式来构造最小生成树的。 从连通网络 N = { V, E }中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0, v),将其顶点...
  • Python附代码)Prim算法最小生成树(贪心算法) 一、问题描述 【问题描述】Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。 【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。 ...
  • mst:用最小生成树聚类

    2021-06-07 06:37:22
    mst 用最小生成树聚类

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,393
精华内容 10,157
关键字:

最小生成树python

友情链接: DCSrarA.rar