问题标签 [spanning-tree]

我有一个与生成树协议有关的非常基本的问题，它如何在路径中提供冗余这是我在某处读到的关于 STP 的内容，但我认为它禁用了 Network Redundancy 。

小伙伴们你们怎么看？

“请注意，确保这个问题属于 SO”，如果不是，则忽略它。

如果给定的树是 MST，我如何检查线性时间 O(n)？

我不想找到所有最小生成树，但我想知道其中有多少，这是我考虑的方法：

• 使用 prim 或 kruskal 算法找到一棵最小生成树，然后找到所有生成树的权重，当它等于最小生成树的权重时，递增运行计数器。

我找不到任何方法来找到所有生成树的权重，而且生成树的数量可能非常大，所以这种方法可能不适合这个问题。由于最小生成树的数量是指数级的，因此将它们计数起来并不是一个好主意。

• 所有的权重都是正数。
• 我们也可以假设图中没有权重出现超过 3 次。
• 顶点数将小于或等于 40,000。
• 边数将小于或等于 100,000。

图中只有一棵最小生成树，其中顶点的权重不同。我认为找到最小生成树数量的最佳方法必须是使用此属性。

编辑：

我找到了解决这个问题的方法，但我不确定它为什么有效。谁能解释一下。

解决方案：求最小生成树长度的问题是众所周知的；寻找最小生成树的两种最简单的算法是 Prim 算法和 Kruskal 算法。在这两者中，Kruskal 的算法以权重递增的顺序处理边缘。不过，克鲁斯卡尔算法有一个重要的关键点需要考虑：当考虑按权重排序的边列表时，边可以贪婪地添加到生成树中（只要它们不连接已经以某种方式连接的两个顶点）。

现在考虑使用 Kruskal 算法的部分形成的生成树。我们已经插入了一些长度小于 N 的边，现在必须选择几条长度为 N 的边。算法规定，如果可能，我们必须在任何长度大于 N 的边之前插入这些边。但是，我们可以以我们想要的任何顺序插入这些边。还要注意，无论我们插入哪条边，它都不会改变图的连通性。（让我们考虑两个可能的图，一个具有从顶点 A 到顶点 B 的边，而另一个没有。第二个图必须将 A 和 B 作为同一连通分量的一部分；否则从 A 到 B 的边将被插入到一点。）

这两个事实一起意味着我们的答案将是使用 Kruskal 算法插入长度为 K 的边（对于 K 的每个可能值）的方法数的乘积。由于最多有三个任意长度的边，因此可以暴力破解不同的情况，并且可以在每个步骤之后像往常一样确定连接的组件。

加权图G的最小瓶颈生成树是G的生成树，使得生成树中任何边的最大权重最小化。MBST 不一定是 MST（最小生成树）。

请举一个这些陈述有意义的例子。

我有一个带有未加权边的无向连通图。如何构建生成树（解决方案可能不是唯一的），以使所有节点的深度总和最小化？这显然没有找到最小生成树，因为边缘的“权重”实际上取决于孩子的深度。

我认为，给定一个指定的根，深度总和最小的树可以通过以广度优先顺序贪婪地将所有可以连接的子节点连接到每个节点来形成。因此，我将通过应用相同的过程 N 次来找到总深度最小的树，将 N 个节点中的每一个指定为根，并在 N 个候选者中选择最小的一个。这是一个有效的算法吗？请指出它是否错误，或者是否存在更有效的方法。

通过运行 kruskal 算法可以找到最大生成树（只需更改边函数并首先考虑最大权重边）。我有兴趣找到最大权重欧几里得生成树。是否存在比 kruskal 更好的算法（更好的最坏情况运行时间）来找到这样的生成树？

在给定的连接和无向图上运行深度优先搜索 (DFS) 算法G = (V,E)可提供生成树。在图上运行 DFS 时，当我们到达一个度数大于 1 的顶点时，即 - 有多个边连接到它，我们随机选择一条边继续。我想知道选择边（或顶点）继续的选项是否实际上允许使用 DFS 创建给定图形的每个生成树？

最小乘积生成树与最小和生成树不同吗？请解释（如果可能的话，用例子）。我的意思是，添加到最小值的边缘应该（？）也有最小的产品。

我遇到了一个基于生成树的问题，即：

边不相交的生成树是什么意思？这是否意味着不同的树，以至于它们在所有树中都没有相同的边缘？因为不相交意味着没有共同点。请解释一下，然后它的答案应该是什么？

你们中有人知道使用生成树数据结构的任何现实世界应用程序吗？