- -
- -
最
小
生
成
树
- -
- -
最小生成树问题
摘要：本文通过对最小生成树两种算法〔Kruskal算法和Prim算法〕的分析，用C语言写出了Kruskal算法的C语言源程序，通过计算机实现求一个连通图的最小生成树问题。
关键词：最小生成树 Kruskal算法 Prim算法 C语言源程序
- -
- -
- -
- -
引言
现实中一些实际应用问题可通过利用连通图、生成树的模型来建立求解，找出最优的方法，而在任意一个连通图中存在许多条生成树，如何从这些生成树中找出一条权最小的生成树对解决现实生活中实际应用问题具有重大意义，所以经过数学家的研究，目前最小生成树的算法主要有Kruskal算法和Prim算法，那么对这两种方法在计算机上的实现也关系着效率的提高，两种算法的C语言程序也应运而出。
- -
- -
正文
对最小生成树问题中的认识:
G(V，E)是一个树，假设p(G)≧2，那么G中至少有两个悬挂点。
树G(V，E)中不相邻的两个点间添上一条边，那么得到只含一个圈的图G'；假设在图G'中从该圈中再去掉任意一条边得到图G"，那么图G"又成为树。
最小生成树的算法：
Kruskal算法〔避圈法〕：
Ⅰ 令i=1，E0=Φ(空集)
最小生成树论文 来自淘豆网m.daumloan.com转载请标明出处.
