问题标签 [spanning-tree]

我想知道如何解决这个问题。

我得到了一个图表G = (V,E)。这是一个连通的无向加权图。
该图由一棵生成树和一条附加边组成。
我将如何想出一种算法来计算n = |V|时间复杂度图的 MST。
我在考虑 Kruskal 算法，但它不符合时间复杂度要求。

如何使用呼吸优先搜索从起始顶点查找所有可能的生成树。不止一个。

我需要使用 scapy 生成和 STP 流量，当我通过可视化它时，wireshark我得到类似于下面显示的标题的输出： 当我运行此代码时：

这是我的wireshark输出

我不知道如何将组织代码更改为 00:00:0c，因为我相信这是制造此问题的人

我的任务是有效地处理带有节点Q的生成树图中的查询。N

每个查询都引用我需要处理的一条边，并且我应该输出图中删除该边后剩余的两个组件中的每一个的大小。

我目前的想法是从由该边缘连接的两个节点启动一个 DFS，确保 DFS 永远不会遍历边缘本身。这样，我将能够及时找到两个组件的大小，O(N)总复杂度为O(Q * N).

但是，我认为我可以做一些预处理来进一步降低我的解决方案的时间复杂度，但我就是想不出那可能是什么。有人可以指出我正确的方向吗？

我有以下表示加权图的python字典

我正在尝试创建一个算法，允许在给定节点和边数的情况下生成这些图。为了了解如何从头开始创建图表，我首先尝试将单个节点添加到上面的图表中。我做了以下事情：

这工作得很好。然而我不明白{6:7} 是什么。是字典中的字典吗？是一套吗？

我的目标是能够在一组 n 节点之间添加随机边，所以我试图弄清楚如何执行以下操作。

然而，这是不可能的，因为字典没有附加或添加功能。还有另一种方法可以做到这一点吗？

我正在尝试设计一种算法，其中给定一个连接的加权图 G = (V, E) 和 V 中的顶点 U 的子集，将构造一个最小生成树，使得 U 中的所有顶点都是叶子（其他顶点可能也可以是叶子），或者返回不存在这样的树（假）。

这就是我所得到的，适应 Prim 的算法（公平警告，它真的很糟糕；甚至不知道它是否有效/有效或使用什么数据结构，我会接受任何其他正确的算法）：

我也有一张我认为它会对我画的这张图做些什么的图片： 图片在这里

证明该算法是正确的也会让我高枕无忧。

如何更改此算法以提供最大生成树？

我试着改变它，这样它会给我

但我不认为这是正确的。

我无法提出多项式时间算法来解决以下问题：

设=(,)是一个有顶点的无向无权图。让_1,_2,...,_是=−1的不同生成树。找到一种多项式时间算法，该算法在其中找到
=(,_)包含每个生成树的至少一条边的生成树_。

我真的很感激这方面的任何帮助！

用 Python 编写一个算法，该算法将 prufer 代码作为输入并返回树的边缘集。输入：一个名为“p”的列表（精简代码，零索引）示例：

p = [3,1,0,0,3,2,9,9,2,3]

（可以在代码块中定义 prufer 代码。您不需要编写接受用户输入的函数）输出：名为“edges”的列表（边缘集_示例：

打印（边缘）

[[3, 4], [1, 5], [0, 1], [0, 6], [3, 0], [2, 7], [9, 8], [9, 10], [ 2, 9], [3, 2], [3,11]]

我遇到了麻烦。如何获取“p”的值，以便在“edges”中打印输出？

我有个问题。我正在尝试计算图中的所有生成树（它没有多重边）。我知道有基尔霍夫定理，它让我可以很容易地计算它，但我更喜欢在此图中使用循环的解决方案。

我试图弄清楚循环如何影响生成树的数量，我发现当有一个循环（没有额外的边）时，我们可以简单地删除其中一个边，我们将得到一棵生成树。当有 n 个循环仅由一个节点连接时，我们可以将每个循环中的边数相乘，这就是我们的结果。问题是当两个循环与多个节点（例如 1 或 3 条边）连接时。我试图写一个等式，它可以让我计算这个数字，我唯一得到的是c1*c2-s^2，其中 c1 是循环 nr 的大小。1，c2是循环nr.2的大小，s是它们的公共边的数量。但是在某些情况下它不起作用。我在下面附上一个例子：完整的图表

我们知道一个完整图中的生成树的数量是n^(n-2)，所以我们知道它有16个可能的生成树。但是我的算法找到了其中的 20 个。原因如下：

我发现 3 个周期：(3,4,2),(4,2,1) 和 (3,4,2,1)。然后我只是将我的方程用于循环 nr 1 和 2 (3* 3-1)，它给了我 8，最后我在最后一个循环中再使用一次（8*3-4 [它有 2 个常见的edge]) 这给了我 20。我还必须补充一点，我的循环查找算法并不总能找到一个简单的循环。

有人可以告诉我错误在哪里，以及如何解决吗？提前致谢。