0

我正在使用 NGenerics 的 Prim 算法来找到连接一些顶点的最小生成树。这就像在每个顶点都连接到每个其他顶点的图上搜索 MST，这意味着边比顶点多，我应该使用 Prim 算法（而不是 Kruskal 算法）。Prim 的算法，如果实施得当，具有 O(|E| + |V| log |V|) 时间复杂度。由于 NGenerics 是一个众所周知的库，它可能具有 Prim 算法的最佳实现，或者至少比 O(|V|^2) 更好。

但是，有一个问题：
如果我想使用 NGenerics 库，我必须将我的图形的所有边添加到 NGenerics 图形数据结构中。像这样的东西（这是伪代码）： 

for i = 0 to |V| - 1
  for j = i + 1 to |V| - 1
    graph.Add(new Edge(vertices[i], vertices[j])

但是，这部分代码显然具有 O(|V|^2) 时间复杂度，这比使用具有更好算法实现的库的目的要好。好吧，不是真的，因为常量也有影响，但我的算法现在是 O(|V|^2) 仍然令人沮丧。

无论如何，我在这里错过了什么吗？我可以在 O(|E| + |V| log |V|) 中完成这项工作吗？

4

0 回答 0