问题标签 [spanning-tree]

实现生成树协议时如何获取交换机MAC地址？

有没有什么方法可以在不使用生成树算法的情况下获得最低成本的广播路由方案？

任何可以指导我的参考资料对我都有很大用处。

给定一个无向连通图 G，找到一棵直径最小的生成树。

我有一个连接的无向图，其边都是黑色或白色，还有一个整数 k。我正在尝试编写一个算法来判断是否存在具有恰好 k 个黑色边缘的生成树（不一定要找到实际的树）。

我使用 Kruskal 算法在生成树中找到最小和最大可能的黑边数。如果 k 超出此范围，则不存在具有 k 条边的生成树。

但是我很难考虑是否必须为该范围内的每个 k 生成一棵生成树。我的直觉说是的，并且它适用于我尝试过的每个示例，但我不知道如何证明它。

有什么建议吗？提前致谢。

我是整个分布式系统世界的新手。我需要帮助来了解如何在此环境中形成集群并确定哪个是 CH（集群标头）。我想使用生成树来选择能量最高的节点作为 CH。选择CH时，其他所有节点应将其信息发送到CH并将其发送到基站（红色节点）。

问题是我不知道算法应该如何。这是我尝试做的一些算法

聚类算法

• 每隔一小时，节点会启动一棵生成树来寻找能量最多的节点

• 如果收到“搜索”消息的节点：

  - 比较每个节点的剩余能量，如果来自发送者的能量低于自身。用它自己的 ID 回复。如果来自发送者的能量高于自身。回复发件人 ID 并将其传递给另一个邻居

• 当一个节点收到它自己的 ID 时，它会成为自己的集群头
• 当其他节点知道簇头已经被选择时，开始向簇头发送信息

环境：

假设这是一个路由器网络

数字是每个节点的能量功率

红色节点是基站。

我有一个只有父母和孩子的 n 叉树结构。spantree 本身只包含一个节点，即根。然后创建与其他节点或根链接的节点。每个节点（包括根）最多允许有 MAXCHILDREN 个子节点。这是结构：

视觉图：

在我创建了我的树之后，我想释放整个事情，但我不确定用哪种方式去做。我不能从根开始解除分配，因为这样树就会被破坏。所以我想我必须从叶子开始，一直到根？但这意味着我必须先找到最深的叶子，对吧？我对如何开始感到很困惑。

我不认为这是必要的，但为了保险，这是我每次需要创建新节点时使用的：

我对这个很困惑。刚发帖，如果这是一个愚蠢的问题，请原谅我。

假设我们得到一个带有加权边的图 G=(V,E)。我想创建目标成本为 c 的 G 的生成树，其中生成树的成本定义为其所有边成本的总和。我们如何确定是否存在成本为 c 的 G 的生成树？

如何将不平衡的树转换为（平衡的）生成树？假设我有一棵树（不同节点的子节点数量不同（不一定不同））。我想以这样的方式操纵这棵树，使它成为一个 k-ary 生成树。

允许对树进行各种迭代。限制是我们不能只在一个地方收集所有节点，然后用它们制作生成树（这将是一种简单的方法）。而是必须从给定的树创建生成树。也就是说，子节点可以与父节点（以及祖父节点，如果需要）交换信息（例如，它拥有的子节点的数量和子节点的 ID），并且父节点决定在其子节点之间移动节点（按顺序平衡树）。

您可能已经理解我正在尝试在并行计算环境中执行此操作。其中，节点只知道其父节点的 id、子节点以及每个以子节点为根的子树中的节点数。

（当我们试图平衡树时，父母和孩子会改变）。关于如何解决这个问题的任何提示？

回复为什么这个问题很重要/值得考虑的评论 - 毕竟微不足道的方法是可扩展的：

1. 从理论上讲，开发一种使用小于 O(N) 空间（在普通方法中使用）来构建生成树的算法具有挑战性。

2. 大规模考虑替代解决方案很有趣。

3. 就数字而言：N=100,000（这在当今的超级计算机中很常见，在即将到来的 BG/Q 中 N 将是 1000,000）。在简单的方法中，涉及的步骤是 a) all-reduce b) O(N) 来构造生成树和 c) 最后是一对多广播。

另一种分布式方法可能不会带来太大改进，但出于好奇，它可能值得尝试。

我一直在观看Van Jacobson的演讲，他在演讲中随意声称 IP 尝试在生成树上进行路由，因为不这样做会导致循环，从而迅速导致网络瘫痪。然后他接着说，这里的缺点之一是容量损失，因为您最终会从连接图中删除一些代表空闲链接的边。

从理智上讲，我理解生成树的概念，当你向生成树添加任何边时，你就会创建一个循环。但是，我仍然非常希望看到一个示例，说明这在 IP 的实践中如何发挥作用，在每个节点处发展/导致循环数据的路由状态的上下文中。谁能提供一个孤立的小例子来澄清我的理解？

我正在阅读用于查找最小生成树（在加权图的情况下）和查找图是否具有汉密尔顿路径（取决于汉密尔顿循环的存在）的算法。我把一切都搞砸了。那么汉密尔顿路径和生成树有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有有效的算法来找到生成树（也许是最小生成树），但为什么我们不能有找到哈密顿回路的算法呢？我们可以继续一次添加和删除一条边，直到达到一个循环，也许我们可以找到一个哈密顿循环？