在对无向图使用Kruskal的MST时，是否可以使用n(V)

Question

根据GeeksForGeeks的说法，在无向图中找到最小生成树的步骤如下：

1. 按其权重的非递减顺序对所有边进行排序。
2. 选择最小的边缘。检查它是否与到目前为止形成的生成树形成循环。如果没有形成循环，则包括此边。否则，将其丢弃。
3. 重复步骤#2，直到生成树中有(V-1)条边。

这里，对于步骤#2，使用联合查找算法。

如果我们不采用这种方法，那么检查以下条件：

（图中已包含的顶点数）<=（图中已包含的边数）。我相信如果上面的条件是真的，就会有一个循环（因为不会有任何顶点的度是0）

我的方法有什么问题吗？虽然时间复杂度保持不变，因为我们仍然对边缘进行排序，但这种方法可以减少执行步骤#2所花费的时间和代码复杂度。

Answer 1

不，你不能用这个，因为你可以在一个图中遇到一个循环，对于这个循环，n(V)>n(E)。

例如，图由4个顶点组成，有3条边，1-2、2-3、1-3。存在一个循环，但n(V)<=n(E)不是真的。

本质上，你所做的是检测出一个循环，如果n(V)<=n(E)，但你没有证明，循环仅限于当它是真的情况。