基于快速排序改进的Kruskal方法

本发明公开了一种基于快速排序改进的Kruskal方法；属于计算机应用领域，其操作步骤如下：步骤(1)：准备一个空集合S、空线性表L；步骤(2)：将图中的边存入线性表L，以L为参数启动执行quickKruskal(list)；步骤(3)：执行quickKruskal(list)操作；步骤(4)：返回集合S，其中的边构成图的一棵最小生成树。本发明涉及图(graph)的最小生成树(MST)算法；最小生成树，是图论中的一个经典问题，算法的相关研究具有理论和实际应用价值；本发明相较于经典的Kruskal算法和Prim算法，将判断边“是否构成回路”这一操作，融入快速排序之中，以减少排序的开销，新方法的理论效率高、执行速度快；特别是当“边多点少”时，执行速度显著提高。