algorithm - 有向图的双向最小生成树

Question

给定具有加权边的有向图，可以使用什么算法来给出具有最小权重的子图，但允许从图中的任何顶点移动到任何其他顶点（假设任何两个顶点之间的路径始终存在） .

这样的算法存在吗？

score 3 · Accepted Answer

尽管他们自己并不正确，但花时间关注 Vitalii 的 Wikipedia 链接很快发现了这个算法：

score 2 · Accepted Answer

将图中的每个节点拆分为两个节点。一个节点将接受原始节点的所有传入边，而另一个节点将拥有所有传出边。然后，将方向放在所有边上，因此图形是无向的。然后，您可以在图上运行标准 MST 算法（Prim's，Kruskal's），您将确保每个原始节点都可以被其他每个原始节点传送到。

score 2 · Accepted Answer

这看起来是 NP-Hard：最小权重强连接跨越子图问题。

我相信哈密顿循环问题可以简化为：给定一个图 G(V,E)，构造一个有向图 DG，其中出现的边的权重为 1，不出现的边的权重为 100 (|V|+1)。DG 有一个最小权重的强连接跨越子图，正好 |V| 当且仅当 G 具有哈密顿循环。

score 1 · Accepted Answer

这是一个有向斯坦纳树问题。作为施泰纳树，它是 NP-Hard。

你可以在这里找到一些近似算法：

score 0 · Accepted Answer

选择任何节点并将其返回。

您的意思是找到最大的强连接子图（可能删除的节点数量最少），还是最小权重跨越子图（不允许删除节点）？

5 回答 5