标签: kruskals-algorithm

我想知道什么时候应该使用Prim的算法,什么时候Kruskal才能找到最小的生成树？它们都具有简单的逻辑,同样最坏的情况,唯一的区别是实现可能涉及一些不同的数据结构.那么决定因素是什么？

与最小生成树的Kruskal算法相反吗？我的意思是,每一步选择最大重量(边缘)？

找到最大生成树的任何其他想法？

我正在计算像这样的kruskal算法的时间复杂度(请参阅图像附加中的算法)

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

CLRS算法:

这是正确的还是我做错了请告诉我.

任何人都可以请给出这两种算法的一些应用程序,它们可以用于哪些应用程序？

设G =(V,E)为无向图.如果G的每个循环在F中具有至少一个边缘,则边集的F ​​FE被称为 反馈边集.

(a)假设G未加权.设计一种有效的算法来查找最小尺寸的反馈边集.

(b)假设G是具有正边权重的加权无向图.设计一种有效的算法来找到最小权重反馈边集.

我的解决方案(需要建议):

a)最小尺寸反馈边集:由于图是未加权的,我们可以使用DFS.我们像往常一样从任何顶点开始DFS.当我们遇到后边缘时,我们将其插入一组反馈边缘.当DFS完成时,该集将是答案.

b)最小权重反馈边集:由于图是加权的,我们可以使用Kruskal.但Kruskal通常以最小重量的边缘开始.如果我们可以否定所有边权重,然后运行Kruskal,每当我们在相同组件的顶点之间获得边缘时,我们可以将其保存在反馈边集中.最后,否定边权重.我建议否定边权重的原因是因为我们需要最小权重反馈集.对于负重,Kruskal将从具有最小重量(实际上最大)的边缘开始,并且将发现具有较小重量的相同组件的边缘.

有人能说出这个解决方案是否正确吗？

我试图理解为什么Prim和Kruskal在稀疏和密集的图形方面有不同的时间复杂性.在使用几个小程序来演示每个小程序如何工作之后,我仍然对图的密度如何影响算法感到困惑.我希望有人能给我一个正确方向的推动.

参考Ada中的Kruskal算法,我不知道从哪里开始.

在我实际编写程序之前,我正在考虑所有内容,但我很遗憾我应该使用什么数据结构以及如何表示所有内容.

我最初的想法是在邻接列表中表示完整的树,但是阅读维基百科的算法说明create a forest F (a set of trees), where each vertex in the graph is a separate tree并且我不确定如何实现它而不会很快变得非常混乱.

它接下来create a set S containing all the edges in the graph要说的是,但我不知道最好的方法是做什么.我在想记录的数组,具有to,from和weight,但我失去了对forest.

最后,我试图弄清楚我是如何知道边缘是否连接两棵树,但我不知道最好的方法是做什么.

设G =(V,E)为加权,连通和无向图,并且令T为最小生成树.设e是不在E中的任何边(并且具有权重W(e)).证明或反驳:TU {e}是包含G'=(V,EU {e})的最小生成树的边集.

嗯,这对我来说听起来是对的,所以我决定证明这一点,但我每次都被卡住了......

例如,如果e是具有最小权重的新边缘,那么谁可以向我们保证T中的边缘不会以不良方式被选择,这将阻止我们在没有E中其他边缘的"帮助"的情况下获得新的最小权重 - T？

我将不胜感激任何帮助,在此先感谢.

Kruskal的算法如下:

MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v? G.V
3.      MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ? G.E, taken in nondecreasing order by weight w
6.      if FIND-SET(u)!=FIND-SET(v)   
7.         A=A U {(u,v)}  
8.         Union(u,v)
9. return A

根据我的教科书:

初始化第1行中的集合A需要O(1)时间,并且对第4行中的边缘进行排序的时间是O(E lgE).第5-8行的for循环在不相交的林上执行O(E)FIND-SET和UNION操作.随着| V | MAKE-SET操作,这些操作总共需要O((V + E)α(V))时间,其中α是一个非常缓慢增长的函数.因为我们假设G是连接的,所以我们有| E | <= | V | -1,因此不相交设置操作需要O(Eα(V))时间.此外,由于α(V)= O(lgV)= O(lgE),因此Kruskal算法的总运行时间为O(E lgE).观察到| E | <| V | ^ 2,我们有lg | E | = O(lgV),因此我们可以将Kruskal算法的运行时间重新表示为O(E …

我想知道Boruvkas算法和Kruskals算法之间的区别。

他们的共同点：

• 两者都在无向图中找到最小生成树（MST）
• 两者都将最短边添加到现有树中，直到找到 MST
• 两者都从整体上看待图，这与 Prims 算法不同， Prims算法将一个又一个节点添加到 MST 中
• 两种算法都是贪婪的

唯一的区别似乎是，Boruvka 的视角是每个单独的节点（从那里寻找最便宜的边），而不是查看整个图（像 Kruskal 那样）。

因此，Boruvka 似乎应该相对容易并行执行（与 Kruskal 不同）。真的吗？