问题标签 [spanning-tree]

我有这个硬件：

1. 从文件中读取边缘列表
2. 把它变成邻接表
3. 输出图的未加权、无向生成树（我们可以假设起点在顶点 0）

我有问题 3. 正确输出。即，文件 1 应该输出[[1],[0,2,3],[1],[1]]，我得到了[[1,2],[0,3],[0],[1]]这有点好，因为它们都是n=4从文件 1生成的树

但这是主要问题：我不知道我的代码有什么问题，对于文件 2：我得到：[[10], [], [10], [10], [], [], [], [], [], [], [0, 3, 2], [], []]

我的代码末尾的文件数据。（编辑：从tree=[]问题所在开始，其余没有问题）

这是我对这个问题的尝试：

我需要检查使用 RSTP 的物理交换机的合规性。我决定使用 SDN（mininet）并将我的真实设备包含到 SDN 拓扑中，而不是构建真正的拓扑。“测试”是指一致性测试、根选举测试、环路预防测试和其他功能测试。我对此很陌生，无法自己决定-

这是我的目的的正确方法还是我不应该使用SDN？

从概念上讲，图表中的生成树和生成森林有什么区别。

另外，是否可以通过DFS或BFS遍历构建生成林？为什么？如何？

我了解生成树，但我找不到任何关于生成森林的明确解释。甚至维基百科（https://en.wikipedia.org/wiki/Spanning_tree）也没有给出明确的定义。我的书（Data Structures & Algorithms, Wiley - 第六版）也没有关于跨越森林的定义。

我想知道，如果我们有一个图，例如其中包含三个连接的组件，是否可以通过 DFS/BFS 遍历构建一个跨越森林？

我指的是这里给出的生成树的解释。

我想知道生成树可以包含自循环吗？即从一个顶点到自身的边缘？我觉得不是; 因为对于那个循环，有两条路径可以到达那个节点。一个直接，一个包括循环，但我想确认一下。

这基本上是一个 ICPC 东京区域问题 - Slim Span(UVA -1395)

链接到问题 - https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4141

该问题指出，最苗条的树是其最短边和最长边之间差异最小的树，并且树本身不需要是最小生成树，它只需要是生成树即可。

我的想法是使用苗条而不是权重对边缘进行排序。它不起作用，因为从一开始它总是将最短边标记为已访问。

如何更正我的程序以解决此问题？

样本输入-

4 6//节点数，边数

1 2 10//源目标权重

1 3 100

1 4 90

2 3 20

2 4 80

3 4 40

输出 - 20

log假设如果所有边的权重都为正，则可以通过取每条边的 ，然后应用 Kruskal 或 Prim来获得最小乘积生成树。但是如果某些权重是负数，我们就不能应用这个过程。因为我们需要包含奇数个负边缘，并且这些边缘必须具有最大权重。这种情况下怎么办？

这就是问题所在。

给出了一个加权无向连通图 G。权重是恒定的。任务是提出一种算法，该算法将找到满足这两个条件（按优先级排序）的 G 的生成树的总权重：

• 生成树必须具有相同权重的最大边数（实际重复的权重值无关紧要）；
• 应该最小化总的生成树权重。这意味着，例如，权重为 120 的生成树 T1 应优先于权重为 140 且权重为大多数 4 条边具有相同的权重（这四个边的权重为 8）。

我已经坚持了很长一段时间了。我已经为图实现了Boruvka的MST搜索算法，现在我不确定是否应该在找到MST之后执行任何操作，或者最好修改MST-search算法本身。

欢迎任何建议！

“Uplink Fast”解决方案对生成树协议有何改进？

就像标题已经说的那样，我正在尝试绘制一棵生成树。

但是，如果我尝试绘制图表，则会出现以下错误：

附加信息：

用更少的观察尝试了同样的方法，它工作得非常好。错误的原因是什么，如何修复代码？

我发现了这个简洁的 Kruskal 算法实现，现在我想“反转”它，以便它产生最大生成树而不是最小生成树。我太天真了，试图改变if rank[root1] > rank[root2]:工会if rank[root1] < rank[root2]:。显然这没有奏效。我还尝试在几个地方交换 root1 和 root2。显然，这段代码的复杂性超出了我的技能。编码：

如何更改脚本以生成最大生成树？只要返回的图表看起来像这样，即使是激进的更改也是受欢迎的

谢谢！