毕业论文初稿(4)

最小生成树

摘要

首先，我们知道最小生成树的定义。最小生成树，一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。即在一给定的无向图G=（V,E）中，（u，v）代表连接顶点u与顶点v的边，而w（u，v）代表此边的权重，若存在T为E的子集且为无循环图，使得w（T）最小，则此T为G的最小生成树 。构造最小生成树可以有多种算法，它在我们日常生活中的应用也有很多， 所以我们研究并且改进最小生成树就显得很有必要，也很值得期待。

关键字：最小生成树 算法 应用 改进

以下是求解最小生成树的一般算法流程：GENERIC-MST(G,W) 1，A->P

2，while A没有形成一棵生成树

3，do 找出A的一条安全边（u，v）

4，A->A并{（u,v）}