给定两个带有加权边的完整图，我想分别在两个图上找到两个最小生成树（MST），条件是两个学习的 MST 在给定的边子集上具有公共边。请注意，这两个图具有相同数量的顶点，但边权重都不同。
例如，如果这两个图是具有顶点 {1,...,d} 的完整边加权图。我们要求两个学习的 MST 在具有顶点 {1,...,d/2} 的完整子图上具有相同的边。
我可以使用什么算法来查找此类 MST？我尝试使用 Kruskal 算法的修改，但无法使其工作。
问问题
862 次
1 回答
0
不确定我是否遇到了问题，因为描述缺少一些重要的细节。
无论如何，这是一种可能的方法，具有给定的约束，使其适用。
只要两个图具有相同数量的边，并且您可以将这些图表示为边列表，MRT 算法就可以用于查找它们所有的公共生成树。
它通常被称为两图通用生成树算法，并在 Mint、Read 和 Tarjan 的学术文章中进行了描述。
请注意，Boost Graph Library 已经包含一个正确的实现。
找到这些树后，您可以遍历它们以删除它们各自图形的不是最小生成树的树。请注意，如果您删除第一个图的第 i 个通用生成树，您也应该删除第二个图的第 i 个树。
之后，如果集合不为空，您可以删除所有那些不包含属于您的问题的给定边子集的树（我不完全理解您的意思是说边是共同的到两个图，但如果它是一个约束，你可以在结果集上强制执行它）。
剩下的树就是你要找的树。
如果两个图的边数不同，您可以将假节点和边添加到较小的图中。
换句话说，创建一个假节点nf-i并添加一条边nf-i -> ni，其中ni是一个真实节点。给边缘一个零权重。
在该过程结束时，您可以轻松删除这些节点和边并取回原始生成树。
于 2016-12-18T09:01:58.963 回答