问题标签 [spanning-tree]

我不知道如何在 Python 中实现一个基本的生成树；未加权的生成树。

我已经学会了如何实现邻接列表：

但我不知道如何实现“查找最近的未连接顶点”。

给定一个简单的无向网格网络，如下所示：

并且假设每条边都有一个与其长度相对应的权重：

怎么可能计算网格中的所有生成树及其相关的总权重？

注意：这是所有权重= 1 的微不足道的情况。

STP BPDU 以协议 id 字段和版本 id 开头。我知道版本是STP的类型：0代表STP，
2代表RSTP
，3代表MSTP。
那么我们真正需要协议 id 字段是为了什么？什么时候不为0？

在 STP 中，我们有 MAX 年龄计时器。它告诉我们在假定根网桥或链路已死之前等待上级 BPDU（在根或阻塞端口上）多长时间。给定那个计时器，为什么每个网桥也必须知道 Hello 计时器？他们如何从中受益？

我知道它背后的逻辑，但我不知道如何应用它来完成我的代码以输出 8。

得到 8 的方法是将图中每个顶点的最短路径相加。最短路径是顶点数最少的路径。如果有平局，那么您使用路径的重量作为平局断路器。

输入示例输入后，有人可以帮我完成输出 8 的代码，如下所示？

输入：

4 6

女性保守派 新保守派 退伍军人

特朗普女性 1

特朗普保守党 1

特朗普新保守主义 5

女性新保守主义者 1

新保守派老兵 5

保守派老兵 1

输出：

8

找到下面的图像以获取图表 这是我的代码：

点击这里

我需要证明，给定一个连通图，每个边都有不同的权重，每个生成树（最小生成树除外）都有一个相邻的权重较小的生成树。w(T') < w(T)，其中 T' 与生成树 T 相邻。

我坚持证明与 MST 相邻的每个 ST 都有相邻的生成树（实际上是 MST）。如何使用任何非 MST 相邻生成树来显示这一点？

我在尝试解决这个问题时遇到了一些问题：（网格图）M 2,4 有多少种不同的生成树？

有人能解释一下如何找到这个号码吗？

（我在课堂上没有看到基尔霍夫定理或矩阵树，所以我不应该使用它们）

谢谢

所以我的问题如下：

我有一个无向（完整）加权图 G=(V,E)，我想生成所有可能的生成树，其叶子数最少，即最小顶点数为 1。让我们称这种树MIN_LEAF。

可能，我想直接在所有具有最小叶数的树中生成总权重最小的树（请注意，这不一定是最小生成树）。确定树 T 是否是给定图 G NP 完全的 MIN_LEAF 的问题？

如果是这样，我想知道是否存在某种启发式算法（贪婪或局部搜索），它至少可以为这个问题提供一个近似的解决方案。

提前致谢。

我试图弄清楚如何从给定的边列表中打印生成树列表。例如，如果我读到：

0 1

2 1

0 2

1 3

我想打印出一个生成树列表：

[[1], [0,2,3], [1], [1]]

我知道如何使用以下代码创建邻接列表：

但是创建生成树是另一回事。鉴于生成树未加权，我不确定是否需要在这里使用 Prim 算法的某个版本？

任何帮助表示赞赏！

我有需要使用 XDocument 处理的 xml 文档

我尝试通过选定的节点属性获取最小子树，例如 98512000, 98513300, 98514000 ：