2回答
我是最小生成树的新手，并试图找出在任何特定情况下使用哪种MST算法。有没有人能举几个例子，说明哪种MST算法比其他算法更合适
浏览 3提问于2013-01-04得票数 2
回答已采纳
3回答
我有一个无向，正边权图(V，E)，我想要一个最小生成树覆盖一个顶点的子集k( Steiner树问题)。
我并不是将生成树的大小限制为k个顶点，而是确切地知道在MST中必须包含哪些k个顶点。从整个MST开始，我可以缩小边缘/节点，直到得到包含所有k的最小MST为止。我可以使用Prim的算法获得整个MST，并在子集k的MST未被破坏的情况下开始删除边缘&#x
浏览 5提问于2011-10-07得票数 44
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此它们可以从不同的顶点开始，从而生成不同的树</
浏览 3提问于2014-04-29得票数 2
回答已采纳
1回答
任务是提出一个算法，为满足这两个条件的G寻找生成树的总权重(按优先级排序)：
总生成树权重应该最小化。，这意味着，例如，权重为120的生成树T1最多有4条边具有相同的权重(而这4条边的权重为15)应该优于权重最多为4条边具有相同权重的生成树T2 (而这4条树的权重最多为8)。我已经为图实现了Boru
浏览 2提问于2017-10-17得票数 2
回答已采纳
我可以使用什么算法来解决这样的问题：
有一个图的正权重，我想知道每个节点连接的权重的最小和(像网络一样连接，其中每个节点是一个eg。网络设备)。
浏览 1提问于2010-04-26得票数 0
回答已采纳
那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定强连通分量的数量。2. MST中必须存在由铰接点组成的边。3.每个连接组件中最亮的边必须存在于MST中。
浏览 1提问于2018-10-20得票数 1
2回答
我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
1回答
我有一个对称的图，并创建了一棵树，其中包含从随机顶点到任何其他顶点的所有最短路径。是否可以使用树构建最小生成树(MST)？我的算法类似于深度优先算法。
浏览 1提问于2013-07-06得票数 0
回答已采纳
3回答
查找连接所有节点的最短路径集
、、、、
我只需要每个点连接到至少一个其他点，这样集合中的所有点至少间接地彼此连接，所选连接的长度之和将被最小化。因此，它应该是非循环的，以最小化连接长度的总和。简单的最近邻居算法(即，将每个点连接到尚未连接到它的最近邻居)不起作用，因为彼此相距较远的小集群最终将被隔离，而您最终将最终创建循环。
浏览 6提问于2020-01-31得票数 1
假设您使用Kruskal或Prim的算法来计算第一个MST，您希望检查是否还有其他的MST。我可以在O(E/V)时间内做到这一点。
当权值为小整数时，可在线性最坏情况下求解。弗雷德曼和威拉德，“最小生成树</em
浏览 2提问于2013-12-20得票数 0
回答已采纳
2回答
设计一种算法，该算法采用加权图G，并找出代价对非MST边的最小变化，这将导致G的最小生成树发生变化。若要更改MST，我们需要更改非MST边缘s.t的权重。它比它的起始顶点和MST中的结束顶点的路径中的最大边小一个。
因此，我们可以从移动MST的边缘开始，对于每个顶点，检查是否有一个非MST边缘。如果存在，则可以进行bfs以到达边缘的端点(在<e
浏览 1提问于2012-05-28得票数 1
假设给定的图G (有n个顶点，m条边)的最小生成树T和一个权重为w的新边e= (u，v)，我们将添加到G中。
I)检查T是否仍为MST。II)如果不是，给出一个有效的算法来寻找图G+ e的最小生成树。
浏览 4提问于2013-05-29得票数 2
回答已采纳
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
2回答
计算此图的最小生成树的最快算法是什么？我们仍然可以使用现有的最小生成树算法，例如Kruskal的算法O(m log N)或Prim的算法(O(m +n log n))。有没有比更传统的MST算法更具竞争力的算法，这些算法能够利用边缘长度被限制在某个范围内这一事实？
谢谢!
浏览 4提问于2012-01-16得票数 12
回答已采纳
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
腾讯云开发者
