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())

初始的图如下。

运行结果如下。

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

时间: 2019-01-15

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决策树之C4.5算法详解

本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下 1. C4.5算法简介   C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化.C4.5算法对ID3算法主要做了一下几点改进:   (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足:   (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理:   (3)构造决策树之后进行剪枝操作:   (4)能够处理具有缺失属性值的训练数据. 2

Python机器学习之K-Means聚类实现详解

本文为大家分享了Python机器学习之K-Means聚类的实现代码,供大家参考,具体内容如下 1.K-Means聚类原理 K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大.其基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类.通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果.各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开. 算法大致流程为:(1)随机选取k个点作为种子点(这k个点不一定属于数据集)

python算法演练_One Rule 算法(详解)

这样某一个特征只有0和1两种取值,数据集有三个类别.当取0的时候,假如类别A有20个这样的个体,类别B有60个这样的个体,类别C有20个这样的个体.所以,这个特征为0时,最有可能的是类别B,但是,还是有40个个体不在B类别中,所以,将这个特征为0分到类别B中的错误率是40%.然后,将所有的特征统计完,计算所有的特征错误率,再选择错误率最低的特征作为唯一的分类准则--这就是OneR. 现在用代码来实现算法. # OneR算法实现 import numpy as np from sklearn.da

C++使用Kruskal和Prim算法实现最小生成树

很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易.最近学习了并查集算法,得知并查集可以用于实现上述两个算法后,我自己动手实现了最小生成树算法. 宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构--优先级队列,用于动态排序.由于这两个算法很容易理解,在此不再赘述.接下来给出我的源代码. 输入 第一行包含两个整数n和m,n表示图中结点个数,m表示图中边的条数:接下来m行,每一行

Python做简单的字符串匹配详解

Python做简单的字符串匹配详解 由于需要在半结构化的文本数据中提取一些特定格式的字段.数据辅助挖掘分析工作,以往都是使用Matlab工具进行结构化数据处理的建模,matlab擅长矩阵处理.结构化数据的计算,Python具有与matlab共同的特点:语法简洁.库丰富,对算法仿真来说都是一门简洁易用的语言. Python做字符串匹配相对来说上手比较容易,且具有成熟的字符串处理库re供我们使用: 在re库的帮助下,只需简单的两步就可完成匹配工作,对做数据分析/算法的工作者来说,轻松了许多: ste

python实现图片处理和特征提取详解

这是一张灵异事件图...开个玩笑,这就是一张普通的图片. 毫无疑问,上面的那副图画看起来像一幅电脑背景图片.这些都归功于我的妹妹,她能够将一些看上去奇怪的东西变得十分吸引眼球.然而,我们生活在数字图片的年代,我们也很少去想这些图片是在怎么存储在存储器上的或者去想这些图片是如何通过各种变化生成的. 在这篇文章中,我将带着你了解一些基本的图片特征处理.data massaging 依然是一样的:特征提取,但是这里我们还需要对跟多的密集数据进行处理,但同时数据清理是在数据库.表.文本等中进行.这是如何