精华内容
下载资源
问答
  • #Editing time : 2019/7/3 20:40 #File Name : 最小生成树prim算法.py from heapq import * class Node(object): pass class UnionFindSet(object): def __init__(self,nodes): self.fatherDict = {} ...
    #Editing time : 2019/7/3 20:40
    #File Name : 最小生成树prim算法.py
    
    from heapq import  *
    class Node(object):
        pass
    class UnionFindSet(object):
        def __init__(self,nodes):
            self.fatherDict = {}
            # key node  value father 一层一层向上找
            self.sizeDict = {}
            # key 节点  value 节点所在集合共有多少个节点
            for node in nodes:
                self.fatherDict[node]= node
                self.sizeDict[node] = 1
            #每个节点的父亲是自己 并且所在的集合为个数为1
            #因为要少挂多 ,所以要找节点数目
        def FindHead(self,node):
            stack = []
            father = self.fatherDict[node]
            while father!=node:
                stack.append(node)
                node = father
                father = self.fatherDict[node]
            while stack:
                self.fatherDict[stack.pop()] = father
            return father
        def isSameSet(self,a,b):
            return self.FindHead(a) == self.FindHead(b)
        def uion(self,a,b):
            if a is None or b is None:
                return
            aHead = self.FindHead(a)
            bHead = self.FindHead(b)
            if aHead!=bHead:
                asize = self.sizeDict[aHead]
                bsize = self.sizeDict[bHead]
                if asize<=bsize:
                    self.fatherDict[aHead] = bHead
                    self.sizeDict[bHead] = asize+bsize
                else:
                    self.fatherDict[bHead] = aHead
                    self.sizeDict[aHead] = asize+bsize
    
    class Node(object):
        def __init__(self,value=None):
            self.value = value #节点的值
            self.come = 0 #节点入度
            self.out = 0 #节点出度
            self.nexts = [] #节点的邻居节点
            self.edges = [] #在节点为from的情况下,边的集合
    class Edge(object):
        def __init__(self,weight=None,fro,to):
            self.weight = weight # 边的权重
            self.fro = fro # 边的from节点
            self.to = to #边的to节点
        def __lt__(self, other):
            return self.weight<other.weight
    class Graph(object):
        def __init__(self):
            self.nodes = {} #图所有节点的集合  字典形式 :{节点编号:节点}
            self.edges = [] #图的边集合
    
    def creatGraph(matrix):
        # 二维数组matrix [权重  从那个点的值  去哪个点的值]
        graph = Graph()
        # 建立所有节点
        for edge in matrix:
            weight = edge[0]
            fro = edge[1]
            to = edge[2]
            if fro not in graph.nodes:
                graph.nodes[fro] = Node(fro)
            if to not in graph.nodes:
                graph.nodes[to] = Node(to)
        #建立所有的边
            fromNode = graph.nodes[fro]
            toNode = graph.nodes[to]
            newEdge = Edge(weight,fromNode,toNode)
            fromNode.nexts.append(toNode) #加上邻居指向
            fromNode.out+=1 #出度+1
            toNode.come+=1 #to 的入度+1
            fromNode.edge.append(newEdge) #边的集合+1
            graph.edges.append(newEdge)
    
        return graph
        
    def primMST(graph):
        heapq = []
        set1 = set()
        res1 = set()
        #把节点与对应的边加入
        for node in graph.nodes.values():
            if node not in set1:
                set1.add(node)
                for edge in node.edges:
                    heappush(heapq,edge)
                while len(heapq)>0:
                    edge = heappop(heapq)
                    tonode = edge.to
                    if tonode not in set1:
                        set1.add(tonode)
                        res1.add(edge)
                        for nextedge in tonode.edges:
                            heappush(heapq,nextedge)
        return res1

     

    展开全文
  • Prim算法(Python实现)

    千次阅读 2020-10-16 01:17:01
    Prim算法是图论中的一种算法,可在加权连通图里搜索最小生成树。 算法描述 输入:一个加权连通图,顶点集合为V,边集合为E 初始化:Vnew={x},其中x是V中任一节点,作为起始点,Enew={} 在E中选择权重最小的边(u,v)...

    Prim算法是图论中的一种算法,可在加权连通图里搜索最小生成树

    算法描述

    1. 输入:一个加权连通图,顶点集合为V,边集合为E
    2. 初始化:Vnew={x},其中x是V中任一节点,作为起始点,Enew={}
    3. 在E中选择权重最小的边(u,v),其中u为集合Vnew中的元素,而v则是V中没有加入Vnew的顶点(如果权重相同就任选一个)
    4. 将v加入集合Vnew中,将(u,v)加入集合Enew中
    5. 重复步骤3-4,知道Vnew=V
    6. 输出:使用Enew和Vnew描述得到的最小生成树

    对于使用堆和邻接表表示最小权边和图的情况,时间复杂度为 O ( ( ∣ V ∣ + ∣ E ∣ ) log ⁡ ∣ V ∣ ) = O ( ∣ E ∣ log ⁡ ∣ V ∣ ) {\displaystyle O((|V|+|E|)\log |V|)=O(|E|\log |V|)} O((V+E)logV)=O(ElogV)

    算法示例

    在这里插入图片描述
    在这里插入图片描述

    代码实现

    对于图:
    在这里插入图片描述

    from collections import defaultdict
    from heapq import *
    
    def prim(vertexs, edges,start='D'):
        adjacent_dict = defaultdict(list) # 注意:defaultdict(list)必须以list做为变量
        for weight,v1, v2 in edges:
            adjacent_dict[v1].append((weight, v1, v2))
            adjacent_dict[v2].append((weight, v2, v1))
        '''
        经过上述操作,将图转化为以下邻接表形式:
        {'A': [(7, 'A', 'B'), (5, 'A', 'D')], 
         'C': [(8, 'C', 'B'), (5, 'C', 'E')], 
         'B': [(7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E')], 
         'E': [(7, 'E', 'B'), (5, 'E', 'C'), (15, 'E', 'D'), (8, 'E', 'F'), (9, 'E', 'G')], 
         'D': [(5, 'D', 'A'), (9, 'D', 'B'), (15, 'D', 'E'), (6, 'D', 'F')], 
         'G': [(9, 'G', 'E'), (11, 'G', 'F')], 
         'F': [(6, 'F', 'D'), (8, 'F', 'E'), (11, 'F', 'G')]})
        '''
        minu_tree = []  # 存储最小生成树结果
        visited = [start] # 存储访问过的顶点,注意指定起始点
        adjacent_vertexs_edges = adjacent_dict[start]
        heapify(adjacent_vertexs_edges) # 转化为小顶堆,便于找到权重最小的边
        while adjacent_vertexs_edges:
            weight, v1, v2 = heappop(adjacent_vertexs_edges) # 权重最小的边,并同时从堆中删除。 
            if v2 not in visited:
                visited.append(v2)  # 在used中有第一选定的点'A',上面得到了距离A点最近的点'D',举例是5。将'd'追加到used中
                minu_tree.append((weight, v1, v2))
                # 再找与d相邻的点,如果没有在heap中,则应用heappush压入堆内,以加入排序行列
                for next_edge in adjacent_dict[v2]: # 找到v2相邻的边
                    if next_edge[2] not in visited: # 如果v2还未被访问过,就加入堆中
                        heappush(adjacent_vertexs_edges, next_edge)
        return minu_tree
    
    vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
    edges = [(7, 'A', 'B'),
             (5, 'A', 'D'),
             (8, 'B', 'C'),
             (9, 'B', 'D'),
             (7, 'B', 'E'),
             (5, 'C', 'E'),
             (15, 'D', 'E'),
             (6, 'D', 'F'),
             (8, 'E', 'F'),
             (9, 'E', 'G'),
             (11, 'F', 'G'),
             ]
    print(prim(vertices, edges ,start='D'))
    

    输出为:

    [(5, 'D', 'A'), (6, 'D', 'F'), (7, 'A', 'B'), (7, 'B', 'E'), (5, 'E', 'C'), (9, 'E', 'G')]
    
    展开全文
  • 最小生成树--Prim算法Python

    千次阅读 2019-03-29 16:21:11
    1、Prim算法原理   Prim算法在找当前最近顶点时使用到了贪婪算法。Prim算法从任意一个顶点开始,每次选择一个与当前顶点集最近的一个顶点,并将两顶点之间的边加入到树T中,直到当前顶点集顶点个数为n或者树T中边...

    1、Prim算法原理
      Prim算法在找当前最近顶点时使用到了贪婪算法。Prim算法从任意一个顶点开始,每次选择一个与当前顶点集最近的一个顶点,并将两顶点之间的边加入到树中,直到当前顶点集顶点个数为n或者树中边数为n-1。
    2、实战演练
      下面给出一个无向图G=(VE,我们使用Prim算法来找它的最小生成树。
      第一步,我们先随意选择一个顶点作为起始点(起始点的选取不会影响最小生成树结果),在此我们一般选择v1作为起始点,现在我们设当前所找到最小生成树里面的顶点为集合V’,所找到的边为集合E’。初始状态如下:V’={v1}; E’={}
    在这里插入图片描述

      第二步,查找顶点在V’ ={v1},V-V’ 集合中的最小权值,如下图,在红线相交的线上找最小值。通过图中我们可以看到边(v1,v8)的权值最小为2,那么将v8加入到V’,边(v1,v8)加入到 E’。 此时状态如下:V’={v1,v8}; E’={(v1,v8)}。
    在这里插入图片描述
      第三步,查找顶点在V’={v1,v8},V-V’ 集合中的最小权值,如下图,在红线相交的线上找最小值。通过图中我们可以看到边(v8,v9)的权值最小为4,那么将v9加入到V’,边(v8,v9)加入到 E’。 此时状态如下:V’ ={v1,v8,v9}; E’={(v1,v8),(v8,v9)}。
    在这里插入图片描述
      第四步,查找顶点在V’ ={v1,v8,v9},V-V’ 集合中的最小权值,如下图,在红线相交的线上找最小值。通过图中我们可以看到边(v9,v2)的权值最小为1,那么将v2加入到V’,边(v9,v2)加入到 E’。 此时状态如下:V’={v1,v8,v9,v2}; E’={(v1,v8),(v8,v9),(v9,v2)}。
    在这里插入图片描述
      以此类推,直到找到所有顶点为止,最后得到无向图G的最小生成树MST=(V’E’,如下图所示:
    在这里插入图片描述
    3、Python实现

    #Prim algorithm(python)
    from collections import defaultdict
    from heapq import heapify, heappush, heappop
    import time
    start = time.perf_counter()
    def Prim(nodes, edges):
        '''  基于最小堆实现的Prim算法  '''
        element = defaultdict(list)
        for start, stop, weight in edges:
            element[start].append((weight, start, stop))
            element[stop].append((weight, stop, start))
        all_nodes = set(nodes)
        used_nodes = set(nodes[0])
        usable_edges = element[nodes[0]][:]
        heapify(usable_edges)
        # 建立最小堆
        MST = []
        while usable_edges and (all_nodes - used_nodes):
            weight, start, stop = heappop(usable_edges)
            if stop not in used_nodes:
                used_nodes.add(stop)
                MST.append((start, stop, weight))
                for member in element[stop]:
                    if member[2] not in used_nodes:
                        heappush(usable_edges, member)
    
        return MST
    
    def main():
        nodes = list('123456789')
        edges = [("1", "2", 5), ("1", "3",13),("1", "4",12), ("1", "5",10),
                       ("1", "6", 8), ("1", "7", 6),("1", "8", 2), ("1", "9", 5),
                       ("2", "3", 3), ("2", "9", 1),("3", "4", 9), ("4", "5",11),
                       ("5", "6", 9), ("6", "7", 6),("7", "8", 7), ("8", "9", 4)]
        print("\n\nThe undirected graph is :", edges)
        print("\n\nThe minimum spanning tree by Prim is : ")
        print(Prim(nodes, edges))
    
    if __name__ == '__main__':
        main()
    end = time.perf_counter()
    print('Running time: %f seconds'%(end-start))
    
    
    展开全文
  • python实现prim 最小生成树算法 源码
  • 主要为大家详细介绍了python最小生成树kruskal与prim算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 随机prim算法全解python实现 目录 概述 算法流程 数据组织 代码实现 额外想法 0.概述 随机prim算法是一种较为通用的迷宫生成算法,网上的教学也蛮成熟的,这里就目前的学习需要写一篇文章帮助需要找资料的小伙伴...

    随机prim算法全解python实现

    目录

    概述

    算法流程

    数据组织

    代码实现

    额外想法


    0.概述

    随机prim算法是一种较为通用的迷宫生成算法,网上的教学也蛮成熟的,这里就目前的学习需要写一篇文章帮助需要找资料的小伙伴提供一个参考。

    参考蛮多的,但是很少有人把整个具体的方案提出来,这里会根据具体需求用到算法上去。那第一部分就是算法的概要,接着是设计的一些观念,你可以参照目录看看你需要什么。

    1.算法流程

    先大概阐述一下随机prim算法的流程。

    首先,你需要把一个n*n的地图初始化。初始化的方法是将整个迷宫变为田字格的形式具体你可以参照下图。
    0     1     0     1     0
    1     1     1     1     1
    0     1     0     1     0
    1     1     1     1     1
    0     1     0     1     0
    实现起来还是很简单的,只需要让矩阵的行和列中出现奇数的点位标记为墙就好了。但需要注意的是,这样做的弊端就是你的矩阵行列最大值必须是奇数,你也可以通过设置保护方法来转换设置为偶数时的情况。但我们最好将这个矩阵设置为全奇数规格,这样初始化后是很标准田字格,然后坐标超出规格的都认为是外墙因为我们需要这个迷宫为全封闭的。

    先了解几个概念,

    1:seeker当前查找的单元格,我们将seeker访问到的单元格附近的有效墙添加至墙每当我们需要添加墙了就要找seeker的坐标,而墙体变动的时候seeker也可能会跟着变动,至于seeker如何变动,我们待会再聊。

    2:可访问的单元格分为2种状态,分别是被访问和未被访问,你可能需要两种状态位去标记。

    3:墙状态被分为3种,分别是:打破的墙、还存在的墙、无效墙。这样给你分类的原因是,有一种情况可能导致循环无限添加墙而无法退出,原因是,当一面墙连通2个已访问单元格的时候,我们需要墙存在而不是打破它,但如果这面墙和还存在的墙为同一标签,它就会被无限添加,这种连通2歌已访问单元格的墙我们称他为无效墙,后面我们会遇到这>为同一种类型,这个不会有什么影响。

    以上就是本文涉及的3种独立的概念。接下来是算法的流程:
    流程1:我们将seeker初始化,至于初始化为什么点都是无所谓的,默认可以是第一个点(0,0)。
    流程2:将seeker附近的墙添加至墙列表。
    流程3:从墙列表中随机选择一个墙进行判断,如果是无效墙则标记一下然后从列表中删除该墙。如果是有效墙,则把他打通,同时把那个未被访问单元格标记为已访问然后标记为seeker的位置。
    流程4:返回过程2.
    流程5:当墙列表为空的时候程序结束。

    具体的流程可以参照下图(好丑啊):

    Created with Raphaël 2.2.0 开始框 初始化迷宫、seeker、墙列表 将seeker附近的墙添加至墙列表 墙列表是否为空 随机从墙列表选择一个墙 该墙是或否为无效墙 从墙列表中删除墙 (其余不做如何操作) 结束框 打通该墙并且将未访问的那一侧修 改为已访问且为新的seeker位置。 将seeker附近的墙添加至墙列表 yes no yes no

    2.数据组织

    在写程序之前,我们需要先规划好底层数据格式,虽然在本文看不出这个模块的重要性,但是在使用这个算法的时候,我遇到的绝大部分讨厌的问题就是因为底层的东西没有规划好,到后面突然想加一个有趣的功能导致对接困难,所以我们在一开始尽可能的把数据封装好。

    第一点:迷宫数据选取。本文选择的数据结构是Pythonh扩展包numpy的ndarray类型数组对象。

    第二点:标记选择。

    0:未访问路径.
    1:未访问墙.
    2:已访问后标记的路径,包括墙,墙在被打破后也属于可行进路径.
    3:已访问但不打破的墙.(无效墙)

    第三定:迷宫类方法:

    属性:

    ​     迷宫的本体矩阵

    ​     大小参数(用于初始化迷宫等)

    ​     seeker

    ​     墙列表


    方法:

    1:初始化迷宫

    2:将一个seeker周围所有墙插入墙列表

    3:摧毁墙

    4:生成迷宫(需要用到2和3)

    5:返回迷宫矩阵(因为用了类)

    3:实现代码

    import numpy as np
    import random
    
    class PrimMaze():
        def __init__(self):
            self.image = np.array([])  # 类型备份,因为后面我需要迷宫成2值状态
            self.size = (15, 15)
            self.maze = self.initmaze()  # 初始化
            self.size = np.shape(self.maze)
            self.seeker = self.initseeker()
            self._walls = []    # 墙列表
            self.createmaze()   # 生成迷宫
    
        # 初始化规格
        def initmaze(self):
    在这里插入图片描述
            x, y = self.size
            maze = np.zeros(self.size)
            for i in range(x):
                for j in range(y):
                    if i % 2 == 1 or j % 2 == 1:
                        maze[i, j] = 1
            return maze
    
        # 初始化seeker
        def initseeker(self):在这里插入图片描述
            self.maze[0, 0] = 2
            return (0, 0)
    
        # 将墙插入列表
        def insertwall(self):
            size = np.shape(self.maze)
    
            if self.seeker[0] + 1 < size[0] and self.maze[self.seeker[0] + 1, self.seeker[1]] == 1:
                self._walls.append((self.seeker[0] + 1, self.seeker[1]))
            if self.seeker[0] - 1 > 0 and self.maze[self.seeker[0] - 1, self.seeker[1]] == 1:
                self._walls.append((self.seeker[0] - 1, self.seeker[1]))
            if self.seeker[1] + 1 < size[1] and self.maze[self.seeker[0], self.seeker[1] + 1] == 1:
                self._walls.append((self.seeker[0], self.seeker[1] + 1))
            if self.seeker[1] - 1 > 0 and self.maze[self.seeker[0], self.seeker[1] - 1] == 1:
                self._walls.append((self.seeker[0], self.seeker[1] - 1))
            self._walls = list(set(self._walls))
    
        # 摧毁墙
        def destroywall(self, wall):
            x = wall[0]
            y = wall[1]
    
            # 纵墙
            if wall[0] % 2 == 1:
                # 上边和下边都访问过,无效墙
                if self.maze[x - 1, y] == 2 and self.maze[x + 1, y] == 2:
                    self.maze[x, y] = 3
                    return True
                # 穿透
                else:
                    self.maze[x, y] = 2
                    if self.maze[x - 1, y] == 2:
                        self.maze[x + 1, y] = 2
                        self.seeker = (x + 12.数据组织</span>, y)
                        return True
                    elif self.maze[x + 1, y] == 2:
                        self.maze[x - 1, y] = 2
                        self.seeker = (x - 1, y)
                        return True
            # 横墙
            if wall[1] % 2 == 1:
                # 左边和右边都访问过,无效墙
                if self.maze[x, y - 1] == 2 and self.maze[x, y + 1] == 2:
                    self.maze[x, y] = 3
                    return True
                # 穿透
                else:
                    self.maze[x, y] = 2
                    if self.maze[x, y - 1] == 2:
                        self.maze[x, y + 1] = 2
                        self.seeker = (x, y + 1)
                        return True
                    elif self.maze[x, y + 1] == 2:
                        self.maze[x, y - 1] = 2
                        self.seeker = (x, y - 1)
                        return True
            print(wall, "invalid wall , can not destroy!")
            return False
    
        # 将迷宫初始化,
        def createmaze(self):在这里插入图片描述
            while True:
                self.insertwall()
                temp = self._walls.pop(random.randint(0, np.shape(self._walls)[0] - 1))
                self.destroywall(temp)
                if self._walls == []:
                    break
    
        # 返回迷宫序列
        def displaymaze(self):
            return self.maze
    

    说明:如果你需要使用这串代码,你只需要创建这个类对象,然后使用返回迷宫序列的方法也就是displaymaze(),该方法会返回一个ndarray对象,这个矩阵就是迷宫本身。实际使用的效果图如下(第一个是拿到矩阵后用pygame画的,你可以用方向键实实在在移动的哦):


    说明:上图是pygameu做的小界面,将就看一下吧,下图是一个5*5的迷宫矩阵,是一个ndarray数组。你拿到数组的时候可以直接使用,比如像上图一样绘图?可呢?

    4.额外的想法

    这一部分是关于这个算法的一些想法和问题,第一点就是我在上面忽略了一开始想到但是忘记了的细节,就是关于无效墙的处理,如果加入seeker点变动才添加墙的话,就能成功避免无效墙需要额外标记的问题,但是额外标记其实也没什么大问题,所以就没在写这篇博客的时候改。其次,这个算法在某些角度上去看效率是很低的,你永远最多只能一次添加3面墙,有的时候只能添加1面墙,这对于遍历整个矩阵有相当大的阻碍作用,所以你若能有幸需要做超大迷宫设计,这个算法还是有超多优化空间的,但这里就先不提了。

    关于一些游戏性的问题:如果你对迷宫的趣味行问题感兴趣那不妨看看这个部分。首先是多维迷宫的构建,我想到了一个很有趣的构建机制,就是将大小不一的各种迷宫堆叠再选取相同的点进行允许通过,这样就能从一个迷宫到达另一个迷宫,这里指的不是纯粹的三位迷宫,纯粹的三位迷宫也可以使用上述算法直接得出,这里指的是更像关卡类的设计,同时该算法生成的是完美迷宫,也就是迷宫内部i不存咋闭环,那么如果我么能够在迷宫里设计闭环且让另一个迷宫能够通向这个闭环就能够达成更有趣的迷宫设计(虽然我知道没人会闲着没事干玩迷宫)。甚至在迷宫游戏中加入更多的收集要素。后面如果我真的闲着无聊,有可能会对这些想法进行实现。

    展开全文
  • 【模板】最小生成树 prim算法 https://www.luogu.com.cn/problem/P3366 这道题目主要是考验我们对prim算法的熟练程度,prim算法的主要思想就是找一个起始点,就是一直寻找一个最小边,当添加了M-1条边后停止添加,然后...
  • Prim算法Python实现

    千次阅读 2018-03-25 12:50:40
    话不投机半句多。 代码一一如下。... Prim algorithm import sys # 同样的,这里也是为了引入无穷大 graphMatrix = [[0, 54, 32, 7, 50, 60], [54, 0, 21, 58, 76, 69], [32, 21, 0, 35, 67, 66], [7, 58...
  • 最小生成树prim算法python实现

    千次阅读 2018-05-29 20:58:52
    from collections import defaultdict from heapq import heapify, heappush, heappop def Prim(nodes, edges)... ''' 基于最小堆实现的Prim算法 ''' element = defaultdict(list) for start, stop, weight in e...
  • 文章目录库的版本号最小生成树的知识点PRIM算法Kruskal算法 库的版本号 列了这个是因为在学习过程中,会有很多文章,可能时间稍微久点了,用起来因为版本迭代,函数可能发生了变化,但你也不确实到底是什么问题。。...
  • Python 实现Prim最小生成树算法

    千次阅读 2018-07-31 22:34:16
    Prim算法:假设N=(V,E) 是具有n个顶点的连通图,设U是最小生成树中顶点的集合,设TE是最小生成树中边的集合;  初始,U = { u1 } ,TE = { } ,  重复执行: 在所有 u∈U,v∈V-U 的边 ( u , v...
  • prim算法(最小生成树) python实现

    千次阅读 2018-11-23 16:20:14
    prim算法和dijkstra算法基本思路一模一样,都是贪婪。都是从costs边数组里面找最短边,把这个最短边的结点加入t(已经确定好最短边的点)中。然后再遍历这个结点的邻边,更新costs。 但是prim和dijkstra的区别在哪里呢...
  • 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索得到最小生成树。最小生成树即在一个带权连通图中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。 算法思路 利用字典建立图 以...
  • Prim算法求解无向连通图的最小生成树: 输入的图如下所示: 期望得到的结果: 输入例子如下所示: 6 10 0 1 7 0 2 4 0 3 3 0 5 7 1 3 6 1 4 5 1 5 2 2 3 8 2 4 5 3 4 1 代码如下: VexNumber...
  • Python实现最小生成树(Prim算法

    万次阅读 2019-04-27 11:04:06
    使用链表构建图,利用递归、栈实现Prim算法求取最小生成树。 或许实现的结果与最小生成树的定义有区别,下面代码的结果是:穷举所有的节点,获取从任何顶点出发的一条最小权重的路径。(此代码是博主自己实现,可能...
  • |-带权图:用python内置数据类型dict存储带权图的边 |-最小生成树问题和切分定理 最小生成树:对于一个完全连通的具有v个结点的无向带权图,找到v-1条边使v个... prim算法的第一个实现:Lazy Prim 时间复杂度O(Elog...
  • 得到的最小生成树如下: D / \ A F \ B / E / \ G C 总费用最小为39 05 — prim-python代码实现 prim的实现代码请参考github库: https://github.com/jackzhenguo/machine-learning/tree/master/basics 运行以上代码...
  • def prim(graph, vertex_num): INF = 1 &lt;&lt; 10 visit = [False] * vertex_num dist = [INF] * vertex_num #preIndex = [0] * vertex_num #对所有的顶点进行循环,首先是确定头结点 #找到当前无向...
  • 离散大作业 最小生成树算法 一Prim算法 设G=(V,E)是连通带权图V={1,2,n}构造G的最小生成树的Prim算法的基本思想是 (1)置S={1} (2)只要S是V的真子集就作如下的贪心选择 选取满足条件i Sj V-S且c[i][j]最小的边将顶点j...
  • 算法涉及到在互联网中网游设计者和网络收音机所面临的问题:信息广播问题,如网游需要让所有玩家获知其他玩家所在的位置,收音机则需要让所有听众获取直播的音频数据 2、算法介绍 (1)单播解法 信息广播问题最...
  • 本代码由本人根据概念自行完成 稳定性与效率未得到验证1.prim算法实现较kruskal简单关键为点的结合与连线顺序2.转载附原作者Id及作品链接原代码如下:importsysMAX=sys.maxsizegraph=[[MAX,10,MAX,MAX,MAX,11,MAX,...
  • 2.prim算法–加点法 算法过程: 将所有节点划分为两类:selected_node和candidate_node 1)任取一节点加入selected_node,遍历头结点在selected_node,尾节点在candidate_node的边,选取符合条件的权重最小的边,...
  • Prim算法python实现

    2021-03-07 11:22:48
    #Prim算法python实现 介绍:首先prim算法我使用的是与Dijkstra实现一致的方式方法,代码部分甚至不需要过多地修改就可以直接拿函数去使用. def prim(matrix,non_matrix,n,Maxline): comp={0} uncomp={i+1 for i ...
  • 恋情申道友优先肯prim算法随机生成迷宫,有自动寻路功能,做了界面,需要easyX库的支持
  • Python附代码)Prim算法最小生成树(贪心算法) 一、问题描述 【问题描述】Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。 【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。 ...
  • Python实现最小生成树--Prim算法和Kruskal算法

    千次阅读 热门讨论 2020-06-21 21:01:22
    Python实现最小生成树–Prim算法和Kruskal算法 文章目录Python实现最小生成树--Prim算法和Kruskal算法前言设计需求分析系统设计系统实现Prim算法Kruskal算法功能介绍测试数据及代码测试数据完整代码参考文章 前言 ...
  • 学习《算法分析与设计》这门课,实验中设计到Prim算法要求实验Python实现,写文章进行记录。如我的代码有错误,欢迎大家指出,如过您有更好的建议,期待和您交流! 1、用到的Python库 import math from queue import...
  • 本代码利用c#语言,实现了基于Prim算法实现最小生成树的可视化界面。用户可以自己输入点以及边的权值,计算出最小生成树。
  • 普利姆算法Prim -python

    2019-10-15 11:38:13
    求最小生成树的算法,贪心算法 在包含n个顶点的连通图中,找出只有n-1条边包含所有n个顶点的连通子图,就是极小连通图 场景:n个顶点连通的最短路径 2 算法原理 无向图的最小生成树算法,结果生成最小生成树 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,545
精华内容 618
关键字:

prim算法python

python 订阅