您的位置： 文档网所有分类IT/计算机计算机软件及应用 最小生成树算法(一)

最小生成树算法(一)

最小生成树算法(一) 包含了最小生成树的原理、相关证明和Prim算法的C实现

最小生成树算法及C语言实现（一）

本文主要讲述最小生成树的概念和相应的算法原理和证明，包含了Prim算法的C实现，其它实现方式会在“最小生成树算法及C语言实现（二）”中讲到。

最小生成树（Minimum Spanning Tree, MST）对于有向图也是有意义的，但那比较难，下文只讨论无向图的情况。

简单地说，生成树就是使用原来图上的所有或者部分边把图上所有点相连的树。

简单地说，最小生成树就是使用原来图上的所有或者部分边并通过最少的总路径把图上所有点相连（可以间接相连）得到的树。

定理：

生成树存在当且仅当图是连通的。

证明：

如果图不是连通的，则显然不存在最小生成树。对于一个连通的图来说，如果它已经是树，则本身即是一棵生成树，如果它的某部分形成了环，则把相应的环去掉，则可以得到一颗生成树。

定理：

最小生成数存在当且仅当图是连通的。

证明：

由上面的定理可以直接得到。

定理：

一个N个顶点的图的最小生成树的边的数量为N-1。

证明：

最小生成树没有环，所以是一棵树，对于一棵树而言，我们可以选定一个根结点，那么，除了根结点外，其它结点有且仅有一条边连向它的父结点，所以共N-1条边。

同样，为了简单起见，下文假设图是连通的。以下的两个经典算法都是通过贪心算法的原理实现的。贪心算法对于MST是成立的，这在下面会证明。

1.Prim 算法

Prim算法的步骤非常简单：

1.选择任意一个顶点为根，并把它做为一棵树。

2.在任意状态下，选择在树上的一点和不在树上的一点构成的边中最短的一条边使树得以伸长。

定理：

Prim算法可以用于产生MST。

证明：设G是一个连通的具有n个顶点的有权图。我们知道Prim算法最终会生成一棵n个顶点的树（由上述过程，是不会生成环的，因为形成环必然要连接已经在树上的两个结点），不妨记N-1条边为E1,E2,E3,...,En-1，其中序号沿着树生成时的每条边产生的序号。我们再记Sk为E1,E2,E3,...,EK（k是一个变量，可以进行取值）构成的树。我们再记一棵和S最相接近的最小生成树T（即两者包含的边尽量一致），它包含了E1,E2,E3,...,EK这几条Sk的边（如

第1页

你可能喜欢

  • 最小生成树算法实现
  • 算法合集
  • 数据结构实验报告
  • 最短路径算法
  • 设计问题
  • 道路设计
  • 路线优化
  • 拓扑排序算法

最小生成树算法(一)的相关文档搜索

最小生成树算法(一)相关文档

最新文档

返回顶部