秒懂算法 | Kruskal算法

Python实战Kruskal算法。

01

数据结构选择

图的边集采用Python语言中的list，其中每个元素是一条边，用一个三元组(顶点1，顶点2，边权)表示。最小生成树T和标记顶点分支的数据结构group均采用list。

02

编码实现

定义一个 kruskal函数，接收图的顶点集vertexs和边集edge_list，返回最小生成树tree_mst。其代码如下：

定义Python入口——main函数，在main函数中，初始化图的数据结构，三元组结构为(顶点1,顶点2,边权)，将图中所有边的三元组组成一个edge_list；初始化顶点集vertexs；调用kruskal函数生成最小生成树；最后打印输出。其代码如下：

输出结果为

(1, 3, 1)

(4, 6, 2)

(2, 5, 3)

(3, 6, 4)

(2, 3, 5)

实例讲解

算法设计与分析（Python版）

精彩回顾

秒懂算法

算法设计的一般过程

递推方程求解方法

活动安排问题贪心算法

哈夫曼编码贪心算法

Prim算法

下期预告

秒懂算法

选第二大元素的分治算法

快速排序算法中的分治思想

动态规划算法的基本思想

矩阵连乘问题

0-1背包问题的动态规划改进算法——跳跃点算法

子集树模型——0-1背包问题的回溯算法

满m叉树模型——图的m可着色问题的回溯算法

排列树模型——旅行商问题的分支限界法

最大网络流的增广路算法

蒙特卡罗算法

02

参考书籍

《算法设计与分析》

作者：王秋芬

定价：59.90元

03

精彩推荐

• 微信小程序游戏开发│猜数字小游戏（附源码+视频）

• Flink编程基础│Scala编程初级实践

• Flink编程基础│FlinkCEP编程实践

• Flink编程基础│DataStream API编程实践

• Flink编程基础│DataSet API编程实践

• 数 据分析实战│客户价值分析

• 数据分析实战│价格预测挑战

• 数据分析实战│时间序列预测

• 数据分析实战│KaggleTitanic生存预测

九七分享吧所有文章来源于网络收集整理，如有侵权请联系QQ2387153712删除，如果这篇文章对你有帮助或者还不错的请给小编点个小赞(◠‿◠)，小编每天整理文章不容易(ಥ_ಥ)！！！