旅行商最小生成树变体
我正在尝试解决下面的图形练习：
在一个无向加权图中，有V个顶点和E条边。从标记为0的顶点开始，求访问T(T<=v)个顶点所需的最小权值。另外，如果两个被访问的顶点之间存在边，则其权重设置为0。
编辑：我给你举个例子。假设我们有一个图，有4个顶点，标记为0，1，2和3。我们有以下边(from,to,weight):(0,1,1)(0,2,2)(1,3,4)(2,3,1）最小生成树将包含边:(0,1,1)，(0,2,2）和（2,3,1）。有了它，从0开始每个顶点都是可达的。然而，练习的目标是达到这些顶点的T个数目。也就是说，例如，我们可能只需要到达顶点2和3，使得边（0,1,1）不需要，因此到达目标顶点所需的总权重是2+1，而不是1+2+1。
共有1个答案
看起来你的问题本质上是Steiner树问题，这是众所周知的NP-hard问题。
的确，你有一个无向加权图(V，E)。给定T,V的一个子集，你想找到一棵覆盖T的所有顶点的总权最小的树。
这里有一个例子，最明显的贪婪想法是行不通的。假设我们的图是一个不规则四面体ABCD的顶点和边，其中AB=BC=CA=5和AD=BD=CD=3。如果我们想将A、B和C连接在一起，我们所能做的最好的方法是使用边ad、bd和cd，总重量为9。如果我们决定不使用D，那么我们必须取两条边，每条边的长度5，总重量10。但是，集合abc的每个双顶点子集在最优解中使用一个权值5(ab、bc或ca)的直接边，而没有顶点d的边。
（哎哟！精确的长度在三维欧几里得几何学中是不可能的。不过，它可以作为一个例子。）
-
主要内容：生成树,最小生成树数据结构提供了 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？ 谢谢你的帮
-
赋权图G的最小瓶颈生成树是G的生成树，使得生成树中任何边的最大权值最小。MBST不一定是MST（最小生成树）。 请举例说明这些说法有意义的地方。
-
在一个具有不同正边的无向图中，是否可能有一个MST与最短路径树没有公共边？ 我一直试图引出不同的例子，但似乎这是不可能的。最短路径树中的最短路径边似乎也应该包括在MST中。