tom*_*mmy 8 algorithm graph prims-algorithm kruskals-algorithm
我试图理解为什么Prim和Kruskal在稀疏和密集的图形方面有不同的时间复杂性.在使用几个小程序来演示每个小程序如何工作之后,我仍然对图的密度如何影响算法感到困惑.我希望有人能给我一个正确方向的推动.
jk.*_*jk. 1
这些不同的复杂性是否与顶点数量有关？
经常有一个稍微有点夸张的说法，对于稀疏图，边的数量 E = O(V)，其中 V 是顶点的数量，对于稠密图，E = O(V^2)。由于这两种算法都可能具有取决于 E 的复杂性，当您将其转换为取决于 V 的复杂性时，您会根据稠密图或稀疏图获得不同的复杂性
编辑：
不同的数据结构也会影响复杂性，当然维基百科对此有详细介绍
归档时间：
15 年，8 月 前
查看次数：
4141 次
最近记录：
13 年，2 月 前