Prim的MST:起始节点是否重要？
Prim的MST算法中，起始节点的选择对最终结果的影响非常小。在Prim的MST算法中，我们从一个任意的起始节点开始，逐步地向图中添加边和节点，直到所有的节点都被包含在最小生成树中为止。
在实际应用中，起始节点的选择可能会影响算法的运行时间和效率，但是不会影响最终的最小生成树的结果。因此，在实际应用中，通常会随机选择一个起始节点，或者选择一个具有较低权重边的节点作为起始节点，以提高算法的效率。
总之，在Prim的MST算法中，起始节点的选择对最终结果的影响非常小，因此可以随意选择一个起始节点来运行算法。
相关·内容
3回答
我直观地感觉到，如果一个人使用Prim算法来寻找图的最小生成树，那么选择哪个根节点并不重要--结果MST将具有相同的权重。这是正确的吗？
浏览 1提问于2009-11-24得票数 9
回答已采纳
3回答
有没有人知道如何改变prim的算法，从而处理一个没有连通的图？我知道我必须使用森林，但我不知道如何在Haskell中实现它。
浏览 3提问于2011-12-12得票数 0
1回答
有没有人可以教我如何使用PRIM算法找到MST？突出显示MST的边缘，并写入将节点添加到MST的顺序。谢谢
浏览 1提问于2010-12-31得票数 2
回答已采纳
2回答
Prim和Kruskal的算法都产生最小生成树。根据cut属性，对于这些算法，树的总成本将是相同的，但这两种算法可能会以相同的总成本给出不同的MST，因为我们在面对多个选择时按字母顺序选择它。例如，我们比较max(source，dest)，对于边A->B和B->C，我们比较来自A->B的A和来自B->C的B。
谢谢
浏览 1提问于2012-11-10得票数 4
2回答
Qa)如果G有一个具有唯一最重边e的循环，那么e不能是任何MST的一部分。由Dijkstra算法计算的最短路径树必然是MST.
我的答案是正确的，但我的直觉告诉我有什么不对劲。好吧..。Disjkstra和Prim都是贪婪的算法。他们每一次都
浏览 3提问于2011-10-29得票数 2
我正在编写一个程序，用Kruskal和Prim的算法找到一个给定的无向加权图的MST。我已经在程序中成功地实现了Kruskal的算法，但是Prim算法有问题。在Graph类中，我有一个Prim() -method，它应该计算MST：
ArrayList<Edge>-method只是一个布尔检查，以查
浏览 5提问于2012-03-31得票数 0
给出了成本严格大于10的边缘e。如果e的成本降低10，我们需要回答它的成本是否会提高。
我知道一种解决方案，它涉及到用cost<cost(e)-10生成一个只有边的新图。这个简单得多的解决方案有什么问题:以e的一个顶点v为例。找到v的最小成本边缘事件。现在降低e的成本，并再次找到v的最小成本边缘事件。如果有变化，这意味着prim会找到更好的MST，成本也会得
浏览 5提问于2020-10-02得票数 1
回答已采纳
2回答
如果我们修改最短路径问题，使得两个顶点之间的路径的成本是其上边的成本的最大值，那么对于任何一对顶点u和v，它们之间遵循最小成本生成树的路径是最小成本路径。
我如何证明这种方法是正确的？这是有道理的，但我不确定。有没有人知道文献中是否存在这种算法？它有名字吗？
浏览 0提问于2011-11-02得票数 3
回答已采纳
1回答
最小生成树与最短路径树
、、、
有没有可能在一个无向图中有一个没有公共边的MST，并且在一个无向图中有最短的路径树？
我一直试图举出不同的例子，但这似乎是不可能的。最短路径树中的最短路径边似乎也应该包含在MST中。
浏览 1提问于2016-03-10得票数 1
3回答
我有一个无向，正边权图(V，E)，我想要一个最小生成树覆盖一个顶点的子集k( Steiner树问题)。
我并不是将生成树的大小限制为k个顶点，而是确切地知道在MST中必须包含哪些k个顶点。从整个MST开始，我可以缩小边缘/节点，直到得到包含所有k的最小MST为止。我可以使用Prim的算法获得整个MST，并在子集k的MST未被破坏的情况下开始删除边缘&#x
浏览 5提问于2011-10-07得票数 44
Prim和Kruskal的算法用于寻找连通和无向图的最小生成树。为什么不能在有向图上使用它们呢？
浏览 1提问于2014-03-26得票数 23
回答已采纳
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
2回答
给定一个带权的无向连通图。w:E->{1,2,3,4,5,6,7} -意味着只有7个权重。我需要使用O(n+m)中的Prim算法和O( m*a(m，n))中的Kruskal算法找到一棵生成树。
浏览 4提问于2012-05-28得票数 0
1回答
给定一个G(V,E)加权(在边上)图，我需要找出属于每个MST的边的数量，以及属于至少一个但不是所有的边的数量，以及属于none的边的数量。该图以以下形式(示例)作为输入：First 3是节点的数量，second 3是edges.The的数量，后面三行是边我曾经想过运行一次Kruskal来查找MST，然后对属于G<em
浏览 32提问于2019-01-03得票数 3
回答已采纳
4回答
正如我的问题所说，我想知道为什么我们要在中使用优先级队列？它如何将我们从天真的方式中拯救出来(是的，我听说过，但不知道为什么)。Prim(G,w,r) //what is w (weight?) and r?then π[v] ← u我在考虑使用std::vector，然后使用std::make_heap()；作为存储边的优先队列
浏览 0提问于2011-08-12得票数 6
回答已采纳
1回答
Prim MST算法优化
、、、
我正在实现Prim的最小生成树算法。该算法工作正常。但是如果我有一个有10000个节点的图，这会花费太多的时间。： return graph[u].keys()defcartesian_product[u].keys() return cartesian_p
浏览 12提问于2017-06-30得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
