为什么图论中的边不能小于顶点？

Question

在分析Kruskal算法后，Kruskal算法显然被认为是E log E，因为"对于一个MST的存在，E不能小于V，所以假设它占主导地位">

然而，最简单的树输入将有更多的顶点比边…

我正在看的讲座幻灯片的片段

谁能告诉我为什么对于MST的存在，E不能小于V，所以假设它占主导地位

因此运行时是ElogE而不是ElogE + V

Answer 1

术语" smaller ";这里应该从计算复杂性(big-O)的角度来理解。

要使MST存在，E必须大于等于V - 1。虽然你是对的，这意味着E可以小于V，但它把它放在同一个复杂性类中。

对于具有MST的图，E可以是O(V)或O(V^2)，或介于两者之间的任何值。