我分析了kruskal算法的运行时间，得出了o（eloge+elogv+v）
我问我的教授，他说如果图是非常稀疏的，有很多孤立的顶点v支配e，如果不是这样，那么e支配v，我不明白为什么？
我可以举一个例子，图不是稀疏的，但V仍然大于E
有人能帮我澄清这一困惑吗？
最佳答案
无向图中的Atree具有|V|-1边。
由于树是边尽可能少的连通分量，这基本上意味着对于每个连通的无向图，e在Omega(|V|)中，所以v由e支配。
这基本上意味着如果|E| < |V|-1-图没有连接。
现在，由于kruskal算法是为寻找生成树而设计的，一旦找到|E| < |V|-1-根本没有生成树，找不到生成树，就可以中止该算法。
由此可见，当|E| < |V|-1时，讨论Kraskar算法的复杂性是没有意义的，我们可以安全地假设|E| >= |V| -1，所以|V|是由|E|所支配的。