python最小生成树kruskal与prim算法详解

kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边。

prim算法基本思路:所有节点分成两个group,一个为已经选取的selected_node(为list类型),一个为candidate_node,首先任取一个节点加入到selected_node,然后遍历头节点在selected_node,尾节点在candidate_node的边,选取符合这个条件的边里面权重最小的边,加入到最小生成树,选出的边的尾节点加入到selected_node,并从candidate_node删除。直到candidate_node中没有备选节点(这个循环条件要求所有节点都有边连接,即边数要大于等于节点数-1,循环开始前要加入这个条件判断,否则可能会有节点一直在candidate中,导致死循环)。

#coding=utf-8
class Graph(object):
  def __init__(self, maps):
    self.maps = maps
    self.nodenum = self.get_nodenum()
    self.edgenum = self.get_edgenum()

  def get_nodenum(self):
    return len(self.maps)

  def get_edgenum(self):
    count = 0
    for i in range(self.nodenum):
      for j in range(i):
        if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
          count += 1
    return count

  def kruskal(self):
    res = []
    if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
      return res
    edge_list = []
    for i in range(self.nodenum):
      for j in range(i,self.nodenum):
        if self.maps[i][j] < 9999:
          edge_list.append([i, j, self.maps[i][j]])#按[begin, end, weight]形式加入
    edge_list.sort(key=lambda a:a[2])#已经排好序的边集合

    group = [[i] for i in range(self.nodenum)]
    for edge in edge_list:
      for i in range(len(group)):
        if edge[0] in group[i]:
          m = i
        if edge[1] in group[i]:
          n = i
      if m != n:
        res.append(edge)
        group[m] = group[m] + group[n]
        group[n] = []
    return res

  def prim(self):
    res = []
    if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
      return res
    res = []
    seleted_node = [0]
    candidate_node = [i for i in range(1, self.nodenum)]

    while len(candidate_node) > 0:
      begin, end, minweight = 0, 0, 9999
      for i in seleted_node:
        for j in candidate_node:
          if self.maps[i][j] < minweight:
            minweight = self.maps[i][j]
            begin = i
            end = j
      res.append([begin, end, minweight])
      seleted_node.append(end)
      candidate_node.remove(end)
    return res

max_value = 9999
row0 = [0,7,max_value,max_value,max_value,5]
row1 = [7,0,9,max_value,3,max_value]
row2 = [max_value,9,0,6,max_value,max_value]
row3 = [max_value,max_value,6,0,8,10]
row4 = [max_value,3,max_value,8,0,4]
row5 = [5,max_value,max_value,10,4,0]
maps = [row0, row1, row2,row3, row4, row5]
graph = Graph(maps)
print('邻接矩阵为\n%s'%graph.maps)
print('节点数据为%d,边数为%d\n'%(graph.nodenum, graph.edgenum))
print('------最小生成树kruskal算法------')
print(graph.kruskal())
print('------最小生成树prim算法')
print(graph.prim())

初始的图如下。

运行结果如下。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • python最小生成树kruskal与prim算法详解

    kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边. prim算法基本思路:所有节点分成两个group,一个为已经选取的selected_node(为list类型),一个为candidate_node,首先任取一个节点加入到selected_node,然后遍历头节点在selected_node,尾节点在candidate_node的边,选取符合这个条件的边里面权重最小的边,加入到

  • Java求最小生成树的两种算法详解

    目录 1 最小生成树的概述 2 普里姆算法(Prim) 2.1 原理 2.2 案例分析 3 克鲁斯卡尔算法(Kruskal) 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 6 总结 介绍了图的最小生成树的概念,然后介绍了求最小生成树的两种算法:Prim算法和Kruskal算法的原理,最后提供了基于邻接矩阵和邻接链表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最小生成树的

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

  • python中实现k-means聚类算法详解

    算法优缺点: 优点:容易实现 缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢 使用数据类型:数值型数据 算法思想 k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的,相近的就会放到同一个类别中去. 1.首先我们需要选择一个k值,也就是我们希望把数据分成多少类,这里k值的选择对结果的影响很大,Ng的课说的选择方法有两种一种是elbow method,简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好.另一种则是根据具体的需求确定,比如说进行衬衫尺寸的聚

  • Python编程实现蚁群算法详解

    简介 蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值. 定义 各个蚂蚁在没有事先告诉

  • Python自然语言处理之切分算法详解

    一.前言 我们需要分析某句话,就必须检测该条语句中的词语. 一般来说,一句话肯定包含多个词语,它们互相重叠,具体输出哪一个由自然语言的切分算法决定.常用的切分算法有完全切分.正向最长匹配.逆向最长匹配以及双向最长匹配. 本篇博文将一一介绍这些常用的切分算法. 二.完全切分 完全切分是指,找出一段文本中的所有单词. 不考虑效率的话,完全切分算法其实非常简单.只要遍历文本中的连续序列,查询该序列是否在词典中即可.上一篇我们获取了词典的所有词语dic,这里我们直接用代码遍历某段文本,完全切分出所有的词

  • Python集成学习之Blending算法详解

    一.前言 普通机器学习:从训练数据中学习一个假设. 集成方法:试图构建一组假设并将它们组合起来,集成学习是一种机器学习范式,多个学习器被训练来解决同一个问题. 集成方法分类为: Bagging(并行训练):随机森林 Boosting(串行训练):Adaboost; GBDT; XgBoost Stacking: Blending: 或者分类为串行集成方法和并行集成方法 1.串行模型:通过基础模型之间的依赖,给错误分类样本一个较大的权重来提升模型的性能. 2.并行模型的原理:利用基础模型的独立性,

  • Python机器学习之PCA降维算法详解

    一.算法概述 主成分分析 (Principal ComponentAnalysis,PCA)是一种掌握事物主要矛盾的统计分析方法,它可以从多元事物中解析出主要影响因素,揭示事物的本质,简化复杂的问题. PCA 是最常用的一种降维方法,它的目标是通过某种线性投影,将高维的数据映射到低维的空间中,并期望在所投影的维度上数据的方差最大,以此使用较少的维度,同时保留较多原数据的维度. PCA 算法目标是求出样本数据协方差矩阵的特征值和特征向量,而协方差矩阵的特征向量的方向就是PCA需要投影的方向.使样本

  • python机器学习基础K近邻算法详解KNN

    目录 一.k-近邻算法原理及API 1.k-近邻算法原理 2.k-近邻算法API 3.k-近邻算法特点 二.k-近邻算法案例分析案例信息概述 第一部分:处理数据 1.数据量缩小 2.处理时间 3.进一步处理时间 4.提取并构造时间特征 5.删除无用特征 6.签到数量少于3次的地点,删除 7.提取目标值y 8.数据分割 第二部分:特征工程 标准化 第三部分:进行算法流程 1.算法执行 2.预测结果 3.检验效果 一.k-近邻算法原理及API 1.k-近邻算法原理 如果一个样本在特征空间中的k个最相

  • python机器学习基础特征工程算法详解

    目录 一.机器学习概述 二.数据集的构成 1.数据集存储 2.可用的数据集 3.常用数据集的结构 三.特征工程 1.字典数据特征抽取 2.文本特征抽取 3.文本特征抽取:tf-idf 4.特征预处理:归一化 5.特征预处理:标准化 6.特征预处理:缺失值处理 一.机器学习概述 机器学习是从数据中,自动分析获得规律(模型),并利用规律对未知数据进行预测. 二.数据集的构成 1.数据集存储 机器学习的历史数据通常使用csv文件存储. 不用mysql的原因: 1.文件大的话读取速度慢: 2.格式不符合

随机推荐