最小生成树怕负权重吗？
这是为什么大多数图算法不那么容易适应负数的后续问题？。
我认为最短路径(SP)存在负权重的问题，因为它将路径上的所有权重相加，并试图找到最小权重。
但我不认为最小生成树(MST)在负权值上有问题，因为它只取单个最小权值边，而不关心整体总权值。
我说的对吗？
共有1个答案
是的，你是对的。MST的概念允许任意符号的权重。两种最流行的MST算法（Kruskal算法和Prim算法）在负边情况下工作良好。
实际上，你可以在你的图的所有边加上一个很大的正常数，使所有的边都是正的。MST（作为边缘的子集）将保持不变。
-
假设所有边的权值都为正，那么通过对每条边的，然后应用Kruskal或Prim得到最小乘积生成树。但如果某些权重为负值，我们就不能应用这个程序。因为我们需要包含奇数个负边，而这些边必须具有最大的权重。在这种情况下怎么办？
-
如果它一定是一棵树，你能解释一下连通性和极小性之间的矛盾吗。但是如果你认为它可能是其他的子图，那么你能给我一个例子，一个连通图可能不是树，它的权重更低。
-
主要内容：生成树,最小生成树数据结构提供了 3 种存储结构，分别称为线性表、树和图，如图 1 所示。 图 1 3 种存储结构 a) 是线性表，b) 是树，c) 是图。 在图存储结构中，a、b、c 等称为顶点，连接顶点的线称为边。 线性表是最简单的存储结构，很容易分辨。树和图有很多相似之处，它们的区别是：树存储结构中不允许存在环路，而图存储结构中可以存在环路（例如图 1 c) 中，c-b-f-c、b-a-f-b 等都是环路）。
-
对于最小生成树问题的求解，geotools graph包中是否有Prim的算法或任何其他算法的实现？
-
假设我选择V(H)={a,e,f}和e(H)={ae,af,fe} 现在，对于每条边e∈e(H)，我们用e'记下了（来自原始图G的） 达到这个最小值的边。所以E'={bc,df,eg},因为bc=4,df=9,eg=8,是连接我的元件的最小边。我在H中有一个相对于代价函数C′的最小生成树，而a′是这棵树的边集。 但是我的A'的边和E'的没有一条是一样的。
-
我一直在读生成树的概念及其类型。这就是我所理解的： 生成树：图G中连接所有顶点的边数最小的子集 最小生成树：它是边权的总和最小的生成树。 现在，这是否意味着，在检索MST时， > 如果我们遇到G中的一条路径，它有更多的边（与其他路径相比），但在边权重总和上的权重最小（与所有其他路径相比），我们将不把它视为MST？ MST的概念是否只有在G有多个生成树的情况下才起作用？其他跨树=mst？ 谢谢你的帮