毕业论文初稿(6)

最小生成树

目前，求最小生成树的算法已经非常成熟。平时用的算法有Kruskal算法（也叫避圈法）、Prim算法（也称边割法）、破圈法，但这三种算法需要判断圈或者构造边割。这些算法的优点是简单明了，通俗易懂；缺点是通常用来直接在图上作业；此外，还有基于Dijkstra算法的矩阵法、基于破圈法的完全关联矩阵法等；这些算法的优点是可用于求取大规模网络的最小生成树，缺点是计算过程复杂，效率低。根据最小生成树的定义及性质，想出了一种基于权矩阵的最小生成树算法。将它用来求配电网架规划中的最小生成树会使整个算法的计算效率显著提高。

1.1算法思想

设图G是一个连通的无向带权图。如果Go是一个包含G中所有顶点且无回路的连通子图，则Go是G的一棵生成树。若G有n个顶点，那么它的生成树有n个顶点，n-1条边。一个图可以有很多不同的生成树。其中，各条边权值之和最小的生成树即为最小生成树。根据最小生成树的定义及性质可以得到如下几个结论（1）G1中的各条边权值之和最小。（2）G1中有n个顶点n-1条边。（3）G1必须是连通的且无回路。

因此，只要在一个连通带权图里找到一个同时满足上述三个条件的图，也就找到了该图的最小生成树。

图G中各条边的权值已知，由此可以形成一个n×n的权矩阵A。元素Aij表示第i个顶点到第j个顶点的边的权值。规定：若顶点i与