基于Prim算法的最小生成树优化研究

Research on minimum spanning tree based on prim algorithm

在图的最小生成树算法中,Prim和Kruskal算法分别适用于稠密图和稀疏图,但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身。由此,对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图。经实例验证,利用改进的Prim最小生成树算法,根据无向图的顶点数和顶点的度数动态确定求解最小生成树的时间,并将求解的时间复杂度最小化。

In the minimum spanning tree algorithm of graph, Prim and Kruskal algorithm are respectively applied to dense graph and sparse graph. But both cannot dynamically regulate their own capability based on peak number, edge number and edge distribution. Prim starts from the degree of the vertex and then delete some useless edges from the graph. Therefore, improvement on the Prim algo- rithm, enabling it dynamically regulates its capability, can be applied to both dense graph and sparse graph. After experiments, the method by improving on the Prim algorithm can effectively reduce the search space and have the advantage of speed and so on.