生成树与最小生成树的区别
我一直在读生成树的概念及其类型。这就是我所理解的：
生成树：图G中连接所有顶点的边数最小的子集
最小生成树：它是边权的总和最小的生成树。
现在，这是否意味着，在检索MST时，
>
如果我们遇到G中的一条路径，它有更多的边（与其他路径相比），但在边权重总和上的权重最小（与所有其他路径相比），我们将不把它视为MST？
MST的概念是否只有在G有多个生成树的情况下才起作用？其他跨树=mst？
谢谢你的帮助！！
共有1个答案
- 如果我们遇到G中的一条路径，它具有更多的边（与其他路径相比），但在边权重总和上的权重最小（与所有其他路径相比），我们将不认为它是MST？
我想你说的“路径”是想写“树”吧？（“路径”是一个完全不同的概念：它只有两个端点，没有分支结构。）
一棵树是一个没有圈的连通图，所以每棵有n个顶点的树正好有n−1条边。因此，如果一个图有n个顶点，那么该图的每一棵生成树都必须恰好有n-1条边。如果你有一个超过n-1条边的子图，那么它就不是树，不是生成树，就像你推测的那样，它不是最小生成树。
但请注意，如果一个子图连接所有顶点，则该子图必然包含至少一个生成树；并且除非存在负权边，否则那些生成树将具有小于或等于子图的权。因此，尽管您的示例不是最小生成树，但它很可能包含一个最小生成树。
如果一个图只有一个生成树，那么那个生成树就是最小生成树，是的。但请注意，只有当图本身是树（在这种情况下，它是自己的最小生成树）时，才会发生这种情况；否则它肯定会有多个生成树。
当然，即使它有多个生成树，也有可能它们都有相同的权重，在这种情况下，它们都是最小生成树。
-
(b)假设图的最小生成树是唯一的。无向图的最小生成树中一对顶点之间的路径一定是最短（最小权）路径吗？ 我的回答是 (a)
-
主要内容：生成树,最小生成树数据结构提供了 3 种存储结构，分别称为线性表、树和图，如图 1 所示。 图 1 3 种存储结构 a) 是线性表，b) 是树，c) 是图。 在图存储结构中，a、b、c 等称为顶点，连接顶点的线称为边。 线性表是最简单的存储结构，很容易分辨。树和图有很多相似之处，它们的区别是：树存储结构中不允许存在环路，而图存储结构中可以存在环路（例如图 1 c) 中，c-b-f-c、b-a-f-b 等都是环路）。
-
赋权图G的最小瓶颈生成树是G的生成树，使得生成树中任何边的最大权值最小。MBST不一定是MST（最小生成树）。 请举例说明这些说法有意义的地方。
-
在一个具有不同正边的无向图中，是否可能有一个MST与最短路径树没有公共边？ 我一直试图引出不同的例子，但似乎这是不可能的。最短路径树中的最短路径边似乎也应该包括在MST中。
-
对于最小生成树问题的求解，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'的没有一条是一样的。