【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree

81 阅读 0 评论 54 点赞

我是靠谱客的博主想人陪美女，最近开发中收集的这篇文章主要介绍【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

最小生成树 Minimum Spanning Tree
- 1. 概念
- 2. 计算
- - 2.1 生成树
  - 2.2 经典的最小生成树算法
  - - Kruskal算法 - 从边的角度出发
    - Prim算法 - 从顶点的角度出发
- 3. 与最短路径的关系

最小生成树 Minimum Spanning Tree

1. 概念

一个连通图的生成树是一个极小的连通子图，即包含了全部结点以及连通的最少边数（n-1条）。

最小生成树指带权图的边权值之和最小的生成树。

2. 计算

2.1 生成树

n个结点的无向完全图有多少个生成树： $n^{n-2}$ （prufer编码与cayley公式）

注：prufer是有编号无根树的一种编码方式，一颗无根树与一个prufer编码唯一对应。n结点的无向完全图对应的prufer数列长度为n-2，数列中每个数的取值为[1,n]，可重复，因此n个结点可构成 $n^{n-2}$ 个prufer数列，即n个结点可构成 $n^{n-2}$ 个生成树。

在这里插入图片描述

2.2 经典的最小生成树算法

Kruskal算法 - 从边的角度出发

在这里插入图片描述

Prim算法 - 从顶点的角度出发

在这里插入图片描述

3. 与最短路径的关系

最短路径是找到起始点到终点的最短距离，仅包含必须要经过的点。而最小生成树需要包含所有结点
求最短路径的经典算法dijkstra也是基于贪心策略，算法流程跟prim算法非常相似

最后

以上就是想人陪美女为你收集整理的【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree的全部内容，希望文章能够帮你解决【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：算法
浏览次数：81 次浏览
发布日期：2023-11-02 13:31:05
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_18_f4_14__23__14_4.html

【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree

概述

文章目录

最小生成树 Minimum Spanning Tree

1. 概念

2. 计算

2.1 生成树

2.2 经典的最小生成树算法

Kruskal算法 - 从边的角度出发

Prim算法 - 从顶点的角度出发

3. 与最短路径的关系

最后

评论列表共有 0 条评论

发表评论取消回复

【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree

概述

文章目录

最小生成树 Minimum Spanning Tree

1. 概念

2. 计算

2.1 生成树

2.2 经典的最小生成树算法

Kruskal算法 - 从边的角度出发

Prim算法 - 从顶点的角度出发

3. 与最短路径的关系

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复