摘要
提出一种关于最小生成树的生成法 ,此方法是在一个给定的网络中 ,首先找到一条权最大的边 ,判断此边的 2个结点在不经过此边的情况下是否有另路相通 ,若相通则删除此边 .否则 ,保留此边 ,再寻找所剩余的权最大的边 ,作类似的处理 ,直到在原网络中剩下的边为顶点数减 1为止 ,由此即得最小生成树 .与传统的Prim算法及Kruskal算法相比较 ,此法在点多而边数相对较少的网络中 ,能迅速地找到它的最小生成树 .
Compared with the traditional algorithms of Prim and Kruskal,the new algorithm introduced in this paper has its own advantage.In the given network, find the edge of the maximal power and determine whether there is another access which connects the two vertices of the edge , if there is, delete the edge, or remain it.Search for the edge of the maximal power in the rest edges and deal with it similarly.Repeat this procedure until the amount of edges in the network is equal to that of the vertices minus one.By this way the minimal tree is produced
