五条边按权重排好是什么样
把这五条边按权重从小到大排一遍。运行下面这段程序: edges = [(0, 1, 2), (0, 2, 1), (1, 3, 3), (2, 4, 9), (3, 4, 1)] print("/".join(str(w
暴力枚举所有生成树
补全 brute_mst:从五条边里取出所有四条边的组合,判断它是不是一棵生成树(不成环且连通),取总长最小的。
⚠️ 拆掉一条边,成本变多少
分别拆掉两条边,各重新算一次最小总长: 拆掉最贵的那条 2-4(权重 9) 拆掉最便宜的那条 0-2(权重 1) 把两个总长拼起来输出(拆最贵的在前)。
Kruskal 的做法
Kruskal 求最小生成树的做法是【0】。
⚠️ 拿什么判断"会不会成环"
Kruskal 判断一条边加进去会不会成环,用的是【0】。
Kruskal 什么时候可以停
Kruskal 可以提前收工的条件是【0】。
并查集连了两次之后
五个点各自一块。先 union(0, 2),再 union(3, 4)。运行下面这段程序,看三件事:0 和 2 连通了吗、0 和 3 连通了吗、现在还剩几块: def make(verts): return {u: u for u
复习:写 find 和 union
补全 find(带路径压缩)和 union(已经在同一块里就返回 False)。 做两次合并之后输出那三件事。
写一个 Kruskal
补全 kruskal:边按权重排好,用 union 的返回值决定要不要这条边。输出最小总长。
Kruskal 是按什么顺序选边的
用同一个 kruskal,把选中的四条边按选中顺序输出(每条写成 a-b,边之间用 / 隔开)。