问题标签 [minimum-spanning-tree]

这是消费税

假设给定图 G 的最小生成树 T（具有 n 个顶点和 m 个边）和一条权重为 w 的新边 e = (u, v)，我们将添加到 G。给出一个有效的算法来找到图 G + e 的最小生成树。你的算法应该在 O(n) 时间内运行以获得完整的信用。

我有这个想法：

In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.

棘手的部分是如何在 O(n) 时间内做到这一点，而且我也被卡住了。

问题是如何存储 MST。在普通 Prim 算法中，MST 被存储为父数组，即每个元素都是相应顶点的父元素。

所以假设消费税给了我一个指示 MST 的父数组，我怎样才能在 O(n) 中释放上述算法？

首先，如何从父数组中识别 u 和 v 之间的路径？我可以为 u 和 v 设置两个祖先数组，然后检查共同的祖先，然后我可以获得路径，尽管是向后的。我认为对于这部分，要找到共同的祖先，至少我必须在 O(n^2) 内完成，对吧？

然后，我们有了路径。但是我们仍然需要找到沿路径的每条边的权重。由于我认为该图将使用 Prim 算法的邻接列表，因此我们必须执行 O(m)（m 是边数）来定位边的每个权重。

...

所以我认为不可能在 O(n) 中执行该算法。我错了吗？

这是为什么大多数图算法不那么容易适应负数的后续问题？.

我认为最短路径 (SP) 存在负权重问题，因为它会将路径上的所有权重相加并试图找到最小的权重。

但我不认为最小生成树（MST）有负权重的问题，因为它只需要单个最小权重边缘而不关心整体总权重。

我对吗？

这是一个消费税：

考虑从加权连通图 G 中找到最小权重连通子集 T 的问题。T 的权重是 T 中所有边权重的总和。给出一个计算最小权重连通子集 T 的有效算法。

这是我得到的：

1. 我必须假设权重是由正负混合的。对于这种消费税，只有两种权重的混合才有意义。

2. 我将首先对边缘进行排序，因此负边缘将首先出现。

3. 我会考虑使用 Kruskal 的算法，但应该进行一些修改

4. 因为我欢迎负边缘，所以我会尝试添加尽可能多的负边缘。

5. 此外，可以添加一些正边沿，以防并非所有负边沿都连接，并且它们可能需要一些正边沿作为桥接。

好的，以上是我的想法。但是当我试图弄脏我的手时，我被卡住了。

如何始终记录可能设置的最小权重？

例如，

{0, 1} 的权重为 -20

{2, 3} 的权重为 -10

如果 {1, 3} 的权重为 11，那么我当然不想要 {1, 3}

或者如果 {1, 3} 的权重为 9，那么我想要

使用哪种数据结构，我可以始终保持最小权重和该权重的顶点？

值得注意的是，本次消费税所针对的子集edges。

考虑从加权连通图 G中找到最小权重连通子集 T 的问题

这意味着仍然需要包含所有顶点。

它也不仅仅是一个 MST。考虑如果一个顶点有两条边，一条是-1，另一条是-2。在正常的 MST 算法中，只会采用 -2 的边。但是在这种消费税中，需要同时采用-1和-2来进一步降低整体重量。

我正在制作一个程序来计算最小成本路线，使用最小生成树。我用 c++ 实现了我的实现，但我无法制作一个图形界面来读取输入文件，所以我决定将它传递给 Java 语言并使用 Netbeans 创建界面。这是我在 C++ 中的代码：

这是一个练习：

要么证明以下内容，要么举一个反例：

(a) 无向图的最小生成树中的一对顶点之间的路径一定是最短（最小权重）路径吗？

(b) 假设图的最小生成树是唯一的。无向图的最小生成树中的一对顶点之间的路径是否一定是最短（最小权重）路径？

我的答案是

（一种）

不，例如对于图0、1、2，0-1是4，1-2是2，2-0是5，那么0-2的真实最短路径是5，但是mst是0-1-2 , 在 mst 中, 0-2 是 6

(二)

我的问题来自这个（b）。

我不明白如何whether the MST is unique影响最短路径。

首先，我的理解是，当边的权重不明显时，多个MST可能同时存在，对吧？

其次，即使MST是唯一的，上面（a）的答案仍然适用于（b），对吗？

谁能想出一种方法来修改 Kruskal 的最小生成树算法，使其必须包含某个边（u，v）？

Given an undirected connected graph with weights. w:E->{1,2,3,4,5,6,7} - meaning there is only 7 weights possible. I need to find a spanning tree using Prim's algorithm in O(n+m) and Kruskal's algorithm in O( m*a(m,n)).

I have no idea how to do this and really need some guidance about how the weights can help me in here.

设计一种算法，该算法采用加权图 G 并找到对非 MST 边的成本的最小变化，该变化会导致 G 的最小生成树发生变化。

到目前为止我的解决方案（需要建议）：

要更改 MST，我们需要更改非 MST 边 st 的权重，使其比 MST 中起始顶点和结束顶点路径中的最大边小 1。

所以我们可以从遍历 MST 的边开始，对于每个顶点，检查是否有非 MST 边。如果有，可以执行到达边缘端点（在 MST 中）的 bfs。非 MST 边缘权重必须更新为比路径中的最大边缘权重小一。

这将导致非 MST 边缘包含在 MST 中，并且之前的最大边缘从 MST 中删除。

有人可以判断这个解决方案是否正确？谢谢。

令 E 为给定的有向边集。假设已知 E 中的边可以形成一个有向树 T，所有节点（根节点除外）只有 1 个入度。问题是如何有效地遍历边集 E，以便找到 T 中的所有路径？

例如，给定一个有向边集 E={(1,2),(1,5),(5,6),(1,4),(2,3)}。我们知道这样的集合 E 可以生成只有 1 个入度的有向树 T（根节点除外）。有没有快速遍历边集E的方法，以便找到所有路径如下：

顺便说一句，假设 E 中的边数是 |E|，是否存在找到所有路径的复杂性？

我们已经看到生成树和切割是密切相关的。这是另一个连接。让我们删除 Kruskal 算法添加到生成树的最后一条边；这将树分成两个组件，从而在图中定义了一个切割 (S,S)。我们能说什么？假设我们正在处理的图是未加权的，并且它的边是随机均匀排列的，以便 Kruskal 算法处理它们。这是一个值得注意的事实：至少有 1/n^2 的概率，(S,S) 是图中的最小割，其中割的大小 (S, S) 是 S 和 S 之间交叉的边数. 这意味着重复该过程 O(n^2) 次并输出找到的最小切割以高概率产生 G 中的最小切割：用于未加权最小切割的 O(mn^2 log n) 算法。

• 这不取决于通过 Kruskal 算法处理图形的 n^2 种独特方法这一事实吗？我的意思是，如果Kruskal 算法只有3 种独特的方式来处理具有 10 个节点的图，那么重复该过程 n^2 次将不会产生 n^2 独特的“最后一条边”。在唯一的最终切割少于 n^2 个（即少于 n^2 个唯一的“最后边缘”）的情况下，它将如何工作？

• 如果总共有少于 n^2 条边怎么办？例如，您可以有一个只有 9 条边的 10 个节点的连通图，这意味着无论您重复该算法多少次，您都不会有 n^2 个唯一的“最后一条边”。在这种情况下它将如何工作？

• 循环遍历每个边缘并检查边缘是否是最小切割不是更容易吗？在 n 个节点的图中，唯一边的最大数量为 n + n-1 + n-2... + 1 条边，小于 n^2。考虑到 n^2 小于 n^2 log n，为什么不直接遍历所有边，因为这样更快？