最小瓶颈生成树和最小生成树有何不同？
一个加权图 G 的最小瓶颈生成树是指 G 的一棵生成树，使得生成树中任意边的权重最大值最小化。最小瓶颈生成树不必然是最小生成树（MST）。 请给一个例子以便更好地理解这些定义。
最小化连接多个边缘的顶点的生成树？
有没有一种算法可以找到一个无向图的生成树，使连接多于一条边的顶点数量最小化？ 例如，给定一个4 x 4的网格图，我们想要找到一个生成树，像左边那样（有7个顶点连接多于一条边），而不是右边那样（有12个顶点连接多于一条边）： 编辑：如果我们只考虑平面图（甚至只考虑网格图），那么这个问题会...
汉密尔顿路径和ST的区别
我在阅读关于寻找最小生成树（对于加权图）和判断一个图是否存在哈密顿路径（依赖于哈密顿回路的存在）的算法时一脸懵逼。那么哈密顿路径和生成树之间有什么区别呢？它们都覆盖了图中所有的顶点。虽然我们可以使用高效的算法来寻找生成树（也许是最小生成树），但为什么我们不能寻找哈密顿回路的算法呢？我们可以不断...
生成树与生成森林的区别
概念上，图中的生成树 (Spanning Tree)和生成森林 (Spanning Forest)有何不同？ 此外，是否可以通过深度优先搜索 (DFS)或广度优先搜索 (BFS)遍历来构建生成森林？为什么？怎样实现？ 我了解生成树，但是我找不到任何关于生成森林的清晰解释。即使是维基百科(h...
如何在一个图中找到所有最小生成树的总数？
我不想找到所有的最小生成树，但我想知道有多少个，这里是我考虑的方法： 使用 Prim 或 Kruskal 算法找到一个最小生成树，然后找到所有生成树的权重，并在其等于最小生成树的权重时增加运行计数器。 我无法找到找到所有生成树权重的方法，而且生成树的数量可能非常大，因此这种方法可能不适用于...
具有负权重的最小生成树问题
假设所有边权都为正数，可以通过取每条边的log然后应用Kruskal或Prim算法来获取最小生成树。但是如果一些边的权值为负数，则无法应用此过程，因为我们需要包括奇数条负边，并且这些边必须具有最大权重。在这种情况下该怎么办呢？
寻找一棵生成树，使得节点深度和最小。
我有一张无向连通图，边权重为1。我该如何构建一棵生成树（可能不唯一），使所有节点的深度之和最小？这显然不是找到最小生成树，因为边的“权重”实际上取决于子节点的深度。 我认为，在指定根节点的情况下，可以通过贪心地按广度优先顺序连接所有可连接的子节点来形成深度之和最小的树。因此，我将通过将此相同...