Kruskal算法工程应用的改进方法及实现

摘要

Ｋｒｕｓｋａｌ算法的优越性在于把连通图处理成“最小生成树”时的全局性。这一点在工程上很重要。但对于连通图中存在权值相等的支路时却不适用。本文提出并通过用“权相等支路排序”和“结点集合”法解决此问题的思路及应用方法。结果表明，此方法具有概念清楚，简便易行的特点。可以在整体上解决某网络图的方案选择的工程问题。