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

Improvement and realization of Kruskal arithmatic method in engineering application

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

The advantage of the Kruskal arithmatic method lies in its overall view when it is used to process the linked graph into 'the cost spanning'.This is very important in engineering practice. However it is not suitable when applied to the linked graph where a 'right equal branch 'exists. Here, a solution to this problem, and hence ,a practical method are put forward ,with the help of 'right equal branch sorting' and 'node group' methods. The results indicate that the improved method have such characteristics as clarity and simplicity .and can solve the engineering problem of project selection of an active net graph widely.