我们可以在对无向图使用 Kruskal 的 MST 时使用 n(V) <= n(E) 来检测循环吗？
Can we use n(V) <= n(E) to detect cycle while using Kruskal's MST for an undirected graph?
根据GeeksForGeeks，在无向图中求最小生成树的步骤是：
- 按权重的非降序对所有边进行排序。
- 选择最小的边。检查它是否与目前形成的生成树形成循环。如果未形成循环，则包含此边。否则，丢弃它。
- 重复步骤#2，直到生成树中有 (V-1) 条边。
此处，对于第 2 步，使用了 Union Find 算法。
如果我们检查以下条件而不是这种方法会怎样：
（图中已包含的顶点数）<=（图中已包含的边数）。
我相信如果上述条件成立，就会有一个循环（因为不会有任何度数为 0 的顶点）
我的做法有什么问题吗？
虽然时间复杂度保持不变，因为我们仍在对边缘进行排序，但这种方法可以减少执行步骤 #2 所花费的时间和代码复杂度。
不，你不能使用这个，因为你可能会在图中遇到一个循环，其中 n(V) > n(E)。
例如图由4个顶点组成，有3条边，1-2、2-3、1-3。有一个循环，但不是 n(V) <= n(E).
本质上，您所做的是在 n(V) <= n(E) 的情况下检测循环，但您没有证明循环仅限于为真的情况。
正如@Maurycat 所说，当图形中有两个组件并且其中一个组件有一个循环时，这将不成立。
根据GeeksForGeeks，在无向图中求最小生成树的步骤是：
- 按权重的非降序对所有边进行排序。
- 选择最小的边。检查它是否与目前形成的生成树形成循环。如果未形成循环，则包含此边。否则，丢弃它。
- 重复步骤#2，直到生成树中有 (V-1) 条边。
此处，对于第 2 步，使用了 Union Find 算法。
如果我们检查以下条件而不是这种方法会怎样：
（图中已包含的顶点数）<=（图中已包含的边数）。 我相信如果上述条件成立，就会有一个循环（因为不会有任何度数为 0 的顶点）
我的做法有什么问题吗？ 虽然时间复杂度保持不变，因为我们仍在对边缘进行排序，但这种方法可以减少执行步骤 #2 所花费的时间和代码复杂度。
不，你不能使用这个，因为你可能会在图中遇到一个循环，其中 n(V) > n(E)。
例如图由4个顶点组成，有3条边，1-2、2-3、1-3。有一个循环，但不是 n(V) <= n(E).
本质上，您所做的是在 n(V) <= n(E) 的情况下检测循环，但您没有证明循环仅限于为真的情况。
正如@Maurycat 所说，当图形中有两个组件并且其中一个组件有一个循环时，这将不成立。