造价通
反馈
取消

热门搜词

造价通
取消 发送 反馈意见

建设工程知识

最小树形图问题解法

2022/07/16201 作者：佚名
导读：求最小树的两种方法，是避圈法与破圈法 。 最小树形图问题避圈法 从网络图中任意节点开始寻找与该节点关联的权数最小的边，使之与已选边不构成为圈，直到选够n-1条边为止。 最小树形图问题破圈法 ① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； ② 去掉该圈中权数最大的边； 反复重复 ① ② 两步，直到最小树。 最小树形图问题Kruskal 算法 将图中所有边按权值从小到大排列

求最小树的两种方法，是避圈法与破圈法 。

最小树形图问题避圈法

从网络图中任意节点开始寻找与该节点关联的权数最小的边，使之与已选边不构成为圈，直到选够n-1条边为止。

避圈法

最小树形图问题破圈法

① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；

② 去掉该圈中权数最大的边；

反复重复 ① ② 两步，直到最小树。

破圈法

最小树形图问题Kruskal 算法

将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集 T，只要不和前面加入的边构成回路，直到 T 中有 n-1 条边，则 T 是最小生成树。

Kruskal 算法

*文章为作者独立观点，不代表造价通立场，除来源是“造价通”外。
关注微信公众号造价通（zjtcn_Largedata），获取建设行业第一手资讯

热门推荐

相关阅读