logo标签列表

一种有向图的双向最小生成树

algorithmlanguage-agnosticgraph-theoryminimumminimum-spanning-tree
11

对于一张带权有向图，有什么算法可以用来找到一个具有最小权值的子图，但是允许从图中任何一个顶点到达另一个顶点（在假设任意两个顶点之间都存在路径的情况下）。

是否存在这样的算法？

5个回答
3
Edmond算法只能保证图中每个节点都可以从根节点访问，但不能保证每个节点都可以从其他每个节点访问。 - Mantas Vidutis
我的链接的NP分类与它对原始问题的相关性有什么关系？ - Mathew
“这是NP难问题”意味着原始问题。你的算法是针对另一个问题的多项式时间算法。 - Aryabhatta
2

将图中的每个节点分成两个节点。一个节点将接受原始节点的所有入边，另一个节点将拥有所有出边。然后，取消所有边的方向，使图形成无向图。 然后，您可以在图上运行标准MST算法（Prim的、Kruskal's），并确保每个原始节点可由其他原始节点到达。

不幸的是，这样做不起作用，因为它会向最终图形添加不必要的边。即使某个节点不需要具有该边，至少一个节点将附加额外的边。例如，在具有顶点A、B、C和边缘AB、BA、BC、CB、AC、CA的图中，图的最小生成可能仅是边缘AB、BC、CA。但是使用您的方法，这三条边将无法互相连接，并且需要添加其他边才能完成MST。 - Mantas Vidutis
2
这似乎是一个NP-Hard问题：最小权重强连通生成子图问题。
我认为可以将哈密顿环问题归约为此问题：给定一个图G（V，E），构造一个有向图DG，对于出现的边赋予1的权重，对于没有出现的边赋予权重100（| V | +1）。当且仅当G具有哈密顿环时，DG具有一种恰好为| V |的最小权重强连通生成子图。
这篇论文提供了近似算法：http://portal.acm.org/citation.cfm?id=844363。
1
但是有向斯坦纳树需要一个根节点，不是吗？ - highBandWidth
算法可以找到最佳的根顶点，但您也可以指定一个根和一组顶点。 - jwinandy
0

选择任何节点并返回它。

您是否意味着查找最大强连通子图（可能删除的节点数最少），或者最小权重生成树子图（不允许删除节点）？

标题说的是“生成树”，所以我猜应该是指后者。 - Aryabhatta
@Moron：啊，我错过了那个:)。在这种情况下，你的答案是正确的。 - BlueRaja - Danny Pflughoeft
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接