标签: minimum-spanning-tree

http://en.wikipedia.org/wiki/Minimum_spanning_tree

我希望将最小生成树算法与最佳算法进行对比.有人知道我在哪里可以找到这些算法的C++实现吗？我叮叮当当地用谷歌搜索,但没有找到任何东西.如果这些算法是最好的,肯定必须在某处进行C++实现？

迄今为止最快的最小生成树算法是由David Karger,Philip Klein和Robert Tarjan开发的,他们发现了一种基于Borůvka算法和反向删除算法的线性时间随机算法.[2] [3] Bernard Chazelle最快的非随机算法基于软堆,即近似优先级队列.[4] [5] 其运行时间为O(mα(m,n)),其中m是边数,n是顶点数,α是Ackermann函数的经典函数逆.函数α增长非常缓慢,因此对于所有实际目的,它可以被认为是不大于4的常数; 因此Chazelle的算法非常接近线性时间.如果边权重是具有有界位长的整数,则确定性算法已知具有线性运行时间.[6] 对于一般权重是否存在具有线性运行时间的确定性算法仍然是一个悬而未决的问题.然而,Seth Petie和Vijaya Ramachandran已经发现了一种可证明最优的确定性最小生成树算法,其计算复杂性未知.[7]

我已经测试了Boost C++的图算法.

我的作业有以下问题:

给出O(n + m)算法以找出边e是否是图的MST的一部分

(我们被允许在这项任务中得到别人的帮助,所以这不是作弊.)

我认为我可以做一个BFS并找出这个边缘是否是两个层之间的边缘,如果是,那么这个边缘是否是这些边缘中最小的边缘.但是当这个边缘不是BFS树的树边缘时,我能说什么呢？

我正在努力解决这个问题.

我们可以使用Kruskal算法或Prim的MST算法获得MST.

对于"次佳"MST,我可以:

1. 首先使用上述任一算法获取MST.
2. 对于来自MST的最佳边缘的每个V-1:
   a.首先删除或标记边缘
   b.继续计算没有边缘
   c的MST .比较并记录上次迭代的"次佳"MST
3. 最后我们有"第二好"的MST

但这在O(VE)中运行,其中V是顶点数,E是边数.

如何使用Union-find不相交集或LCA(最低共同的ancester)来加快速度？

提示,pseodo代码或Web链接指针.

任何帮助将非常感谢!谢谢:)

给定一个包含 N 个顶点的图以及存储在 tuple 中的顶点边之间的距离T1 = (d11, d12, …, d1n) to Tn = (dn1, dn2, …, dnn)。从顶点 V1 开始找出这个图的最小生成树。此外，打印旅行这棵生成的树所需的总旅行距离。

Example:
For N =5 
T1 = (0, 4, 5, 7, 5)
T2 = (4, 0, 6, 2, 5)
T3 = (5, 6, 0, 2, 1)
T4 = (7, 2, 2, 0, 5)
T5 = (5, 5, 1, 5, 0)

Selection of edges according to minimum distance are:
V1 -> V2 = 4
V2 -> V4 = 2
V4 -> …

我直观地认为,如果使用Prim的算法来查找图的最小生成树,那么选择哪个根节点无​​关紧要 - 结果MST将具有相同的权重.它是否正确？

如果我们有一个(任意)连接的无向图G,其边缘具有不同的权重,

1. G的每个MST都包含最小加权边？
2. 是否存在不包含最大加权边的G的MST？

另外,如果有人能够提供一些在处理此类MST问题时必须记住的关键事项,我会更感谢.

这是一个家庭作业问题.谢谢.

我在一些度量空间中有一大组点(数量n> 10000)(例如配备Jaccard距离).我想用最小的生成树连接它们,使用公制作为边缘的权重.

• 是否存在运行时间小于O(n ²)的算法？
• 如果没有,是否存在运行时间小于O(n ²)的算法(可能使用随机化)？
• 如果没有,是否有一个算法在小于O(n ²)的时间内运行并且给出了最小生成树的良好近似值？
• 如果没有,是否有这样的算法不存在的原因？

先感谢您!

编辑下面的海报: 查找最小生成树的经典算法在这里不起作用.他们的运行时间有一个E因子,但在我的情况下E = n ^2,因为我实际上考虑了完整的图表.我也没有足够的内存来存储所有> 49995000个可能的边缘.

我正在寻找一种算法(或任何其他方式)来确定给定的加权图是否在O(ElogV)中具有唯一的MST(最小生成树)？

我对权重没有任何了解(例如权重(e1)!=权重(e2)),如果该图只有一个唯一的MST,算法只返回True,否则返回False.

我开始使用Kruskal的算法,并检查是否find-set(u)== find-set(v)所以在MST中有一个圆圈,但这种方式并没有涵盖我想的所有场景:(

非常感谢!托梅尔.

可以使用Prim算法或Kruskal算法来找到顶点/节点和边/链接集合的最小生成树/图.我想要的是一种算法,它可以找到该集合的最小生成图,但结果图只需要包含任意选择的节点,而不是所有节点.如果结果图包含的节点数多于所需的节点数,那也没关系.

这样的算法存在吗？在修改图形以仅包含所需节点后,也许可以使用Prim(或Kruskal)算法？但是,我不确定如何在保持连接性的同时修改图形.

例如,假设我们有一个菱形的起始图(括号中的链接成本):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

现在,我们任意决定只需要节点A和D. 如果我们从A开始,我们仍然希望它采用左路径,因为((2 + 2)<(1 + 5)).

假设我们稍微修改了图表:

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

如果我们确定只需要节点A,D和E,我们就会发现成本最低的路径不一定是链路最少的路径.考虑A - B - D和A - C - E成本为7,但A - C - D和C - E成本为8.

我使用的是邻接矩阵,优先级队列是数据结构.

根据我的计算,复杂性是V^3 log V:

• 循环: V
• 检查相邻的顶点: V
• 如果条目已存在则检查队列,并更新相同的队列: V log v

但是,我到处都读到复杂性 V^2

请解释.