algorithm - 具有某些公共(public)边的两个图上的最小生成树

Question

给定两个具有加权边的完整图，我想在两个图上分别找到两个最小生成树 (MST)，条件是两个学习的 MST 在给定的边子集上具有公共(public)边。请注意，这两个图具有相同数量的顶点，但边权重都不同。

例如，如果两个图是顶点为{1,...,d}的完全边加权图。我们要求两个学习的 MST 在顶点为 {1,...,d/2} 的完整子图中具有相同的边。

我可以使用什么算法来找到这样的 MST？我尝试使用 Kruskal 算法的修改版，但没能成功。

Answer 1

不确定我是否遇到了问题，因为描述缺少一些重要的细节。
无论如何，这是一种具有给定约束的可能方法，使其适用。

只要两个图具有相同数量的边，并且您可以将这些图表示为边列表，就可以使用 MRT 算法找到它们所有的公共(public)生成树。
它通常被称为双图公共(public)生成树算法，并在 Mint、Read 和 Tarjan 的一篇学术文章中进行了描述。
请注意，Boost Graph Library 已经包含一个 proper implementation .

一旦找到这些树，就可以对它们进行迭代，以删除那些不是各自图形的最小生成树的树。请注意，如果您删除第一个图的 i-th 公共(public)生成树，您也应该删除第二个图的 i-th 树。
之后，如果该集合不为空，您可以删除所有那些不包含属于您问题一部分的给定边子集的树(我不完全理解您所说的边是共同的是什么意思到两个图，但如果它是一个约束，您可以在结果集上强制执行它)。
剩下的树就是你要找的树。

如果两个图的边数不一样，可以在较小的图上添加假节点和边。
换句话说，创建一个假节点 nf-i 并添加一条边 nf-i -> n-i，其中 n-i 是一个真实节点。给边缘一个空权重。
在该过程结束时，您可以轻松删除这些节点和边并恢复原始生成树。