algorithm - 为什么E支配v？

Question

我分析了 Kruskal 算法的运行时间，得出了 O(ElogE+Elogv+v)

我问我的教授，他说如果图形非常稀疏，有许多孤立的顶点，V 支配 E，如果不是，那么 E 支配 V，我不明白为什么？我可以举一个例子，其中图形不是稀疏的，但 V 仍然大于 E

谁能帮我消除这种困惑？

Answer 1

无向图中的树有|V|-1边。

由于树是具有尽可能少边的连通分量——这基本上意味着对于每个连通的无向图，|E| 在 中Omega(|V|)，所以 |V| 由 |E| 支配。

这基本上意味着如果|E| < |V|-1- 图形未连接。

现在，由于 Kruskal 算法旨在查找生成树，因此您可以在找到后中止该算法|E| < |V|-1- 根本没有生成树，没有必要寻找。

由此我们得出结论，当 时|E| < |V|-1，讨论克鲁斯卡尔算法的复杂性是没有意义的，我们可以有把握地假设|E| >= |V| -1 ，所以|V|由 主导|E|。

Answer 2

密度 = 边数 / 可能边数 = E / (V(V-1))/2

设图为一棵树 E = V - 1

所以 V = (E + 1)

克鲁斯卡尔的复杂性是

O(E log E + E log V + V) = O(E log E + E log (E + 1) + (E + 1)) = O( E log E)

所以E占主导地位。只要 E = O(V)，E 就会占主导地位。