问题标签 [spanning-tree]

给定一个具有红色和蓝色边的图G和一个常数K ，设计一个确定性的线性时间算法，该算法找到G的生成树，其中恰好有K个红色边（False如果这样的生成树不存在，则返回）。

到目前为止我们做了什么：

让每条红色边的权重为 -1，每条蓝色边的权重为 0。

找到最小生成树（使用标准线性时间算法）。因此，我们有一个权重最小的生成树T，这意味着我们使用了尽可能多的红色边，因为红色边只会降低权重。

如果T中有少于K个红色边，我们返回。False

如果正好有K个红色边，我们就完成了，T就是答案。

如果有超过K个红色边缘，我们需要将它们替换为蓝色边缘。

这是我们的问题，我们如何在线性时间内做到这一点？

添加的每个蓝色边缘都会创建一个循环，因此从循环中删除一个红色边缘将起作用，但我们如何才能以这种方式实现线性？这甚至是一个好方法吗？

下面引用了这个问题的完整版本：

设 G 是具有 n 个顶点、m 个边具有不同边权重的连通图。设T为G的n个顶点n-1条边的树（即生成树），定义T的瓶颈边为T中权重最小的边。如果不存在具有更大瓶颈边缘的生成树，则最大瓶颈树是 G 的生成树。证明或提供以下陈述的反例：

G 的每个最大生成树都是 G 的最大瓶颈树

我认为由于该图具有唯一的边权重，因此 G 的每个生成树也是唯一的。那么G只有一个最大生成树，如果我能证明这棵树也是一个最大瓶颈树，那么这将证明这个陈述是正确的，但前提是对于所有具有唯一边权重的图都是正确的.

我已经尝试寻找反例来证明这一点是错误的，但到目前为止，看起来我用独特的边权重绘制的每张图最终都有最大生成树也是最大瓶颈树。我想我可以用它来证明这个说法是正确的，但我不知道如何措辞。

如果我知道给定的图实际上是一棵生成树，即每对顶点之间只有一条路径，我如何找到从每个顶点到每个顶点的最短路径？我想要最优化的解决方案。我知道 Dijkstra 算法，但它的时间复杂度很高。

我基本上想知道一个来源的每个顶点的距离和路径。鉴于它是一棵生成树，最好和最优化的解决方案是什么？

此外，鉴于图实际上是生成树，请告诉我是否有一些不同的方法可以找到所有对最短路径，而不是多次应用单源最短路径算法。

请注意我的过度解释。

我编写了这个伪代码来从无向图 (G,V) 创建生成树，其中 S 是堆栈，v 是我们要开始计算的顶点：

由于某种原因，这个算法是错误的。例如，让我们考虑这个简单的无向图：

如果我们从第一个顶点开始，我们访问它，然后我们将 2 和 3 压入堆栈，并创建两条边：(1,2) 和 (1,3)。然后我们访问 3，由于它连接到尚未访问的 2，我们还创建了一条边 (3,2)，但这会创建一个循环，因此计算出的生成树不是树。哪里错了？我想不出另一种在 O(n) 中计算生成树的方法。

我希望有人可以帮助解决我遇到的问题。首先，我尝试尽可能多地删除不会导致问题的代码。

我的问题是：当我运行程序时，一切都运行得很好，直到我创建了一个包含大约 130 个节点的图形。一旦达到 130 多个节点，程序将永远在无限循环中运行。

我尝试在 15 处运行具有 135 个节点的程序以获得所需的图形密度。

为了提供一些背景信息，我正在研究模拟，为此我正在创建随机图并使用 BFS 构建生成树。

我的问题是在创建生成树期间出现的。

复制并粘贴代码并使用 javac MMB.java 编译所有在一个文件中。

让我们将图的方差定义为其边权重的方差。我试图解决的任务是设计一个算法，给定一个图 G 将构建一个具有最小方差的生成树 T。

我很难让球继续前进。到目前为止，我已经注意到，如果知道这种生成树中的平均边权重，那么可以通过将每条边的权重替换为其偏差的平方与平均权重的平方并将图形输入到任何 MST 发现中来解决问题算法。

显然，我对我试图构建的树中的平均边缘权重一无所知，但是我发现平均值必须落在 G 的 2 个边缘之间，也许可以利用这些信息。

我试图将问题减少到找到具有修改边缘权重的 G 的 MST。我考虑过为 G 的每条边运行一个算法，每次都假设初始边最接近 T 中的平均值并给定权重 0，而其他边的权重等于它们与初始边的权重的偏差的平方. 这种方法一无所获，因为如果平均值不等于其中一个边的权重，那么根据它落在 2 个最近边的权重之间的位置，基于它们的权重的边的排序会有所不同，并且会产生不同的跨度输入 MST 查找算法时的树。这是我不知道如何处理（或者甚至可以处理）的事情。

这是家庭作业，所以我更愿意给我一个小提示，让我朝着正确的方向前进，而不是一个解决方案。

我有一个图的生成树，从顶点 v 开始。所有边的距离都相同（比如说 1）。

我怎样才能算出从 v 到另一个顶点 u 的最短路径？

我编写了一个程序，它收集了至少 500 个 Wikipedia 页面以及从这些页面到其他 Wikipedia 页面的链接。它从每个网页收集词频，以确定图中两个顶点（网页）之间的成本。

我现在正在尝试创建第二个程序。我正在使用Swing在 NeatBeans 中创建一个 GUI，用户可以在其中选择两个网页，然后以图形方式查看它们之间的最短路径。我不确定如何直观地显示图表。我一直在研究使用JFreeChart或JUNG，但似乎都无法创建我想要的那种图表。

这是我要创建的示例：

这个问题与这个问题非常相似：spanning tree with exact k coloured edges

这不是同一个问题！- 如您所见，上述问题的答案不一样（对我的Q）....

我们有一个连通的无向图G=(V,E)，其边要么是红色的，要么是蓝色的。

我们知道|V|=n。我们得到两个数字：红色边缘是a1,a2∈N哪里，蓝色边缘是哪里。.a1a2a1+a2=n−1

a1我们必须找到一种算法来检查是否存在恰好具有红色边缘和a2蓝色边缘的生成树。如果不是，则算法返回不存在符合此条件的生成树。

我试图从上面提到的问题中获得帮助，但我仍然卡住了。我认为这些是非常相似的问题。

在这个作业中，我必须向 EdgeList 和 AdjMatrix 对象类添加一个例程，以返回广度优先生成树。签名将是：

在 EdgelList 中： EdgeList BFSpanning();

在 AdjMatrix 中：EdgeList BFSpanning();

但我真的很困惑，我只是在这两个类中编写 BFSpanning 方法吗？谁能给我一个硬结构？我似乎无法写出正确的方法。

这是我的 adjmatrix 类：

这是我的 edglist 课程：

也不知道你是否需要看到这个类的边缘：