问题标签 [spanning-tree]

有谁知道什么是共同生成树。如果有一些好的答案，那么有一个例子也很好。

到目前为止，我已经找到了这篇论文。它过时了吗？有没有更快更好的实现？

顺便说一句，维基百科说在无向图中可以有 n^n-2 棵生成树。有向图中可以有多少棵生成树？

我正在 C++ 中执行 BFS 算法以查找生成树，生成树的输出应该按顺序显示，但我对实现有疑问，如果不完全知道如何构建树，我该如何构建树许多孩子有每个节点？考虑递归树结构树的数据结构可以写成：

但是不要认为它可以像前面提到的那样在这个实现中起作用。

这是我按顺序返回树的函数：

我还想知道是否有任何方法可以在不使用树结构的情况下对节点进行预排序。

我正在尝试为作业实现 BFS 算法，我找到了带有 BFS 的生成树算法，问题是我要求生成的生成树按顺序显示。这是我的解决方案代码：

对于这个输入：

我的算法产生输出：[0 1 2 3 4 7 5 6 8 9]。通过打印每个级别的节点来表示 BFS 树，如下图所示：

但是正确的输出（按顺序）应该是[0 1 3 4 5 6 2 7 8 9]，从而导致按顺序遍历树。我需要我的代码的解决方案，如何修复我的代码以向我显示预购解决方案？，因为不必使用树，也就是说，可以以某种方式将树直接存储在我的数组 BFS_tree 中。我坚持这一点。我在这里读到了一个类似的问题，但我不能为效率措施实施树，而且这是不允许的。我怎么能这样做？有可能吗？...对不起，我的英语。

让我们有一个图表。当我们删除一条边时，会创建 2 辆“汽车”，从边的每个顶点创建一辆。当这两辆车相遇时，它们会停下来。问题是创建一棵生成树，以使通过每个顶点的汽车数量之和最小。

增加的困难是，如果一个顶点有 n 辆车从它经过，那么成本是 K^n 而不是 n*K。

一些想法。我们可以找到最短的无弦周期作为开始，但这些无弦周期的位置，即它们是否相互接触，会改变度量，从而改变最短周期。

这不是最小生成树问题。我想解决这个问题，因为每辆车都代表一个变量，而生成树是计算优化问题的最有效方法。当来自同一边缘的 2 辆车相遇并停止时，我从优化中减少了一个变量。

编辑：

过程是这样的。我们删除了许多边以使图成为生成树。每条移除的边会创建 2 辆汽车，在被移除的边的每个顶点上都有一辆，它们需要彼此相遇。我们为每辆双车固定一条路径。然后我们检查有多少汽车（从我们移除的所有边）通过每个顶点。如果从一个顶点通过的汽车数量为 n，则成本为 K^n，其中 K 是一个常数。然后我们将所有成本相加，这就是需要最小化的全局成本。

如果有不清楚的地方，请告诉我。 https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric

给定一个有向图，其中每个向量的成本都是非负的，每个顶点的利润都是非负的，你如何找到具有最大利润的图的生成子树？我想将成本限制在给定的预算范围内。我正在寻找多项式时间复杂度问题的近似算法，以及理论近似因子。

我正在使用元启发式方法编写一些代码，以找到解决固定电荷传输问题 (FCTP) 的良好解决方案。

我遇到的问题是基于为底层二分图找到生成树来生成一个起始解决方案。

我希望它是一棵随机生成树，这样我就可以多次针对同一个问题运行该过程，可能会得到不同的解决方案。

我在做这件事时遇到了一些困难。到目前为止，我采用的方法是对弧进行随机排列，然后遍历此列表，如果不会创建循环，则按顺序将它们放入基础。

我需要找到一种快速的方法来检查是否包含弧会创建一个循环。我不想“蛮力”它，因为考虑到大问题实例，这种方法可能需要大量时间。

鉴于这A是一个具有随机排列的弧的数组，您将如何进行选择过程？

我已经为此工作了几个小时，但我尝试过的任何方法都没有奏效，其中大部分在应用方面都是荒谬的......

我正在配置一对交换机，我们的两个数据中心各一个。我们在站点之间有一对链路，一个是专用的专用光纤，另一个是备用的 100Mbps 连接。出于不值得探讨的原因，我需要在链路上推送多个 VLAN，并且需要使用 STP（或等效的）来管理路径冗余并避免交换循环和相关的崩溃。

目前，我在根主节点和辅助节点的备份链路上设置了 4096 的路径成本，效果很好，交换机选择光纤并阻塞备份链路，直到光纤断开。我还为相关 VLAN 设置了 2 的网络直径，这将收敛时间减少到 14 秒（2 倍转发时间）。

我已经读过，使用 RSTP 可以在一秒钟左右获得收敛，如果这是真的，我会很想知道如何。

这是我到目前为止所拥有的（这个配置或多或少地反映在两个交换机上）：

我从 interviewstreet.com 遇到了这个问题

机器再次袭击了锡安王国。锡安王国有N座城市，N-1条双向道路。道路网络使得任何一对城市之间都有一条独特的路径。

Morpheus 得知 K Machines 计划摧毁整个王国的消息。这些机器最初生活在王国的 K 个不同城市，从现在开始，他们可以随时计划并发动攻击。所以他要求 Neo 破坏一些道路以破坏机器之间的连接，即在破坏这些道路之后，任何两台机器之间都不应该有任何路径。

由于攻击可能发生在从现在开始的任何时间，Neo 必须尽快完成这项任务。王国中的每条道路都需要一定的时间才能被摧毁，一次只能摧毁一条。

您需要编写一个程序，告诉 Neo 中断机器之间的连接所需的最短时间。

示例输入 输入的第一行包含两个以空格分隔的整数 N 和 K。城市编号为 0 到 N-1。然后沿着 N-1 行，每行包含三个空格分隔的整数 xyz，这意味着有一条双向道路连接城市 x 和城市 y，摧毁这条道路需要 z 个单位的时间。然后跟随 K 行，每行包含一个整数。第 i 个整数是第 i 个机器当前所在城市的 id。

输出格式 在一行中打印中断机器之间连接所需的最短时间。

样本输入

样本输出

说明 Neo 可以摧毁连接城市 2 和城市 4 的权重为 5 的道路，以及连接城市 0 和城市 1 的权重为 5 的道路。由于一次只能摧毁一条道路，因此所需的总最小时间为 10 个单位时间. 摧毁这些道路后，任何机器都无法通过任何路径到达其他机器。

约束

有人可以给出如何处理解决方案的想法。

我的问题：

令 G(V,E) 为全连接图，其中 V 是节点集，E 是链接集。如果生成树按字典顺序排序，则覆盖图中所有链接所需的最小生成树数量的上限（最坏情况）是多少？

例如，对于 |V|=4，因此 |E|=6，G(V,E) 包含以下 16 个生成树（按字典顺序）；请注意，以不同方式标记链接可能会产生不同顺序的生成树。

1 2 3

1 2 4

1 2 6

1 3 4

1 3 5

1 3 6

1 4 5

1 5 6

2 3 4

2 3 5

2 4 5

2 4 6

2 5 6

3 4 6

3 5 6

4 5 6

在这种情况下，覆盖图中所有链接所需的最小生成树数将是 5 棵生成树（{1 2 3}、{1 2 4 }、{1 2 6}、{1 3 4}、{ 1 3 5}）。所以所有的链接都包含在这 5 棵生成树中。

计算小图的生成树的数量很容易，但我对较大的图有问题，例如|V|>4。

是否有任何公式可以计算生成树的上限以覆盖图中的所有链接？

非常感谢