避圈法另一种做法: 1.在所有各边中找到边权最小的一条,将其作为最 小部分树中的第一边;在剩余的边中,仍然找到边权最小 的作为最小部分树的第二条边; 2.在剩余的边中,找到边权最小的边,查看其是否 与前面的边形成圈,如果没有,则在最小部分树中添加该 边,如果形成了圈,则不再考虑该边; 3.重复进行第二步,直到找到第n-1条边为止。 (因为有n个顶点的树中一定有n-1条边)
避圈法另一种做法： 1. 在所有各边中找到边权最小的一条，将其作为最 小部分树中的第一边；在剩余的边中，仍然找到边权最小 的作为最小部分树的第二条边； 2. 在剩余的边中，找到边权最小的边，查看其是否 与前面的边形成圈，如果没有，则在最小部分树中添加该 边，如果形成了圈，则不再考虑该边； 3. 重复进行第二步，直到找到第 n-1 条边为止。 （因为有 n 个顶点的树中一定有 n-1 条边）
例:分别用两种避圈法构造下图的最小部分树。 第一种解法: 1.在点集中任选一点,不妨取S,令{S} 2.找到和S相邻的边中,权值最小的S,4
例：分别用两种避圈法构造下图的最小部分树。 第一种解法： 1. 在点集中任选一点，不妨取 S，令 V={S} 2. 找到和 S 相邻的边中，权值最小的 [S , A]
3.≠={S,4 4.重复第2,3步,找到下一个点
3. V={S , A} 4. 重复第2，3步，找到下一个点
第二种做法求解过程:
第二种做法求解过程：
破圈法求解步骤: 1.从图N中任取一回路,去掉这个回路中边权最大 的边,得到原图的一个子图N 2.从剩余的子图中任找一回路,同样去掉回路中边 权最大的一条边,得一新的子图; 3.重复第2步,直到图中不再含有回路为止。 用破圈法求解上例: 1.任意找到一回路,不妨取DETD,去掉边权最大 的边[T,E;
破圈法求解步骤： 1. 从图 N 中任取一回路，去掉这个回路中边权最大 的边，得到原图的一个子图 N1。 2. 从剩余的子图中任找一回路，同样去掉回路中边 权最大的一条边，得一新的子图； 3. 重复第 2 步，直到图中不再含有回路为止。 用破圈法求解上例： 1. 任意找到一回路，不妨取 DETD，去掉边权最大 的边[T , E];