标签: spanning-tree

加权图的最小瓶颈生成树ģ是生成树ģ使得在生成树任何边的最大重量最小化.MBST不一定是MST(最小生成树).

请举例说明这些陈述是否有意义.

是否有算法可以找到无向图的生成树,从而最大限度地减少连接到多个边的顶点数？

例如,给定一个4 x 4网格图,我们希望在左边找到一个生成树(它有7个顶点连接到多个边)而不是右边的生成树(有12个):

编辑:如果我们只考虑平面图(甚至只是网格图),这个问题会更简单吗？

我正在阅读用于查找最小生成树的算法(在加权图的情况下)以及查找图是否具有哈密顿路径(这取决于哈密顿循环的存在).我把一切搞砸了.那哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点.虽然我们可以使用有效的算法来查找生成树(可能是最小的生成树),但为什么我们不能找到哈密顿电路的算法？我们可以继续一次添加和删除一个边缘,直到我们达到一个周期,也许,我们可以找到一个哈密顿周期？

我有一个带有未加权边缘的无向连通图.如何构建生成树(解决方案可能不是唯一的),以便最小化所有节点的深度总和？这显然没有找到最小生成树,因为边缘的"权重"实际上取决于孩子的深度.

我认为,给定一个指定的根,可以通过贪婪地将所有可以作为子节点连接的所有节点连接到以广度优先顺序连接到每个节点来形成具有最小深度总和的树.因此,我将通过应用相同的过程N次来找到具有最小总深度的树,将N个节点中的每一个指定为根,并且在N个候选中选择最小的一个.这是一个有效的算法吗？请指出它是否错误,或者是否存在更高效的问题.

假设如果所有边都具有正权重,则可以通过获取log每个边来获得最小产品生成树,然后应用Kruskal或Prim.但如果某些权重为负数,我们就无法应用此程序.因为我们需要包括奇数个负边,并且这些边必须是最大权重.在这种情况下该怎么做？

我不想找到所有最小的生成树,但我想知道它们中有多少,这是我考虑的方法:

• 使用prim或kruskal算法找到一个最小生成树,然后找到所有生成树的权重,并在它等于最小生成树的权重时递增运行计数器.

我找不到任何方法来查找所有生成树的权重,并且生成树的数量可能非常大,因此此方法可能不适合该问题.由于最小生成树的数量是指数级的,因此将它们计算起来并不是一个好主意.

• 所有权重都是正数.
• 我们也可以假设图表中没有重量超过三次.
• 顶点数量将小于或等于40,000.
• 边数将小于或等于100,000.

图中只有一个最小生成树,顶点权重不同.我认为找到最小生成树数量的最佳方法必须是使用此属性的东西.

编辑:

我找到了解决这个问题的方法,但我不确定,为什么会这样.任何人都可以解释一下.

解决方案:找到最小生成树的长度的问题是众所周知的; 用于查找最小生成树的两个最简单的算法是Prim算法和Kruskal算法.在这两个中,Kruskal的算法按其权重的递增顺序处理边缘.然而,Kruskal算法需要考虑一个重要的关键点:当考虑按权重排序的边缘列表时,可以将边缘贪婪地添加到生成树中(只要它们不连接已经以某种方式连接的两个顶点) ).

现在考虑使用Kruskal算法的部分形成的生成树.我们插入了一些长度小于N的边,现在必须选择长度为N的几条边.算法表明如果可能的话,我们必须在任何长度大于N的边之前插入这些边.但是,我们可以以我们想要的任何顺序插入这些边.另请注意,无论我们插入哪个边缘,它都不会改变图形的连通性.(让我们考虑两个可能的图形,一个具有从顶点A到顶点B的边缘,一个没有边缘.第二个图形必须具有A和B作为相同连通分量的一部分;否则从A到B的边缘将被插入到一点.)

这两个事实共同意味着我们的答案将是使用Kruskal算法的方式数量的乘积来插入长度为K的边(对于K的每个可能值).由于任何长度最多有三个边缘,因此可以强制使用不同的情况,并且可以在每个步骤之后确定连接的组件,因为它们通常是正常的.

我在interviewstreet.com上遇到了这个问题

机器再一次袭击了Xions王国.Xions王国有N个城市和N-1双向道路.道路网络使得任何一对城市之间都有一条独特的道路.

Morpheus有消息称K Machines计划摧毁整个王国.这些机器最初生活在王国的K个不同城市,从现在起他们可以随时计划并发动攻击.因此他要求Neo摧毁一些道路以破坏机器之间的连接,即在摧毁这些道路之后,任何两台机器之间都不应该有任何路径.

由于攻击可以在任何时间进行,因此Neo必须尽快完成此任务.王国中的每条道路都需要一定的时间才能被摧毁,而且每次只能摧毁一条道路.

您需要编写一个程序,告诉Neo他需要最少的时间来破坏机器之间的连接.

样本输入输入的第一行包含两个空格分隔的整数,N和K.城市编号为0到N-1.然后按照N-1行,每行包含三个以空格分隔的整数xyz,这意味着有一条连接城市x和城市y的双向道路,并且要消耗这条道路需要z个单位的时间.然后按照K行,每行包含一个整数.Ith integer是第i台机器当前所在城市的id.

输出格式在一行中打印中断机器之间连接所需的最短时间.

样本输入

5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0

Run Code Online (Sandbox Code Playgroud)

样本输出

10

Run Code Online (Sandbox Code Playgroud)

说明Neo可以破坏连接城市2和城市4的重量5的道路,以及连接城市0和城市1的重量为5的道路.由于一次只能摧毁一条道路,所以总的最小时间是10个单位时间.在摧毁这些道路后,这些机器都无法通过任何路径到达其他机器.

约束

2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000

Run Code Online (Sandbox Code Playgroud)

有人可以提出如何处理解决方案的想法.

在概念上,图表中的生成树和生成森林之间有什么区别.

此外,是否可以通过DFS或BFS遍历构建生成林？为什么？怎么样？

我理解生成树,但我找不到任何关于跨越森林的明确解释.甚至维基百科(https://en.wikipedia.org/wiki/Spanning_tree)也没有给出明确的定义.我的书(数据结构和算法,Wiley - 第六版)也没有关于跨越森林的定义.

我想知道,如果我们有一个图表,例如其中包含三个连接组件,是否可以通过DFS/BFS遍历构建生成林？

可以通过运行 kruskal 算法找到最大生成树（只需更改边函数并首先考虑最大权重边）。我有兴趣找到最大权重欧几里得生成树。是否存在比 kruskal 更好的算法（更好的最坏情况运行时间）来找到这样的生成树？

给定无向图和连通图G，找到直径最小的生成树。