问题标签 [minimum-spanning-tree]

如果这个问题有点宽泛，我深表歉意，但我很难理解如何创建最小成本生成树。如果重要的话，这是在 C++ 中。

据我了解，您将使用 Kruskal 来选择构建生成树的最小成本边。我的想法是将边缘读入一个minheap，这样你就可以从顶部移除，以便以最低的成本获得边缘。

到目前为止，我只能为 union-find 实现 minheap 和 sets，我仍然不确定 union-find 的目的和用于创建生成树的排序算法。

我将不胜感激任何建议。

编辑：我不限于联合查找、minheap、kruskals 和排序算法，也不需要我做任何事情。这些只是导师建议的项目。

http://en.wikipedia.org/wiki/Minimum_spanning_tree

我希望将我的最小生成树算法与最佳中的最佳算法进行基准测试。有人知道我在哪里可以找到这些算法的 C++ 实现吗？我用谷歌搜索并没有找到任何东西。如果这些算法是最好的，那么肯定在某个地方一定有 C++ 实现吗？

迄今为止最快的最小生成树算法是由 David Karger、Philip Klein 和 Robert Tarjan 开发的，他们发现了一种基于 Borůvka 算法和反向删除算法组合的线性时间随机算法。[2][3] Bernard Chazelle 提出的最快的非随机算法基于软堆，一个近似优先级队列。[4][5] 它的运行时间为 O(m α(m,n))，其中 m 是边数，n 是顶点数，α 是 Ackermann 函数的经典反函数。函数 α 增长非常缓慢，因此对于所有实际目的，它可以被认为是一个不大于 4 的常数；因此 Chazelle 的算法需要非常接近线性时间。如果边缘权重是具有有界位长度的整数，然后确定性算法具有线性运行时间。 [6] 对于一般权重是否存在具有线性运行时间的确定性算法仍然是一个悬而未决的问题。然而，Seth Petie 和 Vijaya Ramachandran 发现了一种可证明的最优确定性最小生成树算法，其计算复杂度未知。 [7]

我已经针对 Boost C++ 的图形算法进行了测试。

Kruskal 最小生成树算法的反面是否适用？我的意思是，每一步都选择最大重量（边缘）？

找到最大生成树的任何其他想法？

考虑 A* 算法。

在 Google 中可以找到一个很好的伪代码：

好吧，我不明白一件事：考虑一下图中的情况：

A* 如何能够从 a->b->c 变为 a->d... ??? 好吧，我的意思是，A* 从一个节点开始并通过节点导航。在某一点，一个节点有多个邻居，嗯，A* 能够遵循由邻居生成的路径，但在某一点它能够切换......并从前一个开始返回它的步骤节点并走另一条路，即使废弃的路径没有穿过那条路......

在代码中，启用此环境的条件是什么？

嗨，很棒的人！

我有一个问题......当我的测试用例到达allEdges.add(newEdge);connectNodes 方法时，我得到一个 NullPointerException。

我认为这与Edge newEdge = new Edge( n1, n2, weight );以前使用相同的方法有关。

问题是我在 Edge 类中使用泛型还是类似的东西？我之前收到一个错误，指示我Edge newEdge = new Edge( n1, n2, weight );排队，说“找不到类”之类的东西。但现在我似乎得到了 NullPointerExceptionallEdges.add(newEdge);而没有改变任何东西。

非常感谢您的每一点帮助！

}

我一直盯着这个，它让我发疯。

不知何故e = pq.poll( );，在一个较大的最小生成树的测试用例中，e 的值为 null。一个很小的最小生成树工作。

我非常感谢关于这个问题的所有提示，以及如何解决这些问题，因为我觉得我在这里遥遥无期。

感谢您的帮助！

编辑：我的优先队列似乎是空的。无法弄清楚为什么会这样：/

edit2：我在这里添加了 DisjSet 类以获得额外的洞察力

类声明和一些成员：

DisjSet 类：

失败跟踪是否有帮助？：

令 G 为具有不同边权重的无向图。令 T 为 G 中的 MST。令 (u, v) 为 T 中的任何边。证明存在一个割 (S;VS) 使得 (u;v) 是该割中权重最小的边。

我对包含不属于最小生成树一部分的边e的最小生成树的一般形式感到困惑。我的问题是：

令G为所有边权重等于 1 的加权图。G的 MST不包括边e。在包含边e的约束下，可以制作多少个 MST ？

我整天都在努力理解 Dijkstra 的算法并实施，但没有取得显著成果。我有一个城市及其距离的矩阵。我想要做的是给定一个起点和一个终点，找到城市之间的最短路径。

例子：

我开始想知道是否有其他方法可以解决这个问题。如果我从原点应用 Prim 算法，然后循环遍历创建的整个树，直到找到目标点会怎样？

我有一个无向图，表示为欧几里得权重的邻接矩阵。我用它来表示更大完整图的最小生成树。

我想要找到的是图中的单个节点，当用作根节点时，它会创建最短的树高。我想出的是使用每个节点作为根执行深度优先遍历，并跟踪看到的最短高度。有没有更快的方法来实现这一点？